Leetcode 88 - Merge sorted array

Link to question

Question & Examples

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].

Implementation

function merge(nums1, m, nums2, n) {
  let first = m - 1
  let second = n - 1
  let i = m + n - 1
 
  while (second >= 0) {
    let firstVal = nums1[first]
    let secondVal = nums2[second]
    if(firstVal > secondVal) {
      nums1[i] = firstVal
      i--
      first--
    } else {
      nums1[i] = secondVal
      i--
      second--
    }
  }
}

Walkthrough

  1. We set up two pointers (i.e first and second) and a pointer i which we'll use to insert the values in set index.
  2. We create a while loop and check to see if second is greater or equal to 0. We do this because once second because a minus value, this means that we've done checking/inserting the values from the nums2 array to the nums2 array.
  3. We check to see which of the values in the first and second indices are greater (or smaller).
  4. When the value in the nums1 array is bigger, we set the value in the i index to said value in the nums1 array. After this, we decrement the i and first values. (Same goes for the opposite case).

Visual representation would look something like this

nums1 = [1, 2, 3, 0, 0, 0]
m = 3

nums2 = [2, 5, 6]
n = 3

[1, 2, 3, 0, 0, 0] [2, 5, 6]
     first      i       second
--> 6 is greater than 3 (so replace the value in i index and decrement appropriate values)

[1, 2, 3, 0, 0, 6] [2, 5, 6]
     first   i       second
--> 5 is greater than 3 (so replace the value in i index and decrement appropriate values)

[1, 2, 3, 0, 5, 6] [2, 5, 6]
     firsti       second
--> 3 is greater than 2 (so replace the value in i index and decrement appropriate values)

[1, 2, 3, 3, 5, 6] [2, 5, 6]
  firsti          second
--> 2 isn't greater than 2. This condition would apply to the else statement above (so replace the value in i index and decrement appropriate values)

[1, 2, 2, 3, 5, 6] [2, 5, 6]
firsti          
--> as the second value is less than 0, we end the function (As whatever's left in the nums1 array will already be sorted)

Time and Space Complexities

Time Complexity: O(m + n) | Space: O(1)

Go back to list