Leetcode Study Day 2

Merge Sorted Array

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.

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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

My solution

Merge two arrays

Firstly, we loop the first array nums1, if we find the element in this array is 0 and the index is larger than m, we replace it with the element in nums2 start from 0 to n, we call it j in my code.

int j = 0;
for (int i = 0; i < nums1.size(); i ++){
    if (nums1[i] == 0 && n != 0 && i >= m){
        nums1[i] = nums2[j];
        j++;
    }
}

If m is 0

If m is 0, which means the first array is empty, we just replace the first array with the second array.

if ( m == 0){
    nums1 = nums2;
}

Sort the Array nums1

After merging the two arrays, we sort the array nums1 by using sort() function with lambda function.

sort (nums1.begin(), nums1.end(), [](int& a, int& b){
    return a < b;
});

Full code

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int j = 0;
        for (int i = 0; i < nums1.size(); i ++){
            if (nums1[i] == 0 && n != 0 && i >= m){
                nums1[i] = nums2[j];
                j++;
            }
        }
        if ( m == 0){
            nums1 = nums2;
        }
        sort (nums1.begin(), nums1.end(), [](int& a, int& b){
            return a < b;
        });
    }
};

Time complexity

The for loop runs for nums1.size() iterations, which is m + n in the worst case.
Inside the loop, there is a conditional statement and potentially a nums1 assignment, both of which have constant time complexity.
The dominant factor in the time complexity is the sorting step at the end of the code:

Sorting nums1 using std::sort has a time complexity of O((m + n) * log(m + n)) in the worst case, where m + n is the total number of elements in nums1 and nums2.
So, the overall time complexity of the solution is O((m + n) * log(m + n)) due to the sorting step.

Improved solution run in O(m + n) time

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

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

        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
};

The key idea in this algorithm is to work from the end of the arrays towards the beginning, comparing elements and placing them in the correct position in nums1. This approach efficiently merges the two sorted arrays without the need for additional sorting