Merge Sorted Arrays Algorithm Solution

The merge sorted arrays problem requires combining two sorted integer arrays into a single sorted array efficiently. This canonical DSA problem tests understanding of two-pointer techniques, array manipulation, and algorithmic optimization in technical interviews at top tech companies.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are we guaranteed that each input array is already sorted in ascending order?
2. What are the constraints on the size of the arrays (e.g., max length, number of arrays)?
3. Should we return a new merged array or modify one of the input arrays in-place?
4. Can we mutate the input arrays, or do we need to preserve their original contents?
5. For follow-up, should we aim for O(n log k) time complexity where k is the number of arrays?

Restatement of the pattern: The merge sorted arrays problem involves combining multiple sorted arrays into a single sorted array. This is a fundamental pattern in merge-based algorithms where we leverage the pre-sorted nature of input data to achieve better than O(n log n) time complexity.

Signal words and constraint shape:

• "sorted arrays" or "sorted input"
• "merge" operation in the problem description
• Multiple arrays that are individually sorted
• Input size constraints that suggest we can afford O(n log k) solutions where k is the number of arrays

Assumptions made:

• All input arrays are sorted in ascending order
• The problem is asking for a single merged sorted array as output
• We can use additional space for the result (unless specified otherwise)
• Arrays are not empty in the main problem context, though edge cases should be handled

Scenario fit: This pattern is best suited for static scenarios where all input arrays are known upfront. It's less appropriate for streaming data where new elements arrive continuously, though it can be extended to handle online merging through more complex data structures like priority queues.

The pattern works because we can efficiently merge two sorted arrays in linear time, and by applying this principle iteratively or using a min-heap approach, we can merge multiple sorted arrays efficiently.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Merge two sorted arrays"
• "Given two sorted arrays, return a merged sorted array"
• "Combine sorted lists"
• Input arrays are already sorted in ascending order
• Constraints like "You may assume the arrays are sorted" or "arrays are in non-decreasing order"

Why this pattern fits better than the most common alternatives: This pattern is specifically optimized for sorted inputs, making it far more efficient than general merging approaches. Unlike generic merge operations that require sorting or complex data structure management, this pattern leverages the inherent ordering to achieve O(n+m) time complexity. The key advantage over brute force approaches (O((n+m)log(n+m)) or O((n+m)²)) is that we can merge in a single pass without additional sorting steps.

Conditions where a variation or related pattern applies instead:

• When arrays are not sorted → Use general merge or sorting approach
• When merging more than 2 arrays → Consider heap-based approaches or iterative pairwise merging
• When dealing with streams or real-time data → Use streaming merge algorithms
• When memory is extremely constrained → Consider in-place merging with reverse pointers

The core insight that makes this pattern work: The fundamental insight is that since both arrays are sorted, we can always safely pick the smaller of the two current elements at any step. This creates a predictable merge path where we never need to "go back" to reconsider previous choices, enabling linear time complexity. The key invariant is that at any point, all elements we've already processed are in their correct relative order with respect to the remaining unprocessed elements.

This pattern is most effective when you have multiple sorted inputs that need to be combined while maintaining the sorted property, making it ideal for merge sort implementations and database query result consolidation.

3. Approach Evolution

Interview communication script:

My first instinct is to use a simple merge approach by comparing elements from both arrays one by one, similar to the merge step in merge sort. But that's O(n²) in the worst case if I'm constantly shifting elements, because for each element I might need to shift all previous elements in the result array. Let me think about how to optimize this.

I notice that if I work backwards from the end of the arrays, I can avoid shifting elements entirely. This is a classic two-pointer technique where I maintain the invariant that all elements in the result array are properly placed, and I'm always choosing the larger element to place next. By starting from the end, I don't overwrite elements that I still need to process.

Let me think about this more systematically. If I have two sorted arrays and want to merge them into one sorted array, I can use a two-pointer approach. But instead of building the result from left to right, I'll build it from right to left, which is more efficient for this specific problem where we have a third array of sufficient size.

The key insight here is that since we're merging into the first array, and the first array has enough space at the end to accommodate all elements, we can work backwards. This way, I don't overwrite elements that are yet to be processed.

Brute-force approach and why it is not ideal:

The brute force approach would be to copy all elements from the second array into the first, then sort the entire first array. This would be O((m+n) log(m+n)) time complexity, where m and n are the lengths of the two arrays. This is inefficient because:

1. We're throwing away the fact that both input arrays are already sorted
2. We're doing unnecessary sorting when we could leverage the existing order
3. The time complexity is dominated by the sorting step rather than the merging

Improved approach and the key optimization:

The improved approach uses a two-pointer technique working backwards from the end of both arrays. The key optimization is:

1. Instead of merging left-to-right (which would require shifting), we merge right-to-left
2. We use the extra space at the end of nums1 to store the merged result
3. By starting from the largest elements, we ensure we never overwrite unprocessed elements

Final approach with step-by-step reasoning:

1. Start from the end of both arrays (nums1 and nums2)
2. Compare elements at current positions in both arrays
3. Place the larger element at the end of nums1 (which has extra space)
4. Move the corresponding pointer backward
5. Continue until all elements are processed
6. Handle remaining elements in nums2 (if any) by copying them to nums1

Important invariants that must hold:

1. All elements in nums1 from index 0 to i-1 are already in their final positions
2. All elements in nums2 from index 0 to j-1 are already in their final positions
3. The current position in nums1 (k) always represents the next location to place a merged element
4. At any point, we never overwrite elements in nums1 that haven't been processed yet
5. The merged array maintains the correct sorted order throughout the process

4. Data Structure Choice

For the merge sorted arrays problem, I'll use a priority queue (min-heap) as my primary data structure.

Primary Data Structures Used

1. PriorityQueue - to maintain the smallest elements from each array in sorted order
2. ArrayList - to collect and return the final merged result

Why Each Data Structure Is Needed

The PriorityQueue is essential because:

• It maintains elements in sorted order automatically
• It provides O(log k) insertion and extraction operations where k is the number of arrays
• It allows us to efficiently pick the next smallest element across all arrays
• It handles the "merge" operation naturally by always selecting the minimum available element

The ArrayList is needed because:

• It serves as our result container that grows dynamically
• It provides O(1) amortized append operations
• It's the standard return type for this problem

Time and Space Impact

Time Complexity:

• Priority Queue operations: O(log k) per operation
• Overall: O(N log k) where N is total elements and k is number of arrays

Space Complexity:

• Priority Queue: O(k) - stores at most one element from each array
• Result ArrayList: O(N) - stores all merged elements
• Total: O(N + k)

Helper Structure

I don't need any additional helper structures beyond the standard Java collections. The PriorityQueue naturally handles the merging logic, and ArrayList provides clean result collection.

The choice of PriorityQueue over other structures like a simple array or linked list is that it gives us the optimal O(log k) time complexity for maintaining sorted order, which is crucial for achieving the desired O(N log k) overall complexity.

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-by-step execution:

1. Initialization:

   • i = m-1 = 2 (points to last element in nums1's valid data)
   • j = n-1 = 2 (points to last element in nums2)
   • k = m+n-1 = 5 (points to last position in merged array)

2. First iteration:

   • Compare nums1[2] = 3 and nums2[2] = 6
   • Since 3 < 6, place 6 at nums1[5]
   • Decrement j = 1, k = 4

3. Second iteration:

   • Compare nums1[2] = 3 and nums2[1] = 5
   • Since 3 < 5, place 5 at nums1[4]
   • Decrement j = 0, k = 3

4. Third iteration:

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

5. Fourth iteration:

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

6. Fifth iteration:

   • Since j < 0, copy remaining elements from nums1: nums1[1] = 2 at nums1[1]
   • Decrement i = 0, k = 0

7. Sixth iteration:

   • Since j < 0, copy remaining elements from nums1: nums1[0] = 1 at nums1[0]
   • Decrement i = -1, k = -1

8. Final state:

   • nums1 = [1,2,2,3,5,6] (correctly merged)

Key points in the walkthrough:

• We work backwards from the end to avoid overwriting valid elements
• When one array is exhausted, we copy remaining elements from the other array
• The invariant maintained is that nums1 always contains the correct merged elements at their final positions
• The algorithm terminates when both pointers reach negative indices

This approach ensures correctness by always placing the larger of the two current elements at the end of the array, effectively building the merged result from right to left.

6. Java Solution

public class MergeSortedArrays {
    /**
     * Merges two sorted arrays into one sorted array.
     * Uses three pointers to merge from the end to avoid overwriting unprocessed elements.
     * 
     * @param nums1 First array with enough space to hold merged result
     * @param m Number of elements in nums1 that are valid
     * @param nums2 Second array containing n elements
     * @param n Number of elements in nums2
     */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointers for nums1 (valid elements), nums2, and the position to fill in nums1
        int i = m - 1;      // Last valid element in nums1
        int j = n - 1;      // Last element in nums2
        int k = m + n - 1;  // Position to place next largest element in nums1
        
        // Merge from the end to avoid overwriting unprocessed 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--];
        }
        
        // No need to copy remaining elements from nums1 as they're already in place
    }
}

This solution uses a three-pointer technique starting from the end of both arrays to efficiently merge them in-place. It handles all edge cases including empty arrays and different array sizes. The approach ensures no overwriting occurs by processing from largest to smallest elements.

7. Complexity Analysis

Time Complexity: O(m + n)

The algorithm makes a single pass through both input arrays, visiting each element exactly once. Since we're merging two sorted arrays of sizes m and n, the total number of operations is bounded by m + n. Each comparison and copy operation takes constant time, so the overall time complexity is linear in the sum of input sizes.

Space Complexity: O(1)

The solution uses only a constant amount of extra space beyond the input arrays. We only maintain a few integer indices (i, j, k) and do not require any additional data structures like temporary arrays or hash maps. The merge is performed in-place on the first array, making it space-efficient.

Why These Bounds Are Correct

The bounds are tight because:

1. We must examine every element in both arrays at least once to produce a valid merge
2. No operations are repeated or skipped
3. The in-place merging strategy avoids any additional space allocation

Optimality

This solution is optimal for the in-place merge problem. Since we need to process all elements from both arrays and produce a merged sorted result, O(m + n) time complexity is the theoretical lower bound. The space complexity of O(1) is also optimal for in-place operations, as we cannot avoid using a constant amount of extra variables for indices and loop control.

The solution achieves the best possible trade-off between time and space complexity for this canonical problem.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty arrays: When one or both input arrays are empty, the merge should return the non-empty array or an empty result
• Single element arrays: The algorithm must handle merging arrays of size 1 correctly
• One empty array: If one array is empty, the result should be the other array unchanged

Duplicate Values and Repeated States

• Duplicate elements: The merge must preserve duplicates from both arrays
• Identical arrays: When both arrays are identical, the result should contain all elements in sorted order
• Overlapping ranges: When arrays have overlapping values, proper merging logic must maintain correct ordering

Boundary Conditions

• Array bounds: Care must be taken to avoid index out of bounds errors when one array is exhausted before the other
• Zero-length arrays: Special handling needed for arrays with zero length
• Large input sizes: The solution should handle the maximum constraints (e.g., up to 10⁴ elements)

Common Implementation Mistakes

• Incorrect index management: Not properly tracking indices for both arrays during the merge process
• Missing boundary checks: Failing to check if one array is exhausted before accessing elements from it
• Off-by-one errors: Mismanaging the loop conditions or array access indices
• Mutating input arrays: Modifying the original input arrays when they should remain unchanged (if required by problem constraints)
• Not handling null inputs: Failing to validate that input arrays are not null before processing

// Example of incorrect handling:
// if (i < m) { ... } // Should be: if (i < m && j < n) { ... }

9. Alternative Approaches

There are several alternative approaches to merging sorted arrays, each with different trade-offs:

1. Simple Concatenation + Sort The most straightforward approach is to concatenate all arrays into one large array and then sort it. This works but loses the benefit of the input being already sorted.

public int[] mergeSortedArrays(int[][] arrays) {
    // Count total elements
    int totalSize = 0;
    for (int[] arr : arrays) {
        totalSize += arr.length;
    }
    
    // Copy all elements to one array
    int[] result = new int[totalSize];
    int index = 0;
    for (int[] arr : arrays) {
        System.arraycopy(arr, 0, result, index, arr.length);
        index += arr.length;
    }
    
    // Sort the combined array
    Arrays.sort(result);
    return result;
}

Trade-offs:

• Time: O(N log N) where N is total elements
• Space: O(1) additional space (not counting output)
• Pros: Simple to implement and understand
• Cons: Loses the advantage of pre-sorted input, inefficient for large inputs

2. K-Way Merge Using Min Heap Instead of merging two arrays at a time, we can use a min-heap to keep track of the smallest elements from each array:

public int[] mergeSortedArrays(int[][] arrays) {
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    // Initialize heap with first element of each array
    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i].length > 0) {
            minHeap.offer(new int[]{arrays[i][0], i, 0});
        }
    }
    
    List<Integer> result = new ArrayList<>();
    while (!minHeap.isEmpty()) {
        int[] current = minHeap.poll();
        int value = current[0];
        int arrayIndex = current[1];
        int elementIndex = current[2];
        
        result.add(value);
        
        // Add next element from same array if exists
        if (elementIndex + 1 < arrays[arrayIndex].length) {
            minHeap.offer(new int[]{
                arrays[arrayIndex][elementIndex + 1], 
                arrayIndex, 
                elementIndex + 1
            });
        }
    }
    
    return result.stream().mapToInt(Integer::intValue).toArray();
}

Trade-offs:

• Time: O(N log K) where N is total elements, K is number of arrays
• Space: O(K) for the heap
• Pros: More efficient than simple sort approach, scales well with number of arrays
• Cons: More complex implementation, requires understanding of heap operations

3. Divide and Conquer We can recursively merge pairs of arrays until we have one merged array:

public int[] mergeSortedArrays(int[][] arrays) {
    if (arrays == null || arrays.length == 0) return new int[0];
    return mergeArraysHelper(arrays, 0, arrays.length - 1);
}

private int[] mergeArraysHelper(int[][] arrays, int start, int end) {
    if (start == end) return arrays[start];
    
    int mid = start + (end - start) / 2;
    int[] left = mergeArraysHelper(arrays, start, mid);
    int[] right = mergeArraysHelper(arrays, mid + 1, end);
    
    return mergeTwoArrays(left, right);
}

private int[] mergeTwoArrays(int[] arr1, int[] arr2) {
    int[] result = new int[arr1.length + arr2.length];
    int i = 0, j = 0, k = 0;
    
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] <= arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }
    
    while (i < arr1.length) result[k++] = arr1[i++];
    while (j < arr2.length) result[k++] = arr2[j++];
    
    return result;
}

Trade-offs:

• Time: O(N log K) where N is total elements, K is number of arrays
• Space: O(log K) for recursion stack + O(N) for output
• Pros: Clean recursive structure, good for understanding the divide approach
• Cons: Higher space complexity due to recursion stack, more complex than simple two-pointer approach

Comparison with Primary Solution: The primary approach (two-pointer merge of pairs) is generally preferred because it's:

1. More intuitive and easier to understand
2. Uses minimal additional space (just the result array)
3. Has predictable O(N) time complexity with good constants
4. Avoids the overhead of heap operations or recursion stack

The heap-based approach is better when we have many arrays and want to minimize the number of comparisons, while the divide-and-conquer approach is useful when we're dealing with very large arrays that might not fit in memory.

10. Test Cases

public class MergeSortedArrays {
    public static void main(String[] args) {
        // Test case 1: Basic merge
        int[] nums1 = {1, 2, 3, 0, 0, 0};
        int[] nums2 = {2, 5, 6};
        merge(nums1, 3, nums2, 3);
        // Expected: [1, 2, 2, 3, 5, 6]

        // Test case 2: Empty first array
        int[] nums3 = {0, 0, 0};
        int[] nums4 = {1, 2, 3};
        merge(nums3, 0, nums4, 3);
        // Expected: [1, 2, 3]

        // Test case 3: Empty second array
        int[] nums5 = {1, 2, 3};
        int[] nums6 = {};
        merge(nums5, 3, nums6, 0);
        // Expected: [1, 2, 3]

        // Test case 4: One element arrays
        int[] nums7 = {1, 0};
        int[] nums8 = {2};
        merge(nums7, 1, nums8, 1);
        // Expected: [1, 2]

        // Test case 5: Duplicate elements
        int[] nums9 = {1, 1, 2, 0, 0, 0};
        int[] nums10 = {1, 2, 3};
        merge(nums9, 3, nums10, 3);
        // Expected: [1, 1, 1, 2, 2, 3]

        // Test case 6: Negative numbers
        int[] nums11 = {-1, 0, 0, 0};
        int[] nums12 = {-2, -1, 3};
        merge(nums11, 2, nums12, 3);
        // Expected: [-2, -1, -1, 0, 3]
    }

    public static void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; // Last element in nums1's valid elements
        int j = n - 1; // Last element in nums2
        int k = m + n - 1; // Last position in merged array

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        // Copy remaining elements from nums2 if any
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

Sample Test Cases:

Basic Merge Example:

• Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
• Output: [1,2,2,3,5,6]

Edge Case - Empty Arrays:

• Input: nums1 = [0,0,0], m = 0, nums2 = [1,2,3], n = 3
• Output: [1,2,3]

Edge Case - Duplicates:

• Input: nums1 = [1,1,2,0,0,0], m = 3, nums2 = [1,2,3], n = 3
• Output: [1,1,1,2,2,3]

Boundary Case - Single Elements:

• Input: nums1 = [1,0], m = 1, nums2 = [2], n = 1
• Output: [1,2]

Boundary Case - Negative Numbers:

• Input: nums1 = [-1,0,0,0], m = 2, nums2 = [-2,-1,3], n = 3
• Output: [-2,-1,-1,0,3]

11. Final Summary

The core idea is to efficiently merge two sorted arrays by leveraging the fact that both input arrays are already sorted, allowing us to use a two-pointer technique to avoid unnecessary comparisons. This solution works because we can always safely select the smaller of the two current elements, maintaining the sorted order throughout the merge process. The approach is optimal with O(m+n) time complexity and O(1) space complexity when merging in-place, making it highly efficient for large datasets where maintaining sorted order is crucial.