Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/88.html

88. Merge Sorted Array

Level

Easy

Description

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:

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

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

Output: [1,2,2,3,5,6]

Solution

To avoid overwriting elements in nums1 before the elements are put in the correct positions, start from the end of the array and put elements to the correct positions backwards.

Let index1 and index2 be indices in original arrays nums1 and nums2, and index be the index in merged array nums1. Initially, index1 = m - 1, index2 = n - 1 and index = m + n - 1.

While both index1 and index2 are greater than or equal to 0, each time compare the elements nums1[index1] and nums2[index2], and put the greater elements to nums1[index]. Reduce index1 by 1, and reduce either index1 or index2 by 1 where the element is put to nums1[index].

When only one array has remaining elements, put the elements from the array to the remaining positions in nums1[index].

2 pitfalls

  • 1) Don’t use nums1.length if you give m, because nums1 is followed by a row of 0
  • 2) Note that the pointer of p1 or p2 will be reduced to a negative number, then index error, so add a check

Code

  • import java.util.Arrays;

public class Merge_Sorted_Array {

	public static void main(String[] args) {
		Merge_Sorted_Array out = new Merge_Sorted_Array();

		Solution s = out.new Solution();

		int[] nums1 = new int[]{1};
		s.merge(new int[]{}, 0, nums1, 1);
		System.out.println(Arrays.toString(nums1));
	}

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

            if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
                return;
            }

            int p1 = m - 1;
            int p2 = n - 1;
            for (int i = m + n - 1; i>= 0; i--) {

                int v1 = nums1[p1];
                int v2 = p2 >= 0 ? nums2[p2] : Integer.MIN_VALUE;
                if (v1 > v2) {
                    nums1[i] = nums1[p1--];
                } else {
                    nums1[i] = nums2[p2--];
                }
            }
        }
    }

}

############

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

  • // OJ: https://leetcode.com/problems/merge-sorted-array/
// Time: O(M + N)
// Space: O(1)
class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        for (int i = m - 1, j = n - 1, k = m + n - 1; k >= 0; --k) {
            if (j < 0 || (i >= 0 && A[i] > B[j])) A[k] = A[i--];
            else A[k] = B[j--];
        }
    }
};

  • class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        i, j, k = m - 1, n - 1, m + n - 1
        while j >= 0: # what if j=-1 already but k is not 0 yet? e.g. m=[1,2,0], n=[3] ==> then no more ops needed, rest of m[] already sorted, so this while is good enough
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

############

class Solution(object):
  def merge(self, nums1, m, nums2, n):
    """
    :type nums1: List[int]
    :type m: int
    :type nums2: List[int]
    :type n: int
    :rtype: void Do not return anything, modify nums1 in-place instead.
    """
    end = m + n - 1
    m -= 1
    n -= 1
    while end >= 0 and m >= 0 and n >= 0:
      if nums1[m] > nums2[n]:
        nums1[end] = nums1[m]
        m -= 1
      else:
        nums1[end] = nums2[n]
        n -= 1
      end -= 1

    while n >= 0:
      nums1[end] = nums2[n]
      end -= 1
      n -= 1


class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p = m + n - 1
        m -= 1
        n -= 1
        while m >= 0 and n >= 0:
            if nums1[m] < nums2[n]:
                nums1[p] = nums2[n]
                p -= 1
                n -= 1
            else:
                nums1[p] = nums1[m]
                p -= 1
                m -= 1

        if m != 0:
            while m >= 0:
                nums1[p] = nums1[m]
                p -= 1
                m -= 1
        if n != 0:
            while n >= 0:
                nums1[p] = nums2[n]
                p -= 1
                n -= 1

  • func merge(nums1 []int, m int, nums2 []int, n int)  {
    i, j, k := m - 1, n - 1, m + n - 1
    for j >= 0 {
        if i >= 0 && nums1[i] > nums2[j] {
            nums1[k] = nums1[i]
            i--
        } else {
            nums1[k] = nums2[j]
            j--
        }
        k--
    }
}

  • /**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function (nums1, m, nums2, n) {
    let i = m - 1,
        j = n - 1,
        k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
};


  • class Solution {
    /**
     * @param Integer[] $nums1
     * @param Integer $m
     * @param Integer[] $nums2
     * @param Integer $n
     * @return NULL
     */
    function merge(&$nums1, $m, $nums2, $n) {
        while (count($nums1) > $m) {
            array_pop($nums1);
        }
        for ($i = 0; $i < $n; $i++) {
            array_push($nums1, $nums2[$i]);
        }
        asort($nums1);
    }
}

  • impl Solution {
    pub fn merge(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
        let (mut m, mut n) = (m as usize, n as usize);
        for i in (0..m + n).rev() {
            nums1[i] = match (m == 0, n == 0) {
                (true, false) => {
                    n -= 1;
                    nums2[n]
                }
                (false, true) => {
                    m -= 1;
                    nums1[m]
                }
                (_, _) => {
                    if nums1[m - 1] > nums2[n - 1] {
                        m -= 1;
                        nums1[m]
                    } else {
                        n -= 1;
                        nums2[n]
                    }
                }
            }
        }
    }
}

All Problems

All Solutions