In this tutorial, we will delve into the “Merge Sorted Array” problem and provide a comprehensive Java solution. This problem is a classic algorithmic challenge that tests your ability to merge two sorted arrays in an efficient manner. We will start by understanding the problem statement, breaking it down into smaller components, and then proceed to implement the solution step by step.
Problem Statement
Given two sorted arrays, nums1
and nums2
, the task is to merge nums2
into nums1
as one sorted array. The merged array should be sorted in non-decreasing order.
Note:
nums1
has enough space to hold additional elements fromnums2
.- The number of elements initialized in
nums1
andnums2
arem
andn
respectively.
Approach Overview
To merge two sorted arrays efficiently, we need to compare the elements of both arrays and place them in the correct positions in the final merged array. Since nums1
has enough space to accommodate all elements, we can start from the end of both arrays and work backwards. This approach avoids overwriting values in nums1
that haven’t been processed yet.
The steps involved in this approach are as follows:
- Initialize two pointers,
p1
andp2
, at the last valid elements ofnums1
andnums2
respectively. - Initialize a pointer
p
at the end ofnums1
, which is the last position where elements can be inserted. - Compare
nums1[p1]
andnums2[p2]
. Insert the larger element atnums1[p]
and decrement the respective pointer. - Repeat step 3 until all elements have been merged.
Let’s now implement this approach in Java.
Java Implementation
public class MergeSortedArray {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1; // Pointer for nums1
int p2 = n - 1; // Pointer for nums2
int p = m + n - 1; // Pointer for merged array
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2]) {
nums1[p] = nums1[p1];
p1--;
} else {
nums1[p] = nums2[p2];
p2--;
}
p--;
}
// Copy remaining elements from nums2 if any
System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
}
public static void main(String[] args) {
int[] nums1 = new int[6]; // Initialize nums1 with enough space
nums1[0] = 1;
nums1[1] = 3;
nums1[2] = 5;
int m = 3;
int[] nums2 = {2, 4, 6};
int n = 3;
merge(nums1, m, nums2, n);
// Print the merged array
for (int num : nums1) {
System.out.print(num + " ");
}
}
}
Step-by-Step Explanation
- We start by defining a class named
MergeSortedArray
. - In the
merge
method, we take four parameters:nums1
,m
,nums2
, andn
. Here,nums1
is the target array,m
is the number of initialized elements innums1
,nums2
is the array to be merged, andn
is the number of elements innums2
. - We initialize three pointers:
p1
points to the last valid element innums1
.p2
points to the last element innums2
.p
points to the last position in the merged array.
- We start a
while
loop that continues until eitherp1
orp2
becomes less than 0. - Inside the loop, we compare the elements at
nums1[p1]
andnums2[p2]
. Ifnums1[p1]
is greater, we insert it atnums1[p]
and decrementp1
. Otherwise, we insertnums2[p2]
atnums1[p]
and decrementp2
. - After inserting an element, we decrement the pointer
p
to move to the next position in the merged array. - Once the loop is done, there might be some remaining elements in
nums2
that need to be inserted intonums1
. We use theSystem.arraycopy
method to copy the remaining elements fromnums2
to the beginning ofnums1
. - In the
main
method, we initializenums1
with enough space to accommodate the merged elements. We also initializenums2
. - We call the
merge
method with the appropriate parameters to mergenums2
intonums1
. - Finally, we iterate through the merged array and print the elements.
Time and Space Complexity Analysis
The time complexity of this solution is O(m + n), where m is the number of elements in nums1
and n is the number of elements in nums2
. We only traverse through the arrays once.
The space complexity is O(1), as we are not using any extra space that scales with the input size. We are performing the merging in-place.
Conclusion
In this tutorial, we explored the “Merge Sorted Array” problem and provided a detailed Java solution. We discussed the problem statement, formulated an approach, implemented the solution step by step, and analyzed the time and space complexity of the solution. By following this tutorial, you should now have a clear understanding of how to efficiently merge two sorted arrays in Java while maintaining the sorted order.