3. Merge two Sorted Arrays Without Extra Space

Source: Merge two Sorted Arrays Without Extra Space

Problem Statement

Input : nums1 = [-5, -2, 4, 5, 0, 0, 0], nums2 = [-3, 1, 8] Output : [-5, -3, -2, 1, 4, 5, 8] Explanation : The merged array is: [-5, -3, -2, 1, 4, 5, 8], where [-5, -2, 4, 5] are from nums1 and [-3, 1, 8] are from nums2

Approach 1: Approach

We are given two sorted arrays nums1 and nums2 and nums1 has enough space at the end (filled with zeros) to accommodate all elements from nums2. Now, if we try to insert elements from nums2 into nums1 from the beginning, we would need to shift elements in nums1 every time to make room which becomes time consuming and inefficient.

Since both arrays are sorted in non-decreasing order, the largest elements will be at the end of each array. If we start comparing elements from the back of both arrays and place the largest one at the end of nums1, we won't need to shift anything.

To efficiently insert elements at the end, we will use three pointers.

• Initialize three pointers: One points at the last valid index (excluding zeros) of nums1, one points at the last valid index of nums2 andd the last pointer points to last index of nums1.

• Compare the elements pointed by the first two pointers and whichever is larger, place it at the third pointer's index.

• Move the respective pointer one step back and also move the third pointer one step back.

• If there are any remaining elements in nums2, then copy them in nums1. If any elements remain in nums1, they’re already in place

• The result is a fully merged and sorted array stored in nums1 itself.

• Complexity: Time Complexity: O(N+M), we traverse both the arrays exactly once.

  Space Complexity: O(1), constant extra space is used to store pointers.

Solutions

C++

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

class Solution {
public:
    // Merges nums2 into nums1 in-place in sorted order.
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        // i points to last valid element in nums1
        int i = m - 1;

        // j points to last element in nums2
        int j = n - 1;

        // k is the last index of nums1 (including 0 placeholders)
        int k = m + n - 1;

        // Fil""l nums1 from the end by comparing nums1[i] and nums2[j]
        while (i >= 0 && j >= 0) {
            // Place larger of the two at nums1[k]
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        // If nums2 has remaining elements, copy them
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }

        // No need to copy remaining nums1 elements, as they are already in place
    }
};

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

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

    // Print merged array
    for (int num : nums1) cout << num << " ";
    return 0;
}

Java

class Solution {
    // Merges nums2 into nums1 in-place in sorted order.
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // i: last valid index in nums1
        int i = m - 1;

        // j: last index in nums2
        int j = n - 1;

        // k: last index in nums1 including extra 0s
        int k = m + n - 1;

        // Fill nums1 from the back
        while (i >= 0 && j >= 0) {
            // Place larger element from end of nums1 or nums2
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

        // If nums2 has leftovers, copy them to nums1
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }

        // Remaining nums1 elements are already in correct position
    }
}

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

        new Solution().merge(nums1, m, nums2, n);

        // Print the merged array
        for (int num : nums1) {
            System.out.print(num + " ");
        }
    }
}

Python

class Solution:
    # Merges nums2 into nums1 in-place in sorted order.
    def merge(self, nums1, m, nums2, n):
        # i: last valid element index in nums1
        i = m - 1

        # j: last index of nums2
        j = n - 1

        # k: end of nums1 array
        k = m + n - 1

        # Merge from the back to avoid overwriting
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
j -= 1
            k -= 1

        # If any elements remain in nums2, copy them
        while j >= 0:
            nums1[k] = nums2[j]
            k -= 1
            j -= 1

        # No need to copy nums1 leftovers — already in place

# Example usage
nums1 = [1, 3, 5, 0, 0, 0]
nums2 = [2, 4, 6]
m, n = 3, 3
Solution().merge(nums1, m, nums2, n)
print(nums1)

JavaScript

class Solution {
    // Merges nums2 into nums1 in-place in sorted order.
    merge(nums1, m, nums2, n) {
        // i: last valid index in nums1
        let i = m - 1;

        // j: last index in nums2
        let j = n - 1;

        // k: final index in nums1 (includes 0s)
        let k = m + n - 1;

        // Start merging from end to avoid overwriting
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }

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

        // Remaining nums1 elements are already at correct place
    }
}

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

new Solution().merge(nums1, m, nums2, n);
console.log(nums1);

Reference

• TakeUForward