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

Java

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--];
                }
            }
        }
    }

}

All Problems

All Solutions