LeetCode – Merge Sorted Array

Link: https://leetcode.com/problems/merge-sorted-array/

Solution:

We know that both lists are already sorted, so we will use m and n as indexes to compare elements from right to left, therefore the initial m– and n–. We will use m-1 as the initial pivot on nums1 to start comparing nums2 elements from right to left. If the nums2 number is greater than the pivot we know that actually that number is the greatest from the both lists, so we can start swapping the zeros from right to left. But if its smaller than the pivot, we move the pivot +1 on the right and the new number becomes the new pivot.

For the input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Iteration 1:

  • Pivot: 3 (index 2)
  • 3 < 6 replace: 0 from num1 with 6 from num2
  • nums1: [ 1, 2, 3, 0, 0, 6 ]

Iteration 2:

  • Pivot: 3 (index 2)
  • 3 < 5 replace: 0 from num1 with 5 from num2
  • nums1: [ 1, 2, 3, 0, 5, 6 ]

Iteration 3:

  • Pivot: 3 (index 2)
  • 3 > 2 replace: 0 from num1 with 3 from num1 (notice that this time the pivot goes +1 on the right)
  • nums1: [ 1, 2, 3, 3, 5, 6 ]

Iteration 4:

  • Pivot: 2 (index 1)
  • 2 <= 2 replace: 3 from num1 with 2 from num2
  • nums1: [ 1, 2, 2, 3, 5, 6 ]
var merge = function(nums1, m, nums2, n) {
    if(n == 0) return;
    
    var i = nums1.length-1;
    m--;
    n--;
    
    while(n >= 0 && m >= 0)
    {
        if(nums1[m] > nums2[n])
            nums1[i--]=nums1[m--];
        else
            nums1[i--]=nums2[n--];
    }

    if(n >= 0)
        while(i >= 0)
            nums1[i--]=nums2[n--];


    if(m >= 0)
        while(i >= 0)
            nums1[i--]=nums1[m--];
};

Complexity: O(n)

Leave a Reply

Your email address will not be published. Required fields are marked *