Merge Sorted Array Algorithm Solution

The merge sorted array problem requires merging two sorted arrays into one sorted array in-place. This classic algorithmic challenge tests understanding of two-pointer techniques and efficient array manipulation in coding interviews at top tech companies.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we assume that the input arrays are already sorted in non-decreasing order?
2. What is the expected time complexity constraint? Are we aiming for O(m+n) or better?
3. Do we need to handle cases where one or both arrays are empty?
4. Is it acceptable to modify the input array nums1 in-place, or should we return a new merged array?
5. What is the maximum size of the input arrays?

Restated problem: Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 such that the merged array remains sorted in non-decreasing order. The first array nums1 has enough space (with size m + n) to hold all elements from both arrays.

Input/output specification:

• Input: nums1 (array of size m + n, with first m elements valid and remaining n elements as 0s), m (number of valid elements in nums1), nums2 (array of size n), n (number of elements in nums2)
• Output: nums1 modified in-place to contain the merged sorted array

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Assumptions made:

• Both input arrays are sorted in non-decreasing order
• nums1 has sufficient space to accommodate all elements from both arrays
• We can modify the input array nums1 in-place

Data shape and hidden structure: The problem presents two sorted arrays where the first array has extra capacity to hold all elements. The key insight is that we can merge from right to left to avoid overwriting valid elements in nums1, since the extra space is at the end of nums1. This creates a clean merging pattern where we compare elements from both arrays and place the larger one at the end of nums1.

2. Pattern Recognition

Most likely pattern

The most likely pattern is Two Pointers with a Reverse Two-Pointer Technique.

Wording that signals the pattern

• "Merge sorted arrays" - This immediately suggests we're combining two sorted sequences
• "Sorted arrays" - Indicates the data is already ordered, which is key for optimization
• "Merge" - Standard operation in merge sort and similar algorithms

Why this fits the pattern

This problem fits the Two Pointers pattern because:

1. We have two sorted input arrays that need to be combined into one sorted array
2. The arrays are already ordered, so we can leverage their sorted property to avoid full sorting
3. We're essentially performing a merge operation that's fundamental to merge sort
4. The constraint that nums1 has enough space suggests we're working with an in-place merge approach

Core insight

The key insight is that since nums1 has sufficient space at the end, we can merge from right to left instead of left to right. This avoids overwriting elements in nums1 that haven't been processed yet, which would happen if we merged from left to right.

The pattern is not just about merging but about reverse two-pointer technique - starting from the end of both arrays and placing elements in their correct final positions in nums1. This is a classic optimization for merge operations when one array has extra space at the end.

3. Approach Evolution

Interview communication script:

My first instinct is to simply merge the arrays by copying all elements from nums2 into nums1 and then sorting, but that's O(n log n) because I'd need to sort the entire array. That's not optimal since we already have both arrays sorted.

Let me think about how to optimize this. I notice that if I work backwards from the end of both arrays, I can place elements in their correct final positions without overwriting unprocessed elements. This is a classic two-pointer technique, but I need to be careful about indices.

I notice that if I maintain the invariant that at each step, I'm placing the largest remaining element in the correct final position, I can reduce this to O(n + m) time by working from right to left. The key insight is that since nums1 has enough space at the end, I can use that space to build the merged array from right to left.

The approach is:

1. Use three pointers: one at the end of nums1 (where we'll place elements), one at the end of valid elements in nums1, and one at the end of nums2
2. Compare elements from both arrays and place the larger one at the current position
3. Continue until all elements are processed

This is efficient because:

• We process each element exactly once
• We don't need extra space beyond what's already allocated
• We avoid the cost of sorting

Brute-force approach and why it is not ideal:

My first brute-force approach would be to copy all elements from nums2 into nums1 starting at index m, then sort the entire nums1 array. This would work but has O((n+m) log(n+m)) time complexity due to the sorting step. This is inefficient because:

• We're throwing away the fact that both arrays are already sorted
• We're doing unnecessary work by sorting when we could merge in linear time
• The sorting operation dominates the runtime

Improved approach and the key optimization:

The key optimization is to merge from right to left instead of left to right. Since nums1 has sufficient space at the end, we can build the merged array in reverse order without overwriting elements that haven't been processed yet.

The crucial insight is to use three pointers:

1. i - points to the last element in nums1 that we haven't processed yet
2. j - points to the last element in nums2 that we haven't processed yet
3. k - points to the current position in nums1 where we should place the next largest element

This allows us to maintain the invariant that all elements in nums1 are already in their correct final positions, and we never overwrite unprocessed elements.

Final approach with step-by-step reasoning:

1. Start from the end of both arrays (index m-1 in nums1 and index n-1 in nums2)
2. Compare elements at current positions in both arrays
3. Place the larger element at the end of nums1 (at position m+n-1)
4. Move the corresponding pointer backward
5. Continue until all elements are processed
6. Handle remaining elements in either array (if any)
7. The algorithm terminates correctly because we process all elements exactly once

Important invariants that must hold:

• At each step, the current position in nums1 (k) always has enough space to accommodate the next element
• Elements are placed in their correct final sorted order
• We never overwrite elements that haven't been processed yet

Why this approach works: This is a classic merge operation from merge sort, but adapted to work in-place. By merging from right to left, we ensure that when we place an element at the end of nums1, it's already in its final position and won't be overwritten by subsequent operations.

4. Data Structure Choice

For this problem, I'm choosing to use the input arrays themselves as the primary data structures, with a focus on leveraging the existing space in nums1 to avoid additional memory allocation.

Primary Data Structures:

• int[] nums1 - This is the main array that needs to be modified in-place. It has enough capacity to hold all elements from both arrays.
• int[] nums2 - This is the second array containing elements to be merged into nums1.

Why these data structures are needed: The problem explicitly requires modifying nums1 in-place to contain the merged sorted elements. Since nums1 already has sufficient space (size m + n), we don't need any additional arrays or collections. The existing array structure allows us to work backwards from the end, which is crucial for avoiding overwrites.

Time and space impact:

• Time complexity is O(m + n) as we process each element once
• Space complexity is O(1) since we're using only the existing arrays and a few integer variables for indices

Helper structure: I'll use three integer pointers (i, j, k) to track positions in the arrays:

• i points to the current element in nums1 (from the original elements)
• j points to the current element in nums2
• k points to the current position in nums1 where we'll place the next largest element

This approach eliminates the need for any additional data structures like temporary arrays or collections, making it optimal in terms of space usage.

The key insight is that we can work backwards from the end of nums1 to avoid overwriting elements that haven't been processed yet, which is why we don't need a separate result array.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

Example: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Step 1: Initialize pointers

• i = m - 1 = 2 (points to last element in valid nums1 data: 3)
• j = n - 1 = 2 (points to last element in nums2: 6)
• k = m + n - 1 = 5 (points to last position in nums1: 0)

Step 2: Compare and place largest element

• nums1[i] = 3, nums2[j] = 6
• Since 6 > 3, place 6 at nums1[k] = 0
• Decrement: j = 1, k = 4

Step 3: Continue comparison

• nums1[i] = 3, nums2[j] = 5
• Since 5 > 3, place 5 at nums1[k] = 0
• Decrement: j = 0, k = 3

Step 4: Continue comparison

• nums1[i] = 3, nums2[j] = 2
• Since 3 > 2, place 3 at nums1[k] = 0
• Decrement: i = 1, k = 2

Step 5: Continue comparison

• nums1[i] = 2, nums2[j] = 2
• Since 2 = 2, place 2 at nums1[k] = 0
• Decrement: j = -1, k = 1

Step 6: Handle remaining elements

• Since j < 0, we're done with nums2
• Now nums1 = [1,2,2,3,5,6] with all elements in correct positions

Key insight: By working backwards from the end, we avoid overwriting valid elements in nums1 that haven't been processed yet. The algorithm correctly handles all edge cases including when one array is exhausted before the other.

The termination condition is when j < 0, meaning all elements from nums2 have been placed, at which point nums1 is guaranteed to be properly sorted.

6. Java Solution

public class MergeSortedArray {
    /**
     * Merges two sorted arrays into the first array in-place.
     * nums1 has size m + n where the first m elements are valid,
     * and the remaining n positions are 0s to be filled.
     * 
     * @param nums1 First array with m + n capacity, first m elements valid
     * @param m Number of valid elements in nums1
     * @param nums2 Second array with n elements
     * @param n Number of elements in nums2
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointers for the three positions:
        // i: current position in nums1 (valid elements)
        // j: current position in nums2
        // k: current position in nums1 to fill (from end)
        int i = m - 1; // Last valid element in nums1
        int j = n - 1; // Last element in nums2
        int k = m + n - 1; // Last position in merged array
        
        // Merge from the end to avoid overwriting valid elements in nums1
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--]; // Take from nums1
            } else {
                nums1[k--] = nums2[j--]; // Take from nums2
            }
        }
        
        // Copy remaining elements from nums2 (if any)
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
        
        // Note: No need to copy remaining elements from nums1,
        // since they're already in their correct positions
    }
}

The solution uses a reverse two-pointer approach to merge the arrays in-place. By starting from the end and working backwards, we avoid overwriting valid elements in nums1 that haven't been processed yet. The algorithm handles all remaining elements from nums2 after the main merge loop, since any remaining elements in nums1 are already in their correct positions.

7. Complexity Analysis

Time Complexity: O(m + n)

The algorithm makes a single pass through both arrays using the two-pointer technique. Each element from nums1 and nums2 is visited at most once, resulting in linear time complexity. The while loop processes each element exactly once, and the final copy operations are also O(m + n) total.

Space Complexity: O(1)

The solution operates in-place on the nums1 array without requiring any additional data structures proportional to input size. All operations use only a constant amount of extra space for the three integer pointers (i, j, k). The problem constraints explicitly allow modifying the input array in-place.

Why These Bounds Are Correct

The time complexity is optimal for this problem because we must examine each element at least once to determine its final position in the merged array. Since we have m + n elements total, we cannot do better than O(m + n) time. The space complexity is optimal because the problem requires in-place merging, and we're not allowed to use additional arrays that scale with input size.

The solution is near-optimal as it achieves the theoretical lower bound for this problem's constraints. The approach avoids unnecessary operations like sorting or multiple passes, making it both time and space efficient.

The algorithm's linear complexity is achieved by leveraging the fact that both input arrays are already sorted, eliminating the need for more expensive operations like heap-based merging or divide-and-conquer approaches that would require O((m + n) log(m + n)) time.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty arrays: When either nums1 or nums2 is empty, the merge should handle gracefully. If nums1 is empty, we just copy nums2 into it.
• Single element arrays: The algorithm must correctly handle single-element arrays, ensuring proper positioning in the merged result.
• One array is completely smaller than the other: The merge should work correctly even if all elements from one array are smaller than all elements from the other.

Duplicate Values and Repeated States

• Duplicate values within arrays: If nums1 or nums2 contain duplicates, the merge must preserve all occurrences. For example, if both arrays have 3 at different positions, both should appear in the merged result.
• Duplicate values across arrays: When merging arrays with overlapping elements, duplicates should be handled correctly to maintain the sorted order.

Boundary Conditions

• m = 0: When nums1 has zero valid elements, we should copy all elements from nums2 into nums1.
• n = 0: When nums2 has zero valid elements, we should leave nums1 unchanged.
• m = nums1.length: When all elements in nums1 are valid, we should merge nums2 into nums1 without leaving any unused space.
• Index bounds: Care must be taken to avoid array index out of bounds errors, particularly when comparing elements from both arrays.

Common Implementation Mistakes

• Incorrect pointer management: Using wrong indices or not properly decrementing pointers can lead to incorrect element placement.
• Overwriting valid data: Not using the reverse merge approach (starting from the end) can cause overwriting valid elements in nums1 before they are processed.
• Incorrect loop termination: Not properly handling the case where one array is exhausted before the other, leading to missed elements or index errors.
• Misunderstanding input structure: Assuming that nums1 has enough space or not understanding that the first m elements are valid and the rest are zeros.

Example of Common Pitfall

// Incorrect approach - forward merge that overwrites valid data:
// This will overwrite nums1 elements before they are processed
for (int i = 0; i < n; i++) {
    nums1[m + i] = nums2[i]; // This can overwrite valid elements
}

The correct approach uses reverse merge to avoid overwriting valid data in nums1.

9. Alternative Approaches

There are several alternative approaches to solving the merge sorted array problem, each with different trade-offs:

Approach 1: Two-Pointer from Left to Right Instead of merging from the end, we could merge from the beginning using two pointers. However, this requires shifting elements in array nums1 as we go, which would result in O(n²) time complexity in worst case. This approach is inefficient because we'd need to make room for elements by shifting existing elements.

Approach 2: Extra Space with Merge Sort Logic We could create a new array of size m+n and merge elements using standard merge sort technique, copying the result back to nums1. This approach uses O(m+n) extra space and O(m+n) time, which is acceptable but not optimal for the given constraints where we must modify nums1 in-place.

Approach 3: Sort After Append Append all elements from nums2 to the end of nums1 and then sort the entire array. This approach is O((m+n) log(m+n)) time complexity due to sorting, which is worse than our optimal O(m+n) solution.

Comparison with Primary Solution: The primary approach is superior because:

1. It uses O(1) extra space (no additional arrays)
2. It achieves optimal O(m+n) time complexity
3. It leverages the fact that nums1 has sufficient space at the end
4. It avoids unnecessary operations like sorting or element shifting

The key insight that makes our primary approach optimal is recognizing that we can merge from the end without overwriting unprocessed elements, which is only possible because we're given extra space at the end of nums1. This is a classic example where understanding the constraints leads to an optimal solution rather than a generic approach.

10. Test Cases

public class MergeSortedArray {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Implementation will go here
    }
}

Sample Test Cases

Basic case with mixed values:

int[] nums1 = {1, 2, 3, 0, 0, 0};
int m = 3;
int[] nums2 = {2, 5, 6};
int n = 3;
// Expected: [1, 2, 2, 3, 5, 6]

Edge case - empty second array:

int[] nums1 = {1, 2, 3};
int m = 3;
int[] nums2 = {};
int n = 0;
// Expected: [1, 2, 3]

Edge case - empty first array:

int[] nums1 = {0, 0, 0};
int m = 0;
int[] nums2 = {1, 2, 3};
int n = 3;
// Expected: [1, 2, 3]

Tricky case - all elements equal:

int[] nums1 = {1, 1, 1, 0, 0, 0};
int m = 3;
int[] nums2 = {1, 1, 1};
int n = 3;
// Expected: [1, 1, 1, 1, 1, 1]

Boundary case - single element arrays:

int[] nums1 = {0};
int m = 0;
int[] nums2 = {1};
int n = 1;
// Expected: [1]

Edge case - one array completely smaller than the other:

int[] nums1 = {1, 2, 3, 0, 0, 0};
int m = 3;
int[] nums2 = {4, 5, 6};
int n = 3;
// Expected: [1, 2, 3, 4, 5, 6]

11. Final Summary

The core idea is to merge two sorted arrays efficiently by working backwards from the end of the arrays, placing the larger element at the current position in the merged array. This approach avoids overwriting unprocessed elements by starting from the end and moving towards the beginning, ensuring optimal O(m+n) time complexity with O(1) space usage.

This solution works because it leverages the fact that both input arrays are already sorted, allowing us to always choose the next largest element without needing additional sorting operations. The backward traversal ensures we never overwrite elements that are yet to be processed, making it both time and space optimal for the given constraints.

What makes this solution efficient is its single-pass nature with constant extra space usage, avoiding the need for additional data structures or multiple iterations over the input arrays.