PermalinkProblem statement
Merge two sorted arrays nums1
and nums2
into nums1
of length m + n
. The result should be a single sorted array in non-decreasing order. nums1
has m
elements at the beginning, followed by n
zeros. nums2
has n
elements.
PermalinkConstraints
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10<sup>9</sup> <= nums1[i], nums2[j] <= 10<sup>9</sup>
PermalinkExamples
nums1 = [1, 3, 5, 7, 9, 0, 0, 0, 0]
nums2 = [2, 4, 6, 8]
Output = [1, 2, 3, 4, 5, 6, 7, 8, 9]
PermalinkSudo Code
Initialize i, j and k
Comparison between two array elements to fit in correct position
If first array elements is remaining then add it to answer
If second array elements is remaining then add it to answer
PermalinkDry Run
PermalinkSolution
public void merge(int[] nums1, int n, int[] nums2, int m) {
// Step 1. Initialize i, j and k
int i = n-1, j = m-1, k = m+n-1;
// Step 2. Comparison between two array elements to fit in correct positon
while(i >= 0 && j >= 0){
if(nums1[i] >= nums2[j]){
nums1[k--] = nums1[i--];
}else{
nums1[k--] = nums2[j--];
}
}
// Step 3. If first array elements is remaining then add it to ans.
while(i >= 0){
nums1[k--] = nums1[i--];
}
// Step 4. If second array elements is remaining then add it to ans.
while(j >= 0){
nums1[k--] = nums2[j--];
}
PermalinkTime complexity Analysis
Time Complexity: O(m + n)
Space Complexity: O(1)
PermalinkTopics Covered
Two Pointers
PermalinkCompanies
Amazon, Goldman Sachs, Linkedin, Microsoft, Visa