Good morning! Hope your day has started on the right note. The high temperature in the Twin Cities of Minneapolis and St. Paul is forecasted to be about ten degrees less than yesterday. BTW, yesterday the temperature went up to 61F which is the highest this year so far. My wife and I were planning on grilling yesterday but one thing and the other and I ended having BBQ Chicken Teriyaki from Trader Joe’s. Tasty but I prefer my wife cooking (just making points).
It seems that COVID-19 vaccinations are starting to pick up Minnesota. We are behind other states but the expectations are high. We need to hit herd immunity as soon as possible. It seems that masks and social distancing will be a good idea for people with or without the vaccine for the near future until there is enough data to understand if we will need periodic vaccine boosters or not.
On the other hand, Israel with a population of about 9M people, is leading the world vaccinating people. The results appear to be very good. They appear to be using primarily the Pfizer vaccine. Hopefully the data there collected will be distributed worldwide so we can learn about their process and procedures.
I decided to look for a problem that merges sorted arrays. I found LeetCode 88 Merge Sorted Array so I went for it.
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2. Constraints: o nums1.length == m + n o nums2.length == n o 0 <= m, n <= 200 o 1 <= m + n <= 200 o -109 <= nums1[i], nums2[i] <= 109
We are given two sorted arrays. We have to merge them into one. Our values include positive and negative integers.
I will be solving this problem using Java on my own computer running Windows 10 and will be using the VSCode IDE. Since I will develop the code on my computer I will need to generate some test code. If you decide to develop your solution on-line, then the LeetCode IDE works fine and you will not require developing a test scaffold as I will.
public void merge(int[] nums1, int m, int[] nums2, int n) {
}
The signature for the method is question is appropriate. The first int[] has m elements but it also has a total capacity of m + n elements. The idea is to merge the two arrays into the first one.
1,2,3,0,0,0 3 2,5,6 3 main <<< str ==>2,5,6<== main <<< m: 3 main <<< n: 3 main <<< nums1: [1, 2, 3, 0, 0, 0] main <<< nums2: [2, 5, 6] main <<< nums1: [1, 2, 2, 3, 5, 6] main <<< nums1: [1, 2, 3, 0, 0, 0] main <<< nums2: [2, 5, 6] main <<< nums1: [1, 2, 2, 3, 5, 6] 1 1 0 main <<< str ==><== main <<< m: 1 main <<< n: 0 main <<< nums1: [1] main <<< nums2: [] main <<< nums1: [1] main <<< nums1: [1] main <<< nums2: [] main <<< nums1: [1] 1,2,3,4,5 5 0 main <<< str ==><== main <<< m: 5 main <<< n: 0 main <<< nums1: [1, 2, 3, 4, 5] main <<< nums2: [] main <<< nums1: [1, 2, 3, 4, 5] main <<< nums1: [1, 2, 3, 4, 5] main <<< nums2: [] main <<< nums1: [1, 2, 3, 4, 5] 4,0,0,0,0,0 1 1,2,3,5,6 5 main <<< str ==>1,2,3,5,6<== main <<< m: 1 main <<< n: 5 main <<< nums1: [4, 0, 0, 0, 0, 0] main <<< nums2: [1, 2, 3, 5, 6] main <<< nums1: [1, 2, 3, 4, 5, 6] main <<< nums1: [4, 0, 0, 0, 0, 0] main <<< nums2: [1, 2, 3, 5, 6] main <<< nums1: [1, 2, 3, 4, 5, 6]
We are provides four input lines. The first contains the integer elements for the first array. The number of elements is in the second line. The same holds for the next two lines with the only difference that the information applies to the second array.
Our test code reads the arrays and displays the contents of the string holding the values for the second array only. It seemed to me that the second line was of special interest due to the fact that on some occasions the second array may be empty.
The test code reads and processes the input data and displays the values for the n and m arguments for our method of interest. The initial arrays are then displayed.
It seems that our test code calls the method of interest and then displays the contents of the merged array.
It seems that we restore the values of the first array and repeat the operations making use of a second implementation of the method in question.
All this will become clear as we take a look at the test code WHICH IS NOT PART OF THE SOLUTION.
We have four test cases.
/**
* Test scaffolding.
*
* !!!! NOT PART OF SOLUTION !!!!
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read data for the first array ****
int[] nums1 = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// *** read the number of elements in the first array ****
int m = Integer.parseInt(br.readLine().trim());
// **** read data for the second array ****
String str = br.readLine().trim();
// ???? ????
System.out.println("main <<< str ==>" + str + "<==");
// **** check if empty string ****
int[] nums2 = null;
if (str.equals(""))
nums2 = new int[0];
else
nums2 = Arrays.stream(str.split(","))
.mapToInt(Integer::parseInt)
.toArray();
// *** read the number of elements in the second array ****
int n = Integer.parseInt(br.readLine().trim());
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< m: " + m);
System.out.println("main <<< n: " + n);
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
System.out.println("main <<< nums2: " + Arrays.toString(nums2));
// **** make a copy of nums1 for later use ****
int[] nums3 = nums1.clone();
// **** merge the two arrays into the first array ****
merge1(nums1, m, nums2, n);
// ???? display merged array ????
System.out.println("main <<< nums1: " + Arrays.toString(nums1) + "\n");
// **** restore nums1 ****
nums1 = Arrays.copyOf(nums3, nums3.length);
// ???? ????
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
System.out.println("main <<< nums2: " + Arrays.toString(nums2));
// **** merge the two arrays into the first array ****
merge(nums1, m, nums2, n);
// ???? display merged array ????
System.out.println("main <<< nums1: " + Arrays.toString(nums1));
}
We read the input data with some care to make sure we generate the proper arrays. Of interest is the second array wince it can be empty and the m and n numbers follow the actual data for the arrays. I guess I could have inverted their positions but it is always nice to experiment. It seems that if you do not practice your techniques start to deteriorate rather quickly. At least that is my experience.
I decided to generate two solutions. The first one is slower but easier to grasp than the second. Keep in mind that when developing production code you need to check parameters, allocate and free resources, implement an algorithm and maintain it. You need to aim to develop clean and easy to follow code. Of course there is always the matter of performance. If you are dealing with a dozen values and your code executes now and then and is not part of a very used workflow, then you might emphasize readability for ease of maintenance. Otherwise; your solution could be considered the first pass and once you have something that works, then you can simplify it to make it run faster. Note that in some occasions a complete different algorithm might work much faster than the one you initially selected. You also have to consider the time it takes to develop a first working pass. In industry there is something called the MVP (Minimum Viable Product), which you can use to get initial customer feedback while your team develops light blinding super fast code.
/**
* You may assume that nums1 has a size equal to m + n
* such that it has enough space to hold additional
* elements from nums2.
*
* Execution time: O((n + m) * log(n + m))
*
* Runtime: 2 ms, faster than 6.98% of Java online submissions for Merge Sorted Array.
* Memory Usage: 39 MB, less than 81.89% of Java online submissions for Merge Sorted Array.
*/
static void merge1(int[] nums1, int m, int[] nums2, int n) {
// **** sanity check(s) ****
if (m == 0 && n == 0)
return;
if (n == 0)
return;
// **** initialization ****
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(n + m, (a,b) -> (a - b) );
// **** add elements from nums1 - O(m log(m)) ****
for (int i = 0; i < m; i++)
pq.add(nums1[i]);
// **** add elements from nums2 - O(n log(n)) ****
for (int i = 0; i < n; i++)
pq.add(nums2[i]);
// **** populate nums1 from the pq - O(m + n)****
int i = 0;
while (!pq.isEmpty())
nums1[i++] = pq.remove();
}
This attempt uses a priority queue. The queue is used to maintain the contents of the arrays sorted. After feeding the contents of the two arrays to the priority queue, we populate the first array with the contents of the priority queue.
As you can see this approach is not bad but in general a priority queue is not as fast as we would like. Note that we specified the maximum size for the priority queue so it would not have to resize while we are adding values. Note that our solution was accepted by LeetCode but the execution time could get better with a different approach. At this time we have a MVP (not a brute force) solution.
/**
* You may assume that nums1 has a size equal to m + n
* such that it has enough space to hold additional
* elements from nums2.
*
* Execution time: O(n + m)
*
* Runtime: 0 ms, faster than 100.00% of Java online submissions.
* Memory Usage: 39 MB, less than 71.39% of Java online submissions.
*/
static void merge(int[] nums1, int m, int[] nums2, int n) {
// ***** initialization ****
m--; // last element in nums1
n--; // last element in nums2
int i = nums1.length - 1; // current element in nums2
// **** copy sorted integers from nums2 or nums1 to nums1 (right to left) ****
while (i >= 0 && m >= 0 && n >= 0) {
if (nums1[m] > nums2[n])
nums1[i--] = nums1[m--];
else
nums1[i--] = nums2[n--];
}
// **** copy remaining sorted integers from nums2 to nums1 (right to left) ****
while (n >= 0)
nums1[i--] = nums2[n--];
}
In this approach we looked at the arguments. We could copy data from the second to the first array maintaining order. When done, since the second array is also sorted, we could just make sure we did not leave data that is not present in the first array.
Note that in the first loop we might have to copy an element from the first array if it is of lesser value than the next from the second array.
Stop for a moment and digest the approach by running a few examples using a pen and paper. Of course you can single step and get a similar experience.
This algorithm is faster and does not require the additional O(n + m) space used by the priority queue. This pass is the final product that took more time but runs faster and does not require additional space. In general this is the approach that my team and I tend to use.
My wife is calling me to go up for coffee. I exceeded the 2-hour working block. Will be back in a few…
… I am back. We also spent a few minutes chatting with one of my sons over Skype.
I hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all subscribers to this blog!!!
Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.
Regards;
John
john.canessa@gmail.com