LeetCode - Merge Sorted Array

1 minute read

Problem description

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:

1
2
3
4
5
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

Analysis

Just use insert index to get a O(n) space complexity solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        int j = 0;
        
        int insertIndex = 0;
        
        int[] vals = new int[m];
        
        for (int l = 0; l < m; l++){
            vals[l]=nums1[l];
        }
        
        while(i< m || j < n){
            int v1 = i == m? Integer.MAX_VALUE: vals[i];
            int v2 = j == n? Integer.MAX_VALUE:nums2[j];
            
            if (v1 < v2){
                nums1[insertIndex++] = vals[i];
                i++;
            }
            else{
                nums1[insertIndex++] = nums2[j];
                j++;
            }
        }
    }
}

However, if we start from the end, we can get a O(1) SC solution.

1
2
3
4
5
6
7
8
9
10
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
      while(n>0){
          if(m<=0 || nums1[m-1]< nums2[n-1])
              nums1[m+n-1]=nums2[--n];
          else
              nums1[m+n-1]=nums1[--m];
      }
    }
}

What to improve

  • if we have to save information from the beginning, we can start from the end to save space.