LeetCode: 88. Merge Sorted Array Javascript Solution

Problem description:

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

At first, I considered using nested for loops to compare the values in nums2 using “i” and nums1 using “j”. My plan was to push the smaller value to a temporary array. However, upon further review, this approach was not feasible, so I abandoned the idea of using a temporary array and instead focused on finding a way to directly merge and sort the two arrays into one.

My next approach was to maintain the nested for loop, but compare the values at indices “i” and “j”. The bigger value would then be inserted at “j + 1”. I believed that this approach would allow me to insert all values from nums2 into their appropriate positions in nums1. However, after giving it further consideration, I realized that this approach was also flawed and I had to abandon it.

I returned to considering a solution involving a temporary array. This time, I planned to compare the elements in nums2 with those in nums1. If an element in nums2 was either smaller than or equal to an element in nums1, I would push it into the temporary array. My expectation was that this approach would eventually result in a merged and sorted array. However, even this approach proved to be unproductive.

I ended up eventually hacking together a solution that managed to pass test case 1 on LeetCode, that’s when I realized that my previous solutions were all test case 1 centric, I was myopically focused on making the solution work for test case 1 only.

I wasn’t accounting for the 0s that were in nums1 and my merged output always included them, so I decided to clean up nums1 of 0s before iterating over it using Javascript built-in function slice, the idea being if I take any element from nums2 and subtract 1 from it, it would tell me the appropriate index to insert it in nums1, so I took the following steps:

Step 1: The function creates a copy of the first m elements of nums1 into a temporary array called temp.

Step 2: The nums2 array is sorted in ascending order using JavaScript's built-in sort method and the (a, b) => a - b comparator function.

Step 3: The function loops through the sorted nums2 array and checks if the current element is greater than or equal to 1 and less than or equal to temp.length + 1. If this condition is true, it inserts the current element into the temp array at the index nums2[i] - 1 using the splice method.

Step 4: The loop through temp array and copies its elements into the nums1 array.

Step 5: The function logs the modified nums1 array to the console.

Finally this approach worked, it had a O(nlogn) time complexity because of sorting and a O(m) memory complexity because that is the length of temp, it passed all three test cases and was accepted by LeetCode … I submitted my solution and got this:

Although this solution cleared the first three test cases, the submission was not accepted because overall it was passing only 14/59 test cases.

At this point I was starting to feel hopeless, the different approaches and solutions I had come up with have taken me 5 days so far … and I’m still refusing to look at a solution online because if I do that I would be an imposter, I’m never gonna be able to solve this problem or any other on my own and I’m never gonna become a software engineer …

As I sat in this self-doubt and despair, I decided to go back to basics and actually look up how to properly insert an element into an array … I realized, or rather was reminded of the fact that I can not simply insert an element into an array and call it a day, because every time I do that I’m overwriting another element, now it made total sense (at least partially) why all my solutions didn’t work, they were all based on that assumption.

As I reread the problem description on LeetCode, I realized an essential piece of information that had previously eluded me. The zeros in nums1 were not to be removed, but instead were to be replaced by elements from nums2. They were included as placeholder positions to accommodate the values from nums2.

I also realized that I was dead set on finding a brute force solution to solve this problem and somehow dead set on using a nested for loop to do it, brute force solutions often use nested for loops, matter of fact usually that’s a quick tell that the solution has a n² complexity but perhaps a nested for loop is not even the right brute force approach for this problem.

I also spent an awful lot of time trying to hack a solution focused solely on passing test case 1 … so after all these mishaps I finally arrived at the epiphany and the greatest personal takeaway from problem 88 on LeetCode and the 5 days I have spent on it … and that is:

You simply don’t know what you don’t know!

This was immediately confirmed the moment I looked up what would be the most optimal solution to solve this problem, after analyzing the approach used I realized that I simply could not have arrived at the solution on my own because I was completely unfamiliar with the pattern with which a solution could be found, and that was such a great relief.

How many times have I simply taken the wrong approach, made the wrong assumptions, had the wrong information or simply didn’t know what I didn’t know but walked away from the problem thinking I can’t solve it because I simply don’t have it in me or that I’m not meant to be a software engineer.

I realized that imposter syndrome is more often than not simply a byproduct of looking at the problem incorrectly, making the wrong assumption and simply not knowing what you don’t know.

I further discovered that studying optimal solutions and their underlying approach is critical to developing the necessary pattern recognition and knowledge required to be able to solve problems independently.

The more problems I get exposed to, the more pattern recognition I can develop, the more algorithms and data structures I pick up, the bigger my toolbox gets and my ability to draw on it to solve problems on my own … that was a profound discovery for me and one that will change the way I solve, write or make videos about a problem.

So back to the most optimal solution to actually solve problem 88 on LeetCode, it turns out the best approach to merge two sorted arrays is to use a two pointer technique or in this case three pointers:

• Initialize three pointers, p1, p2, and p, which start at the last index of nums1(m), nums2, and nums1(m+n), respectively.
• Create a while loop that continues as long as both p1 and p2 are greater than or equal to zero.
• Within the while loop, compare the values at nums1[p1] and nums2[p2]. If nums2[p2] is larger, the value is copied to nums1[p] and p2 is decremented. If nums1[p1] is larger, the value is copied to nums1[p] and p1 is decremented. After each copy, p is decremented.
• After the first while loop terminates, if p2 is still greater than or equal to zero, another while loop is executed to copy the remaining values from nums2 to nums1.
• After both while loops have completed, the merged and sorted array will be stored in nums1.

I ran the code, it passed the first 3 test cases then I submitted my solution and got the following stats:

I was absolutely ecstatic to get to this point and finally see an optimal solution that I fully understood, knew how to implement and that had O(m+n) time complexity and O(1) memory complexity, where m and n are the lengths of the arrays nums1 and nums2, respectively.

I have picked up so much while working on this problem but most importantly I understood so much more about myself and my thinking process as an aspiring software engineer, I think I will look back at problem 88 and the 5 days I have spent on it as a turning point that made me change the way I look at problem solving.

Source Code on Github:

https://github.com/jadibdev/Leetcode_Solutions/tree/88_Merge_Sorted_Array

Originally published at http://codemghrib.wordpress.com on February 10, 2023.