Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

88. Merge Sorted Array

Time: $O(m + n)$

Space: $O(1)$

			


class Solution {
 public:
  void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1;      // nums1's index (actual nums)
    int j = n - 1;      // nums2's index
    int k = m + n - 1;  // nums1's index (next filled position)

    while (j >= 0)
      if (i >= 0 && nums1[i] > nums2[j])
        nums1[k--] = nums1[i--];
      else
        nums1[k--] = nums2[j--];
  }
};




			


class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;     // nums1's index (actual nums)
    int j = n - 1;     // nums2's index
    int k = m + n - 1; // nums1's index (next filled position)

    while (j >= 0)
      if (i >= 0 && nums1[i] > nums2[j])
        nums1[k--] = nums1[i--];
      else
        nums1[k--] = nums2[j--];
  }
}




			


class Solution:
  def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = m - 1      # nums1's index (actual nums)
    j = n - 1      # nums2's index
    k = m + n - 1  # nums1's index (next filled position)

    while j >= 0:
      if i >= 0 and nums1[i] > nums2[j]:
        nums1[k] = nums1[i]
        k -= 1
        i -= 1
      else:
        nums1[k] = nums2[j]
        k -= 1
        j -= 1