Top Interview 150

Merging sorted arrays is a classic problem, and understanding how to solve it efficiently is essential for coding interviews. In this post, we'll tackle LeetCode's 88. Merge Sorted Array, part of the Top Interview 150 Questions challenge, using JavaScript. Let's dive into the problem, its nuances, and a clean, optimal solution!

? Problem Description
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order. Your task is to merge nums2 into nums1, such that nums1 remains sorted.

However, there's a twist:

nums1 has enough space (set to 0s) to accommodate the elements of nums2.
The final merged result must be stored in-place in nums1.

? Examples

Example 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Example 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

? Key Insights

• In-place merge: You need to fill nums1 without using extra space. This means directly modifying the array.
• Back-to-front strategy: Since nums1 has extra space at the end, the most efficient approach is to fill it from the back.

? JavaScript Solution: Two-Pointer Approach

The optimal solution leverages a two-pointer approach, starting from the end of both arrays. This ensures that the largest elements are placed first, avoiding unnecessary shifts of elements.

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

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

? How It Works

1. Start from the end:
   Compare the largest elements of nums1 and nums2 (using p1
   and p2 pointers). Place the larger element at the end of
   nums1 (using p pointer).

2. Decrement pointers:
   Move p1, p2, and p as you process elements.

3. Handle remaining elements:
   If any elements in nums2 are left, copy them into nums1. (No
   need to copy elements from nums1, as they’re already in place.)

? Complexity Analysis

? Dry Run
Input:
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Step p1 p2 p nums1
Init 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
Final Output: [1,2,2,3,5,6]

? Try It Yourself!

Check out the full problem and test cases on LeetCode. Challenge yourself to implement the solution without looking at the code!

? Pro Tips for Interviews

1. Clarify constraints: Ask if you can use extra space or if in- place is mandatory.
2. Optimize for edge cases: Consider cases where nums2 is empty or nums1 has no initial elements (m = 0).
3. Walk through your logic: Explain the two-pointer approach clearly to the interviewer.

Got any questions or insights? Share them in the comments below! Let’s learn together. ?

The above is the detailed content of LeetCode Challenge: Merge Sorted Array - JavaScript Solution. For more information, please follow other related articles on the PHP Chinese website!