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.

Clarifying Questions

1. Is it guaranteed that the input arrays nums1 and nums2 are already sorted?
   • Yes, both nums1 (first m elements) and nums2 are sorted in non-decreasing order.
2. Can the elements in nums1 be negative?
   • Yes, the elements can be negative as it is not mentioned that the elements are strictly positive.
3. Should the merged elements fit within the initial length of nums1?
   • Yes, the merged array should replace the elements in nums1 without exceeding its length.

Strategy

1. Two-Pointer Approach: Use two pointers (p1 for nums1 and p2 for nums2) and start comparing from the end of both arrays. This ensures that we utilize the empty spaces at the end of nums1 effectively.
2. Merge in Reverse Order:
   • Start from the back of nums1 and fill in elements from the end to the beginning.
   • Compare the elements that p1 and p2 points to and place the larger element at the current end position.
   • Move the pointer accordingly and reduce the index p where the next element is to be placed.
3. Edge Case: If elements remain in nums2 after p1 is exhausted, copy them directly into the starting positions in nums1.

Code

public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Pointers
        int p1 = m - 1; // pointer for nums1
        int p2 = n - 1; // pointer for nums2
        int p = m + n - 1; // pointer for merged array
        
        // Merge in reverse order
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        
        // If there are remaining elements in nums2
        while (p2 >= 0) {
            nums1[p] = nums2[p2];
            p2--;
            p--;
        }
    }
}

Time Complexity

• Time Complexity: O(m + n)
  • We process each element of nums1 and nums2 exactly once in a single pass, thus it’s O(m + n).
• Space Complexity: O(1)
  • The algorithm does not utilize any extra space proportional to the input size; we modify nums1 in-place.

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?