Merge two sorted arrays without extra space

Intuition

The naive idea is to use the sorted property of array. As the given arrays are sorted, use 2 pointer approach to get a third array by simply comparing the elements at both the pointers, the third array contains all the elements from the given two arrays in the sorted order. Now, from the sorted third array, again fill back the given two arrays.

Approach

Declare a third array, arr3[] of size n+m, and two pointers i.e. left and right, one pointing to the first index of arr1[] and the other pointing to the first index of arr2[].

Now, if arr1[left] is less than arr2[right], insert the element arr1[left] into the third array and increase the left pointer by 1.

If arr2[right] less than arr1[left], insert the element arr2[right] into the third array and increase the right pointer by 1.

If arr1[left] is equal to arr2[right], insert any of the elements and increase that particular pointer by 1.

If one of the pointers reaches the end, then only move the other pointer and insert the rest of the elements of that particular array into the third array i.e. arr3[].

If we move the pointer like the above, will get the third array in the sorted order. Now, from sorted array arr3[], copy all the elements back to arr1[].

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to merge two sorted arrays nums1 and nums2
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        
        // Declare a 3rd array and 2 pointers:
        vector<int> merged(m + n);
        int left = 0;
        int right = 0;
        int index = 0;

        /* Insert elements from nums1 and nums2 into
        merged array using left and right pointers*/
        while (left < m && right < n) {
            if (nums1[left] <= nums2[right]) {
                merged[index++] = nums1[left++];
            } else {
                merged[index++] = nums2[right++];
            }
        }

        // If right pointer reaches the end of nums2:
        while (left < m) {
            merged[index++] = nums1[left++];
        }

        // If left pointer reaches the end of nums1:
        while (right < n) {
            merged[index++] = nums2[right++];
        }

        /* Copy elements from merged array
        array back to nums1 and nums2*/
        for (int i = 0; i < m + n; i++) {
            nums1[i] = merged[i];
        }
    }
};

int main() {
    
    vector<int> nums1 = {-5, -2, 4, 5, 0, 0, 0};
    vector<int> nums2 = {-3, 1, 8};
    int m = 4, n = 3;

    // Create an instance of the Solution class
    Solution sol;

    sol.merge(nums1, m, nums2, n);

    // Output the merged arrays
    cout << "The merged arrays is:\n";
    cout << "nums1[] = ";
    for (int i = 0; i < m; i++) {
        cout << nums1[i] << " ";
    }
  
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to merge two sorted arrays nums1 and nums2
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        // Declare a 3rd array and 2 pointers:
        int[] merged = new int[m + n];
        int left = 0;
        int right = 0;
        int index = 0;

        /* Insert elements from nums1 and nums2 into
        merged array using left and right pointers */
        while (left < m && right < n) {
            if (nums1[left] <= nums2[right]) {
                merged[index++] = nums1[left++];
            } else {
                merged[index++] = nums2[right++];
            }
        }

        // If right pointer reaches the end of nums2:
        while (left < m) {
            merged[index++] = nums1[left++];
        }

        // If left pointer reaches the end of nums1:
        while (right < n) {
            merged[index++] = nums2[right++];
        }

        /* Copy elements from merged array
        array back to nums1 */
        for (int i = 0; i < m + n; i++) {
            nums1[i] = merged[i];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {-5, -2, 4, 5, 0, 0, 0};
        int[] nums2 = {-3, 1, 8};
        int m = 4, n = 3;

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Merge nums1 and nums2
        sol.merge(nums1, m, nums2, n);

        // Output the merged arrays
        System.out.println("The merged arrays is:");
        System.out.print("nums1[] = ");
        for (int i = 0; i < m; i++) {
            System.out.print(nums1[i] + " ");
        }
    
    }
}
from typing import List

class Solution:
    # Function to merge two sorted arrays nums1 and nums2
   def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # Declare a 3rd array and 2 pointers:
        merged = [0] * (m + n)
        left = 0
        right = 0
        index = 0

        """ Insert elements from nums1 and nums2 into
        merged array using left and right pointers """
        while left < m and right < n:
            if nums1[left] <= nums2[right]:
                merged[index] = nums1[left]
                left += 1
            else:
                merged[index] = nums2[right]
                right += 1
            index += 1

        # If right pointer reaches the end of nums2:
        while left < m:
            merged[index] = nums1[left]
            left += 1
            index += 1

        # If left pointer reaches the end of nums1:
        while right < n:
            merged[index] = nums2[right]
            right += 1
            index += 1

        """ Copy elements from merged array
        array back to nums1 """
        for i in range(m + n):
            nums1[i] = merged[i]
            

if __name__ == "__main__":
    nums1 = [-5, -2, 4, 5, 0, 0, 0]
    nums2 = [-3, 1, 8]
    m = 4
    n = 3

    # Create an instance of the Solution class
    sol = Solution()

    sol.merge(nums1, m, nums2, n)

    # Output the merged arrays
    print("The merged arrays is:")
    print("nums1[] =", nums1)
 
class Solution {
    // Function to merge two sorted arrays nums1 and nums2
    merge(nums1, m, nums2, n) {
        
        // Declare a 3rd array and 2 pointers:
        let merged = new Array(m + n);
        let left = 0;
        let right = 0;
        let index = 0;

        /* Insert elements from nums1 and nums2 into
        merged array using left and right pointers */
        while (left < m && right < n) {
            if (nums1[left] <= nums2[right]) {
                merged[index++] = nums1[left++];
            } else {
                merged[index++] = nums2[right++];
            }
        }

        // If right pointer reaches the end of nums2:
        while (left < m) {
            merged[index++] = nums1[left++];
        }

        // If left pointer reaches the end of nums1:
        while (right < n) {
            merged[index++] = nums2[right++];
        }

        /* Copy elements from merged array
        array back to nums1 and nums2 */
        for (let i = 0; i < m + n; i++) {
            nums1[i] = merged[i];
        }
    }
}

// Main function to test the solution
let nums1 = [-5, -2, 4, 5, 0, 0, 0];
let nums2 = [-3, 1, 8];
let m = 4;
let n = 3;

// Create an instance of the Solution class
let sol = new Solution();

sol.merge(nums1, m, nums2, n);

// Output the merged arrays
console.log("The merged arrays is:");
console.log("nums1[] =", nums1);

Complexity Analysis

Time Complexity: O(N+M) + O(N+M), where N and M are the sizes of the given arrays. O(N+M) is for copying the elements from nums1[] and nums2[] to the third array. And another O(N+M) is for filling back nums1[]. Space Complexity: O(N+M) for using an extra array of size N+M.

Intuition

A better idea is to use two-pointers approach to solve this problem without using extra space. Use the fact that the given arrays are sorted, so there are total m+n elements that needs to be merged, will first store the first m smaller elements in nums1[] from index 0 to m-1 and the rest in nums2[]. Then sort the two arrays separately to ensure that both the arrays are in non-decreasing order and finally, put the elements of nums2[] in nums1[] from index m to m+n-1 (last index of nums1). This process will ensure that all the elements are stored in nums1[] in non-decreasing order.

Approach

Declare two pointers i.e. left and right. The left pointer will point to m-1(Basically the maximum element of the array). The right pointer will point to the first index of the arr2[](Basically the minimum element of the array).

Now, the left pointer will move toward index 0 and the right pointer will move towards the index m-1. While moving the two pointers, if arr1[left] is greater than arr2[right], then we will swap the elements and move the pointers to the next positions.

If arr1[left] less than or equal to arr2[right], we will stop moving the pointers as arr1[] and arr2[] are containing correct elements.

Now, arr1[] will contain all smaller elements and arr2[] will contain all bigger elements. Finally, we will sort the two arrays and put the elements of arr2[] back to arr1[] from index m to m+n-1.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to merge two sorted arrays nums1 and nums2
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        // Pointer for nums1 (end of valid elements)
        int left = m - 1;  
        
        // Pointer for nums2 (beginning of valid elements)
        int right = 0;    

        /* Swap the elements until nums1[left]
        is smaller than nums2[right]*/
        while (left >= 0 && right < n) {
            
            if (nums1[left] > nums2[right]) {
                swap(nums1[left], nums2[right]);
                left--, right++;
            }
            //break out of loop if nums1[left] > nums2[right] 
            else 
               break;
        }

        // Sort nums1 from index 0 to m-1
        sort(nums1.begin() + 0, nums1.begin() + m);
        
        //Sort nums2 from start to end
        sort(nums2.begin(), nums2.end());

        // Put the elements of nums2 in nums1
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }
};

int main() {
 
    vector<int> nums1 = {-5, -2, 4, 5,0,0,0};
    vector<int> nums2 = {-3, 1, 8};
    int m = 4, n = 3; 

    // Create an instance of the Solution class
    Solution sol;

    sol.merge(nums1, m, nums2, n);

    // Output the merged arrays
    cout << "The merged arrays are:\n";
    cout << "nums1[] = ";
    for (int i = 0; i < nums1.size( ); i++) {
        cout << nums1[i] << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to merge two sorted arrays nums1 and nums2
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointer for nums1 (end of valid elements)
        int left = m - 1;
        
        // Pointer for nums2 (beginning of valid elements)
        int right = 0;
        
        /* Swap the elements until nums1[left]
        is smaller than nums2[right]*/
        while (left >= 0 && right < n) {
            if (nums1[left] > nums2[right]) {
                int temp = nums1[left];
                nums1[left] = nums2[right];
                nums2[right] = temp;
                left--;
                right++;
            } 
            //break out of loop if nums1[left] > nums2[right] 
            else break;
        }
        
        // Sort nums1 from index 0 to m-1
        Arrays.sort(nums1, 0, m);
        
        // Sort nums2 from start to end
        Arrays.sort(nums2);
        
        // Put the elements of nums2 in nums1
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }
    
    public static void main(String[] args) {
        int[] nums1 = {-5, -2, 4, 5, 0, 0, 0};
        int[] nums2 = {-3, 1, 8};
        int m = 4, n = 3;

        // Create an instance of the Solution class
        Solution sol = new Solution();

        sol.merge(nums1, m, nums2, n);

        // Output the merged arrays
        System.out.println("The merged arrays are:");
        System.out.print("nums1[] = ");
        for (int num : nums1) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    # Function to merge two sorted arrays nums1 and nums2
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # Pointer for nums1 (end of valid elements)
        left = m - 1
        
        # Pointer for nums2 (beginning of valid elements)
        right = 0
        
        """ Swap the elements until nums1[left]
        is smaller than nums2[right]"""
        while left >= 0 and right < n:
            if nums1[left] > nums2[right]:
                nums1[left], nums2[right] = nums2[right], nums1[left]
                left -= 1
                right += 1
            #break out of loop if nums1[left] > nums2[right]    
            else:
                break
        
        # Sort nums1 from index 0 to m-1
        nums1[:m] = sorted(nums1[:m])
        
        # Sort nums2 from start to end
        nums2.sort()
        
        # Put the elements of nums2 in nums1
        for i in range(m, m + n):
            nums1[i] = nums2[i - m]
    
    # Example usage
    def main(self):
        nums1 = [-5, -2, 4, 5, 0, 0, 0]
        nums2 = [-3, 1, 8]
        m, n = 4, 3
        
        # Create an instance of the Solution class
        sol = Solution()
        
        sol.merge(nums1, m, nums2, n)
        
        # Output the merged arrays
        print("The merged arrays are:")
        print("nums1[] = ", end="")
        print(nums1)
    
# Run main function when the script is executed directly
if __name__ == "__main__":
    Solution().main()
class Solution {
    // Function to merge two sorted arrays nums1 and nums2
    merge(nums1, m, nums2, n) {
        // Pointer for nums1 (end of valid elements)
        let left = m - 1;
        
        // Pointer for nums2 (beginning of valid elements)
        let right = 0;
        
        /* Swap the elements until nums1[left]
        is smaller than nums2[right]*/
        while (left >= 0 && right < n) {
            if (nums1[left] > nums2[right]) {
                [nums1[left], nums2[right]] = [nums2[right], nums1[left]];
                left--;
                right++;
            } else {
                break;
            }
        }
        
        // Sort nums1 from index 0 to m-1
        let sortedSlice = nums1.slice(0, m).sort((a, b) => a - b);

        // Replace the sorted segment back into the original array
        nums1.splice(0, sortedSlice.length, ...sortedSlice);
         
        // Sort nums2 from start to end
        nums2.sort((a, b) => a - b);
        
        // Put the elements of nums2 in nums1
        for (let i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }
}

// Example usage
let nums1 = [-5, -2, 4, 5, 0, 0, 0];
let nums2 = [-3, 1, 8];
let m = 4, n = 3;

// Create an instance of the Solution class
let sol = new Solution();

sol.merge(nums1, m, nums2, n);

// Output the merged arrays
console.log("The merged arrays are:");
console.log("nums1[] = " + nums1.join(" "));

Complexity Analysis

Time Complexity: O(min(N, M)) + O(NxlogN) + O(MxlogM), where N and M are the sizes of the given arrays. O(min(N, M)) is for swapping the array elements. And O(NxlogN) and O(MxlogM) are for sorting the two arrays. Space Complexity: O(1) as no additional space is used apart from the input array.

Intuition

Use two-pointer approach to merge two arrays in-place for the most optimized solution. Assume the two arrays as a single continuous array and initially, as the ask is to merge both the arrays in one array eventually, will place the left pointer at the first index and the right pointer at the (left+gap) index of that continuous array, where gap is Initial gap = ceil((size of arr1[] + size of arr2[]) / 2). Now will compare elements at both the pointers and if arr[left] is greater than arr[right], will swap as we want the merged array in non-decreasing order. After each iteration update the gap value. It will ensure to merge the two arrays without using extra space.

Approach

Assume the two arrays as a single array and calculate the gap value i.e. ceil((size of arr1[] + size of arr2[]) / 2).

Now, until the gap value becomes 0, place two pointers in their correct position like the left pointer at index 0 and the right pointer at index (left+gap).

Again, iterate until the right pointer reaches the end i.e. (n+m). Inside the loop, check if the left pointer is inside arr1[] and the right pointer is in arr2[]. Then compare arr1[left] and arr2[right-n] and swap them if arr1[left] is greater than arr2[right-n].

If both the pointers are in arr2[], then compare arr1[left-n] and arr2[right-n] and swap them if arr1[left-n] is greater than arr2[right-n].

If both the pointers are in arr1[], then compare arr1[left] and arr2[right] and swap them if arr1[left] is greater than arr2[right].

After the right pointer reaches the end, we will decrease the value of the gap and it will become ceil(current gap / 2).

Finally, after performing all the operations, copy the elements of arr2 to arr1 and will get the merged sorted array.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to merge two sorted arrays nums1 and nums2
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int len = n + m;
        int gap = (len / 2) + (len % 2);

        while (gap > 0) {
            int left = 0;
            int right = left + gap;
            while (right < len) {
                // When left in nums1[] and right in nums2[]
                if (left < m && right >= m) {
                    swapIfGreater(nums1, nums2, left, right - m);
                }
                // When both pointers in nums2[]
                else if (left >= m) {
                    swapIfGreater(nums2, nums2, left - m, right - m);
                }
                // When both pointers in nums1[]
                else {
                    swapIfGreater(nums1, nums1, left, right);
                }
                //Increment the pointers by 1 each
                left++, right++;
            }
            //If gap is equal break out of the loop
            if (gap == 1) break;
            gap = (gap / 2) + (gap % 2);
        }

        // Copy elements of nums2 into nums1
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }

private:
    // Utility function to swap elements if needed
    void swapIfGreater(vector<int>& arr1, vector<int>& arr2, int idx1, int idx2) {
        if (arr1[idx1] > arr2[idx2]) {
            swap(arr1[idx1], arr2[idx2]);
        }
    }
};

int main() {
    vector<int> nums1 = {-5, -2, 4, 5, 0, 0, 0};
    vector<int> nums2 = {-3, 1, 8};
    int m = 4, n = 3;

    // Create an instance of the Solution class
    Solution sol;

    sol.merge(nums1, m, nums2, n);

    // Output the merged arrays
    cout << "The merged array is:\n";
    cout << "nums1[] = ";
    for (int i = 0; i < nums1.size(); i++) {
        cout << nums1[i] << " ";
    }
    cout << endl;

    return 0;
}
import java.util.*;

class Solution {
    // Function to merge two sorted arrays nums1 and nums2
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
        int len = n + m;
        int gap = (len / 2) + (len % 2);

        while (gap > 0) {
            int left = 0;
            int right = left + gap;
            while (right < len) {
                
                // When left in nums1[] and right in nums2[]
                if (left < m && right >= m) {
                    swapIfGreater(nums1, nums2, left, right - m);
                }
                // When both pointers in nums2[]
                else if (left >= m) {
                    swapIfGreater(nums2, nums2, left - m, right - m);
                }
                // When both pointers in nums1[]
                else {
                    swapIfGreater(nums1, nums1, left, right);
                }
                // Increment the pointers by 1 each
                left++;
                right++;
            }
            // If gap is equal, break out of the loop
            if (gap == 1)
                break;
            gap = (gap / 2) + (gap % 2);
        }

        // Copy elements of nums2 into nums1
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }

    // Utility function to swap elements if needed
    private void swapIfGreater(int[] arr1, int[] arr2, int idx1, int idx2) {
        if (arr1[idx1] > arr2[idx2]) {
            
            int temp = arr1[idx1];
            arr1[idx1] = arr2[idx2];
            arr2[idx2] = temp;
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {-5, -2, 4, 5, 0, 0, 0};
        int[] nums2 = {-3, 1, 8};
        int m = 4, n = 3;

        // Create an instance of the Solution class
        Solution sol = new Solution();

        sol.merge(nums1, m, nums2, n);

        // Output the merged arrays
        System.out.println("The merged array is:");
        System.out.print("nums1[] = ");
        for (int num : nums1) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
}
from typing import List

class Solution:
    # Function to merge two sorted arrays nums1 and nums2
    def merge(self, nums1, m, nums2, n):
        len = n + m
        gap = (len // 2) + (len % 2)

        while gap > 0:
            left = 0
            right = left + gap
            while right < len:
                
                # When left in nums1[] and right in nums2[]
                if left < m and right >= m:
                    self.swapIfGreater(nums1, nums2, left, right - m)
                # When both pointers in nums2[]
                elif left >= m:
                    self.swapIfGreater(nums2, nums2, left - m, right - m)
                # When both pointers in nums1[]
                else:
                    self.swapIfGreater(nums1, nums1, left, right)
                    
                # Increment the pointers by 1 each
                left += 1
                right += 1
                
            # If gap is equal, break out of the loop
            if gap == 1:
                break
            gap = (gap // 2) + (gap % 2)

        # Copy elements of nums2 into nums1
        for i in range(m, m + n):
            nums1[i] = nums2[i - m]

    # Utility function to swap elements if needed
    def swapIfGreater(self, arr1, arr2, idx1, idx2):
        if arr1[idx1] > arr2[idx2]:
            arr1[idx1], arr2[idx2] = arr2[idx2], arr1[idx1]

if __name__ == "__main__":
    nums1 = [-5, -2, 4, 5, 0, 0, 0]
    nums2 = [-3, 1, 8]
    m, n = 4, 3

    # Create an instance of the Solution class
    sol = Solution()

    sol.merge(nums1, m, nums2, n)

    # Output the merged arrays
    print("The merged array is:")
    print("nums1[] =", nums1)
class Solution {
    // Function to merge two sorted arrays nums1 and nums2
    merge(nums1, m, nums2, n) {
        let len = n + m;
        let gap = Math.ceil(len / 2);

        while (gap > 0) {
            let left = 0;
            let right = left + gap;
            while (right < len) {
                // When left in nums1[] and right in nums2[]
                if (left < m && right >= m) {
                    this.swapIfGreater(nums1, nums2, left, right - m);
                }
                // When both pointers in nums2[]
                else if (left >= m) {
                    this.swapIfGreater(nums2, nums2, left - m, right - m);
                }
                // When both pointers in nums1[]
                else {
                    this.swapIfGreater(nums1, nums1, left, right);
                }
                // Increment the pointers by 1 each
                left++;
                right++;
            }
            // If gap is equal, break out of the loop
            if (gap === 1) break;
            gap = Math.ceil(gap / 2);
        }

        // Copy elements of nums2 into nums1
        for (let i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
    }

    // Utility function to swap elements if needed
    swapIfGreater(arr1, arr2, idx1, idx2) {
        if (arr1[idx1] > arr2[idx2]) {
            [arr1[idx1], arr2[idx2]] = [arr2[idx2], arr1[idx1]];
        }
    }
}

// Example usage
let nums1 = [-5, -2, 4, 5, 0, 0, 0];
let nums2 = [-3, 1, 8];
let m = 4, n = 3;

// Create an instance of the Solution class
let sol = new Solution();

sol.merge(nums1, m, nums2, n);

// Output the merged arrays
console.log("The merged array is:");
console.log("nums1[] = " + nums1.join(" "));

Complexity Analysis

Time Complexity: O((N+M)xlog(N+M)), where N and M are the sizes of the given arrays. The gap is ranging from N+M to 1 and every time the gap gets divided by 2. So, the time complexity of the outer loop will be O(log(N+M)). Now, for each value of the gap, the inner loop can at most run for (N+M) times. So, the time complexity of the inner loop will be O(N+M). So, the overall time complexity will be O((N+M)xlog(N+M)). Space Complexity: O(1) as no additional space is used apart from the input array.

Problem List

Merge two sorted arrays without extra space

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts