How to Merge Two Sorted Arrays?
Description
Merge two given sorted ascending integer array A and B into a new sorted integer array.
Example
Example 1:
Input: A=[1], B=[1]
Output: [1,1]
Explanation: return array merged.Example 2:
Input: A=[1,2,3,4], B=[2,4,5,6]
Output: [1,2,2,3,4,4,5,6]
Explanation: return array merged.Challenge
How can you optimize your algorithm if one array is very large and the other is very small?
Step by Step Solution
When doing programming, a very straightforward idea is 2 steps:
1. Combine two arrays into a new Array;
2. Sort the new Array;
In Java, we could utilize the Collections.sort() method to easily sort the new Array since it helps you with the sorting algorithm. Here is the solution if we are allowed to use this method.
Now if we are NOT allowed to use the Collections.sort() method and if we are asked to implement the sorting algorithm, how can we do that?
Let’s do some brainstorm here. Image you are asked to pick up the balls from two buckets A and B, and put the ball into a new bucket in order. How will you do that? It will be some steps:
1. Create a new array;
2. Pick up the first ball of A and B, do comparison, if B < A, drop the B ball into the new bucket and put A ball back to the A bucket; If B > A, drop A ball and give back B ball.
3. Let’s assume that 1st round we pick up B ball, now the 2nd round is to pick up the 2nd ball of B bucket and still pick up the 1st ball from A bucket, do the comparison and decide which ball to put into the new bucket.
Now let’s write some pseudoCode for the above idea, since we need to pick up A ball and B ball anyway, and do comparison, then we would need 2 loops for the idea
Sounds like we have a good start, but there are two pending questions here:
A. How do we define the init value of the j ? For each round of looping A bucket, we don’t j from 0 again, right? Because we may already have some B[j] dropped into the new bucket
B. Consider a case like A = [1,2,3] and B = [4,5,6], for the above idea the new bucket will just have A balls and no B balls since there is no logic to add the rest of the B balls after we run out of A ball.
Now let’s add additional logic to fix the above 2 pending questions.
For the issue A, let’s think through what is the correct initial value of the j. We have count to track how many balls in the new bucket, and we have i to check how many A balls are already put in the new bucket. That means, the number of B balls in the new bucket is count - i, so the start value of j should be count -i.
It is a little hard to understand, right? So use some example to help us understand, let’s say we have A = [1,3,5], B=[2,4,6].
1. The first round of A: i = 0; j = 0; we pick A[0];
2. The second round of A: i = 1; j = 0; we pick B[0]; Continue the inner loop, i = 1; j =1, we pick up A[1], and we are done the second round;
3. Now before we are starting the third round A loop, we already have 2 A balls and 1 B ball in the new bucket. So the count is 3. Since we have 2 A ball, the i will be 2. OK, now question is which B ball we should start to pick to do comparison?
Yeap, we would pick B[1] since B[0] is already in the bucket, no need to pick it again. That means j = 1, right?
So how can you calculate j here using count and i?
The formula is j = count-i
Now you got the 1st issue resolved. Great! It is time to hit the 2nd issue. Now let’s use the idea of 1st issue to answer the following questions:
If we are dropping all A balls into the bucket, how many B balls in bucket? and how many leaves?
It is an easy answer, the amount of B balls in the bucket is count-A.length, so we would need to put the index from count-A.length to B.length of the B bucket to the new bucket.
Now let’s combine everything together into the solution
Finally, let’s dump it into the system. Accepted, good job!
In summary, we will prefer to choose the first solution than the last one in the real world. But this is a good training for us to know how to break down big problem into small problem, try to understand the problem with examples, knock it down then hit the final solution.
