Merge two sorted arrays into first
Hard
Java
Arrays
21 views
Problem Statement
Task: a has size m+n, first m elements valid. b has n elements. Merge b into a in sorted order (in-place).
Input Format
Two integers m and n
Array a of size m + n (first m elements are valid, last n are empty)
Array b of size n
Both arrays are already sorted in non-decreasing order
Array a of size m + n (first m elements are valid, last n are empty)
Array b of size n
Both arrays are already sorted in non-decreasing order
Output Format
Array a after merging b into it in sorted order (in-place).
Example
m = 3, n = 3 a = [1, 3, 5, 0, 0, 0] b = [2, 4, 6]
[1, 2, 3, 4, 5, 6]
Constraints
• m ≥ 0, n ≥ 0
• Total size of a is exactly m + n
• Do not use extra array
• Merge must be done in-place
• Total size of a is exactly m + n
• Do not use extra array
• Merge must be done in-place
Concept Explanation
Both arrays are already sorted.
To merge in-place, we start filling a from the end,
so existing values are not overwritten.
To merge in-place, we start filling a from the end,
so existing values are not overwritten.
Step-by-Step Explanation
1.Set three pointers:
• i = m - 1 → last valid element in a
• j = n - 1 → last element in b
• k = m + n - 1 → last position in a
2.While i >= 0 and j >= 0:
• If a[i] > b[j]:
• Set a[k] = a[i]
• Decrement i
• Else:
• Set a[k] = b[j]
• Decrement j
• Decrement k
3.If elements remain in b:
• Copy them into a (remaining a elements are already in place)
4.Array a is now fully merged and sorted.
• i = m - 1 → last valid element in a
• j = n - 1 → last element in b
• k = m + n - 1 → last position in a
2.While i >= 0 and j >= 0:
• If a[i] > b[j]:
• Set a[k] = a[i]
• Decrement i
• Else:
• Set a[k] = b[j]
• Decrement j
• Decrement k
3.If elements remain in b:
• Copy them into a (remaining a elements are already in place)
4.Array a is now fully merged and sorted.
Concept Explanation
Both arrays are already sorted.
To merge in-place, we start filling a from the end,
so existing values are not overwritten.
To merge in-place, we start filling a from the end,
so existing values are not overwritten.
Step-by-Step Explanation
1.Set three pointers:
• i = m - 1 → last valid element in a
• j = n - 1 → last element in b
• k = m + n - 1 → last position in a
2.While i >= 0 and j >= 0:
• If a[i] > b[j]:
• Set a[k] = a[i]
• Decrement i
• Else:
• Set a[k] = b[j]
• Decrement j
• Decrement k
3.If elements remain in b:
• Copy them into a (remaining a elements are already in place)
4.Array a is now fully merged and sorted.
• i = m - 1 → last valid element in a
• j = n - 1 → last element in b
• k = m + n - 1 → last position in a
2.While i >= 0 and j >= 0:
• If a[i] > b[j]:
• Set a[k] = a[i]
• Decrement i
• Else:
• Set a[k] = b[j]
• Decrement j
• Decrement k
3.If elements remain in b:
• Copy them into a (remaining a elements are already in place)
4.Array a is now fully merged and sorted.
Input / Output Format
Input Format
Two integers m and n
Array a of size m + n (first m elements are valid, last n are empty)
Array b of size n
Both arrays are already sorted in non-decreasing order
Array a of size m + n (first m elements are valid, last n are empty)
Array b of size n
Both arrays are already sorted in non-decreasing order
Output Format
Array a after merging b into it in sorted order (in-place).
Constraints
• m ≥ 0, n ≥ 0
• Total size of a is exactly m + n
• Do not use extra array
• Merge must be done in-place
• Total size of a is exactly m + n
• Do not use extra array
• Merge must be done in-place
Examples
Input:
m = 3, n = 3
a = [1, 3, 5, 0, 0, 0]
b = [2, 4, 6]
Output:
[1, 2, 3, 4, 5, 6]
Example Solution (Public)
static void mergeIntoA(int[] a,int m,int[] b,int n){int i=m-1,j=n-1,k=m+n-1;while(j>=0){if(i>=0 && a[i]>b[j]) a[k--]=a[i--];else a[k--]=b[j--];}}
Official Solution Code
static void mergeIntoA(int[] a,int m,int[] b,int n){int i=m-1,j=n-1,k=m+n-1;while(j>=0){if(i>=0 && a[i]>b[j]) a[k--]=a[i--];else a[k--]=b[j--];}}
Please login to submit solutions.