[📝LeetCode #88] Merge Sorted Array

#leetcode #java #100daysofcode #twopointers

🎀 The Problem

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.

Example:

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

👩‍💻 My Answer

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        if (m == 0) {
            System.arraycopy(nums2, 0, nums1, 0, n);
            return;
        } else if (n == 0)
            return;

        int[] nums3 = nums1.clone(); // copy of nums 1
        int temp;
        int i = 0;
        int j = 0;
        int k = 0;

        while (i < m && j < n) {
            if (nums3[i] < nums2[j]) { // if nums2 is larger than nums3
                nums1[k] = nums3[i]; // add nums3 letter into nums1
                k++;
                i++;
            } else if (nums3[i] >= nums2[j]) {
                nums1[k] = nums2[j]; // add nums2 into nums1
                k++;
                j++;
            }
        }

        while (i < m) { // if i is still smaller than m
                nums1[k] = nums3[i]; // add nums3 into nums1
                k++;
                i++;
        }
        while (j < n) { // if j is still smaller than n
                nums1[k] = nums2[j];  // add nums2 into nums1
                k++;
                j++;
        }
    }
}

Pro & Con

✅ Runtime & Memory
✖️ Too long
✖️ Bit complicated (Hard to read)

💋 Ideal Answer

Approach - "Two Pointer"

I read the solution post on LeetCode and found the "Two Pointer" approach (I feel it is more like a "Three Pointer" approach).

We can start by initializing two pointers, i and j, to m-1 and n-1, respectively. We will also have another pointer k initialized to m+n-1, which will be used to keep track of the position in nums1 where we will be placing the larger element. Then we can start iterating from the end of the arrays i and j, and compare the elements at these positions. We will place the larger element in nums1 at position k, and decrement the corresponding pointer i or j accordingly. We will continue doing this until we have iterated through all the elements in nums2. If there are still elements left in nums1, we don't need to do anything because they are already in their correct place.

I also watched the YouTube video to understand better.
LeetCode University's Merge Sorted Array Explanation

New Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = n + m - 1;
        int j = m - 1;
        int k = n - 1;


        while (k >= 0) {
            if (j < 0 || nums1[j] < nums2[k]) {
                nums1[i] = nums2[k];
                k--;
                i--;
            } else if (nums1[j] >= nums2[k]) {
                nums1[i] = nums1[j];
                j--;
                i--;
            }            
        }
    }
}

💡 What I Learned

How to copy int[]:
int[] nums3 = nums1.clone(); // copy of nums 1
How to minimize the code lines:
nums1[i--] = nums2[k--]; instead of

nums1[i] = nums2[k];
k--;
i--;

DEV Community