Skip to main content

Two Pointer

Merge Sorted Array

Problem Description

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Examples:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10⁹ <= nums1[i], nums2[j] <= 10⁹

Follow-up: Can you come up with an algorithm that runs in O(m + n) time?

💡
Try it with yourself

Given that the problem requires us to solve it in O(m+n) time, let's begin with the first idea that comes to mind.

Brute Force Approach

When we first read the problem, the simplest approach that comes to mind is to directly combine the two arrays without worrying about the complexity. We can do this by appending all elements of the second array, nums2, to the first array, nums1, starting from the point where the valid elements in nums1 end. This is straightforward because nums1 already has extra space at the end to hold all elements of nums2. Once the elements are combined, the next step is to sort the entire nums1 array to ensure it is in the correct non-decreasing order. This method is easy to understand and implement, making it a natural first thought for solving the problem.

Example

Step 1: Copy Elements from nums2 to nums1

  • Start filling the empty slots in nums1 with elements from nums2.
  • Insert the elements of nums2 one by one into nums1 starting at index m=3.
  • After this step, nums1 becomes: [1, 2, 3, 2, 5, 6]

Step 2: Sort the Combined Array nums1

  • Next, sort the entire nums1 array, which now contains elements from both nums1 and nums2.
  • Sorting rearranges all elements in ascending order.
  • After sorting, nums1 becomes: [1, 2, 2, 3, 5, 6]

The final merged and sorted array is: [1, 2, 2, 3, 5, 6]

Steps to write code

  1. Copy the elements from nums2 to nums1: Loop through nums2 and start placing its elements at the index m in nums1.
  2. Sort nums1: Once the elements from nums2 are inserted into nums1, sort the entire array.
Code for All Languages
Brute Force code for Merge two sorted arrays in c++ 
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // Loop through each element in nums2
        for(int i = 0; i < n; i++) {
            // Place the current element of nums2 at the end of the valid elements in nums1
            nums1[m + i] = nums2[i];
        }
        
        // Sort nums1 to merge the two arrays into a single sorted array
        sort(nums1.begin(), nums1.end());
    }
};

Brute Force code for Merge two sorted arrays in Java 
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Copy elements from nums2 into the remaining positions of nums1
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }

        // Sort nums1 to merge the two arrays into a sorted order
        java.util.Arrays.sort(nums1);
    }
}

Brute Force code for Merge two sorted arrays in Python 
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        # Loop through each element in nums2
        for i in range(n):
            # Place the current element of nums2 at the end of the valid elements in nums1
            nums1[m + i] = nums2[i]
        
        # Sort nums1 to merge both arrays into a single sorted array
        nums1.sort()

Brute Force code for Merge two sorted arrays in Javascript 
/**
 * @param {number[]} nums1 - The first sorted array with extra space for nums2
 * @param {number} m - Number of valid elements in nums1
 * @param {number[]} nums2 - The second sorted array
 * @param {number} n - Number of elements in nums2
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // Loop through each element in nums2
    for (let i = 0; i < n; i++) {
        // Place the current element of nums2 at the end of the valid elements in nums1
        nums1[m + i] = nums2[i];
    }
    
    // Sort nums1 to merge both arrays into a single sorted array
    nums1.sort((a, b) => a - b);
};

Complexity Analysis of this Approach

Time Complexity: O((m+n)log⁡(m+n))

  1. Copying Elements from nums2 to nums1:
    • The loop iterates over all n elements of nums2.
    • Each element is placed into the extra space in nums1 at positions starting from index m.
    • Time Complexity of this step: O(n).
  3. Sorting the Combined Array nums1:
    • After copying, the combined array nums1 (of size m+n) is sorted.
    • Sorting an array of size k using inbuilt sorting algorithms has a time complexity of O(klog⁡k), where k=m+n.
    • Time Complexity of this step: O((m+n)log⁡(m+n)).

Overall Time Complexity

The dominant step in the algorithm is the sorting operation. Therefore, the overall time complexity is: O((m+n)log⁡(m+n))

Space Complexity: O(1)

Auxiliary Space

  • Copying Elements:
    • The algorithm directly copies elements from nums2 into nums1 without using any additional data structures.
    • No extra memory is used for this operation.
  • Sorting nums1:
    • Sorting typically requires auxiliary space for internal operations.
    • Depending on the sorting algorithm:
      • If an in-place sorting algorithm (like Timsort) is used, the auxiliary space complexity is O(1) for the in-place operations.
      • However, Timsort also uses O(k) temporary space for merging runs, where k=m+n.
    • Worst-case auxiliary space for sorting: O(m+n).

Auxiliary Space: O(m+n)

2. Total Space

  • Input Arrays:
    • The input arrays nums1 and nums2 have sizes m+n and n, respectively.
    • The total input size is O(m+n).
  • Additional Space Usage:
    • The sorting operation contributes O(m+n) auxiliary space in the worst case.

Total Space: O(m+n)

Will brute force run under given constraints

Yes, the brute force approach will run efficiently within the given constraints. The combined size of the two arrays, m+n, is at most 200.

Even though the sorting step in the brute force approach has a time complexity of O((m+n)log⁡(m+n)), this is manageable for m+n=200, as it would require approximately 1,528 operations in the worst case, which is computationally inexpensive.

Additionally, while the range of values in nums1 and nums2 is large (−10⁹ to 10⁹), this does not affect the performance of the approach since sorting and merging depend only on the number of elements, not their values.

Furthermore, with m and n constrained between 0 and 200, the number of iterations required for merging or sorting will always be relatively small.

Therefore, the brute force approach is feasible and performs efficiently under these constraints.

Optimize Approach

In the earlier approach, we combined the two arrays and sorted them, which was simple but not efficient because sorting takes O((m+n)log⁡(m+n)) time.
If you suggest this method in an interview, the interviewer might challenge you to think of a better way, especially since the problem gives us a crucial hint: both arrays are already sorted. This is an important clue that can help us solve the problem more efficiently.

A smarter approach is to use the two-pointer technique, which allows us to merge the two arrays in sorted order without needing to sort them again. Let’s break it down step by step for better understanding:

To solve the problem efficiently, it’s important to think about how to use the given extra space in nums1. Instead of trying to merge from the beginning, which might require shifting elements repeatedly, we can take advantage of the fact that nums1 has extra space at the end. The largest elements from both arrays will naturally belong at the back of the merged array.

This leads us to the key idea: start filling the array from the last position, where the extra space is, and work backward. By comparing the largest elements of nums1 and nums2, we can place the largest element in the current last position of nums1. This eliminates the need to shift elements, making the process more efficient and intuitive. It’s like filling a bucket from the bottom up—start where there’s room and work your way toward the top.

To efficiently merge the two arrays, we use two pointers to keep track of the elements we are comparing. One pointer starts at the last valid element in nums1 (just before the extra space), and the other starts at the last element in nums2. These pointers allow us to directly compare the largest remaining elements in both arrays.

Since we are filling nums1 from the back, we compare the elements at these two pointer positions and place the larger of the two at the current last position in nums1. This ensures that the largest element is placed correctly without disturbing the order of the smaller elements. After placing the larger element, we move the corresponding pointer one step backward (because we’ve processed that element) and also move the position pointer in nums1 one step back to fill the next spot.

Once we've compared and placed all the elements from both arrays in nums1, there may still be elements left in one of the arrays. If we finish processing all the elements from nums1 but still have the remaining elements in nums2, we don’t need to compare them again. This is because nums2 is already sorted, so whatever is left in nums2 must be smaller than or equal to the smallest element in nums1.

Since we're working backward from the end of nums1, we can simply copy all the remaining elements from nums2 into the beginning of nums1. There’s no need for further comparisons—this step ensures that any leftover elements in nums2 are placed in the correct positions. If there are remaining elements in nums1 (in case nums2 gets exhausted first), we don’t need to do anything because those elements are already in the correct place.

This step is efficient because it takes advantage of the fact that nums2 is sorted, and copying the remaining elements directly into nums1 completes the merge without any extra effort.

This method is not only fast but also easy to explain in an interview. It demonstrates that you can identify useful hints from the problem (like the sorted arrays) and use them to devise an optimal solution. This is exactly the kind of thinking an interviewer would appreciate!

Example

Input:

  • nums1 = [1, 2, 3, 0, 0, 0]
  • m = 3 (The number of valid elements in nums1)
  • nums2 = [2, 5, 6]
  • n = 3 (The number of elements in nums2)

The goal is to merge nums2 into nums1 and keep the array sorted. The last 0's in nums1 are placeholders for nums2 elements.

Step-by-Step Execution

  1. Initial Setup:
    • lastInNums1 = m - 1 = 2: Pointer for the last valid element in nums1, which is 3.
    • lastInNums2 = n - 1 = 2: Pointer for the last element in nums2, which is 6.
    • mergePos = m + n - 1 = 5: Pointer for the last position in nums1, which is the last 0.
  3. Merge Process (Start from the End): We begin comparing and placing elements starting from the last positions of both arrays.
  • First iteration:
    • Compare nums1[lastInNums1] = 3 and nums2[lastInNums2] = 6.
    • Since 6 > 3, place 6 at nums1[mergePos].
    • Update pointers:
      • nums1[5] = 6
      • lastInNums2-- → lastInNums2 = 1
      • mergePos-- → mergePos = 4
  • Second iteration:
    • Compare nums1[lastInNums1] = 3 and nums2[lastInNums2] = 5.
    • Since 5 > 3, place 5 at nums1[mergePos].
    • Update pointers:
      • nums1[4] = 5
      • lastInNums2-- → lastInNums2 = 0
      • mergePos-- → mergePos = 3
  • Third iteration:
    • Compare nums1[lastInNums1] = 3 and nums2[lastInNums2] = 2.
    • Since 3 > 2, place 3 at nums1[mergePos].
    • Update pointers:
      • nums1[3] = 3
      • lastInNums1-- → lastInNums1 = 1
      • mergePos-- → mergePos = 2
  • Fourth iteration:
    • Compare nums1[lastInNums1] = 2 and nums2[lastInNums2] = 2.
    • Since both are equal, either one can be placed at mergePos. Here, 2 from nums2 is placed.
    • Update pointers:
      • nums1[2] = 2
      • lastInNums2-- → lastInNums2 = -1 (all elements in nums2 are processed)
      • mergePos-- → mergePos = 1
  1. Check for Remaining Elements in nums2: After the above loop, if any elements are still left in nums2, they need to be copied into nums1. However, in this example, all elements in nums2 are already processed.
  2. Final State of nums1:
    • At the end of the process, nums1 is fully merged and sorted: nums1 = [1, 2, 2, 3, 5, 6]

Steps to write code

Pointer Initialization:

  • Initialize the pointers:
    • lastInNums1 = m - 1
    • lastInNums2 = n - 1
    • mergePos = m + n - 1

Main Merge Loop:

  • While both pointers lastInNums1 and lastInNums2 are valid:
    • Compare the elements nums1[lastInNums1] and nums2[lastInNums2].
    • Place the larger element at nums1[mergePos].
    • Decrement the respective pointers and the merge position.

Handle Remaining Elements in nums2:

  • If lastInNums2 is still valid, copy the remaining elements of nums2 into nums1.
Code for All Languages
Optimize code for Merge two sorted arrays in c++ 
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // Pointer for the last valid element in nums1
        int lastInNums1 = m - 1;

        // Pointer for the last element in nums2
        int lastInNums2 = n - 1;

        // Pointer for the last position in nums1
        int mergePos = m + n - 1;

        // Merge nums1 and nums2 starting from the end
        while (lastInNums1 >= 0 && lastInNums2 >= 0) {
            // Compare the elements from nums1 and nums2
            // Place the larger element at the current merge position
            if (nums1[lastInNums1] > nums2[lastInNums2]) {
                nums1[mergePos] = nums1[lastInNums1];
                lastInNums1--;
            } else {
                nums1[mergePos] = nums2[lastInNums2];
                lastInNums2--;
            }
            mergePos--;
        }

        // If any elements are left in nums2, copy them into nums1
        while (lastInNums2 >= 0) {
            nums1[mergePos] = nums2[lastInNums2];
            lastInNums2--;
            mergePos--;
        }
    }
};

Optimize code for Merge two sorted arrays in Java 
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointer for the last valid element in nums1
        int lastInNums1 = m - 1;

        // Pointer for the last element in nums2
        int lastInNums2 = n - 1;

        // Pointer for the last position in nums1
        int mergePos = m + n - 1;

        // Merge nums1 and nums2 starting from the end
        while (lastInNums1 >= 0 && lastInNums2 >= 0) {
            // Compare the elements from nums1 and nums2
            // Place the larger element at the current merge position
            if (nums1[lastInNums1] > nums2[lastInNums2]) {
                nums1[mergePos] = nums1[lastInNums1];
                lastInNums1--;
            } else {
                nums1[mergePos] = nums2[lastInNums2];
                lastInNums2--;
            }
            mergePos--;
        }

        // If any elements are left in nums2, copy them into nums1
        while (lastInNums2 >= 0) {
            nums1[mergePos] = nums2[lastInNums2];
            lastInNums2--;
            mergePos--;
        }
    }
}

Optimize code for Merge two sorted arrays in Python 
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: None Do not return anything, modify nums1 in-place instead.
        """
        # Pointer for the last valid element in nums1
        last_in_nums1 = m - 1

        # Pointer for the last element in nums2
        last_in_nums2 = n - 1

        # Pointer for the last position in nums1
        merge_pos = m + n - 1

        # Merge nums1 and nums2 starting from the end
        while last_in_nums1 >= 0 and last_in_nums2 >= 0:
            # Compare the elements from nums1 and nums2
            # Place the larger element at the current merge position
            if nums1[last_in_nums1] > nums2[last_in_nums2]:
                nums1[merge_pos] = nums1[last_in_nums1]
                last_in_nums1 -= 1
            else:
                nums1[merge_pos] = nums2[last_in_nums2]
                last_in_nums2 -= 1
            merge_pos -= 1

        # If any elements are left in nums2, copy them into nums1
        while last_in_nums2 >= 0:
            nums1[merge_pos] = nums2[last_in_nums2]
            last_in_nums2 -= 1
            merge_pos -= 1

Optimize code for Merge two sorted arrays in Javascript 
/**
 * @param {number[]} nums1 - First sorted array with extra space
 * @param {number} m - Number of valid elements in nums1
 * @param {number[]} nums2 - Second sorted array
 * @param {number} n - Number of elements in nums2
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    // Pointer for the last valid element in nums1
    let lastInNums1 = m - 1;

    // Pointer for the last element in nums2
    let lastInNums2 = n - 1;

    // Pointer for the last position in nums1
    let mergePos = m + n - 1;

    // Merge nums1 and nums2 starting from the end
    while (lastInNums1 >= 0 && lastInNums2 >= 0) {
        // Compare the elements from nums1 and nums2
        // Place the larger element at the current merge position
        if (nums1[lastInNums1] > nums2[lastInNums2]) {
            nums1[mergePos] = nums1[lastInNums1];
            lastInNums1--;
        } else {
            nums1[mergePos] = nums2[lastInNums2];
            lastInNums2--;
        }
        mergePos--;
    }

    // If any elements are left in nums2, copy them into nums1
    while (lastInNums2 >= 0) {
        nums1[mergePos] = nums2[lastInNums2];
        lastInNums2--;
        mergePos--;
    }
};

Complexity Analysis of this Approach

Time Complexity: O(m+n)

  1. Merging Elements:
    • The algorithm compares elements from the end of both arrays (nums1 and nums2) and places the larger element in the correct position in nums1.
    • The process continues until one of the arrays is completely traversed.
    • At most m+n iterations occur (where m and n are the lengths of valid elements in nums1 and nums2, respectively).
    • Time Complexity for this step: O(m+n).
  3. Copying Remaining Elements:
    • After the comparison loop, if nums2 still has elements left, they are copied into nums1.
    • This involves iterating over the remaining elements of nums2.
    • In the worst case, all n elements of nums2 need to be copied.
    • Time Complexity for this step: O(n).

Overall Time Complexity

The merging step and the copying step are the main contributors to the time complexity. Both steps together take at most O(m+n). Therefore, the overall time complexity is: O(m+n)

Space Complexity: O(1)

Auxiliary Space:

  • Auxiliary space refers to the extra memory used by the algorithm that is not part of the input or output.
  • In this algorithm:
    • Only three pointers (lastInNums1, lastInNums2, and mergePos) are used for tracking indices.
    • These pointers require constant space, O(1).

Auxiliary Space: O(1)

2. Total Space:

  • Total space includes both the input/output space and any auxiliary space used by the algorithm.
  • The input consists of nums1 and nums2, where:
    • nums1 has a size of m+n.
    • nums2 has a size of n.
  • The merging is performed directly in nums1 without requiring additional space for the result.

Total Space: O(m+n)

Key Takeaways

Having learned the optimal algorithm for "Merge Sorted Array", you can now apply this algorithm to different problems. Additionally, you can attempt to solve the following problems by utilizing this approach.

Merge Strings Alternately

You are given two strings word1 and word2. Merge the strings by adding letters in alternating order, starting with word1. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return the merged string.

Largest Merge Of Two Strings

You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:

If word1 is non-empty, append the first character in word1 to merge and delete it from word1.

For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".

If word2 is non-empty, append the first character in word2 to merge and delete it from word2.

For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".
Return the lexicographically largest merge you can construct.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b.

For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Real World Example

A real-world example where merging two sorted arrays would be useful is in the context of merging two sorted lists of customer orders for an e-commerce platform.

Imagine you have two systems or databases where customer orders are stored in sorted order (e.g., sorted by the order date). One system tracks orders from Region A, and the other tracks orders from Region B. At the end of the day, you want to combine these two sorted lists into a single list, also sorted by the order date, to get a comprehensive view of all customer orders across both regions.