algoadvance

Leetcode 88. Merge Sorted Array

Problem Statement

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.

Clarifying Questions

1. Are nums1 and nums2 only holding non-negative integers?
   • No, the arrays can contain any integer values.
2. Should the merged result be stored back in nums1 without using additional space?
   • Yes, the problem constraints require in-place merging without additional significant space beyond variables for indices.
3. Can nums1 or nums2 be empty?
   • Yes, it’s possible for either m or n to be 0, and this should be handled accordingly.

Strategy

To merge nums1 and nums2 in-place, we’ll use a three-pointer approach:

1. Pointers:
   • i initially points to m - 1 in nums1.
   • j initially points to n - 1 in nums2.
   • k will point to m + n - 1 to fill the nums1 from the back.
2. Steps:
   • Compare elements from the back of nums1 and nums2.
   • Place the larger element at the back position (k) in nums1.
   • Move the respective pointers (i, j, k) accordingly.
   • Continue this process until one of the arrays is fully traversed.
   • If elements in nums2 remain, they need to be copied over to the beginning of nums1.

Time Complexity

• Time Complexity: ( O(m + n) ) – Each element from both arrays is processed once.
• Space Complexity: ( O(1) ) – Merging is done in-place without extra storage apart from variables.

Code

#include <vector>
using namespace std;

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1; // Pointer for the end of the added elements in nums1
    int j = n - 1; // Pointer for the end of nums2
    int k = m + n - 1; // Pointer for the end of nums1
    
    // Merge in reverse order
    while (i >= 0 && j >= 0) {
        if (nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
    
    // If there are remaining elements in nums2, copy them
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
    
    // No need to do anything for remaining elements in nums1 since they are already in place
}

Explanation

• Initialization: Start pointers i, j, and k at the end of the respective segments.
• Merge Loop: Compare elements from nums1 and nums2 backward and place the larger element in the correct position in nums1.
• Remaining Elements: If any elements remain in nums2, copy them over to nums1.

This approach ensures that nums1 contains the merged sorted array using constant extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?