DEV Community

Angela F.
Angela F.

Posted on

Leetcode 150 | Day 1: Merge Sorted Array - Naive vs. Optimized

#leetcode #array #javascript

There's been no shortage of debate lately about whether grinding Leetcode still makes sense in the age of AI. I think it does. AI is a powerful tool, but it was built by humans; which means it inherited our strengths, our blind spots, and our biases. Leaning on it entirely without understanding what's happening under the hood is a risk. A mentor once told me: those who refuse to use AI are not hireable. But neither are those who rely on it entirely. Learning deeply is how you stay on the right side of that line.

This is my journey into just that - learning deeply.

Day 1 Leetcode 88: Merge Sorted Array

This is an interesting problem. You begin with 4 pieces of data - 2 arrays and 2 integers:

  • nums1: a sorted array whose length equals nums1.length + nums2.length. The first m elements are valid numbers; the remaining indexes hold 0s as placeholders.
  • nums2: a sorted array containing only valid numbers, with a length of n.
  • m: the count of valid numbers in nums1.
  • n: the count of valid numbers in nums2.

The objective is to merge both arrays into sorted order in place. Since nums1 is already sized to hold every valid element from both arrays, it's where the final sorted result will live.

Approach 1: Naive (Splice + Sort)

This solution is 2 lines of code. That's it. It's a testament to how much ES6 advanced JavaScript.

nums1.splice(m, n, ...nums2);
nums1.sort((a, b) => a - b);
Enter fullscreen mode Exit fullscreen mode

Here's how it works.

We start by calling .splice() on nums1. While .splice() has many use cases, here's what each argument is doing in this context:

  • m: the index where we start deleting elements. Since m is the count of valid numbers in nums1, starting at index m puts us right at the first placeholder 0 - exactly where we want to be.
  • n: the number of elements to delete. Since n equals the length of nums2, we're deleting exactly as many placeholders as we have values to insert.
  • ...nums2: the values we want to insert in place of the deleted elements. The ... is the spread operator, it unpacks nums2 so its values are inserted individually rather than as a nested array.

To make that concrete, without the spread operator:

nums1 = [1, 2, 3, [2, 5, 6]]  // not what we want
Enter fullscreen mode Exit fullscreen mode

With the spread operator:

nums1 = [1, 2, 3, 2, 5, 6]  // ✓
Enter fullscreen mode Exit fullscreen mode

Now all values live in one array. The last step is sorting. We call .sort() on nums1 and pass a compare function:

nums1.sort((a, b) => a - b);
Enter fullscreen mode Exit fullscreen mode
  • a and b are the two elements being compared
  • A negative result means a comes before b
  • A positive result means b comes before a
  • Zero means they're equal

And that's Approach 1, 2 lines and Leetcode 88 is solved.

You might assume that brevity equals optimization. In terms of readability, you'd be right, as this solution is easy to scan and quick to understand. But as with most things, there are trade-offs.

Time complexity: O((m + n) log(m + n))

O(m + n) comes from iterating through both arrays once during the splice. The log(m + n) comes from calling .sort() on the combined array. Sort has to do real work, and that cost adds up as the array grows.

Approach 2: Optimized (While Loop)

This approach uses a more classic while loop. Using the same example arrays from above, here's how it works.

We begin by initializing three pointers:

  • i: set equal to m - 1. This points to the last valid element in nums1. Since m is 3 and arrays are zero-based, i starts at index 2.
  • j: set equal to n - 1. This points to the last valid element in nums2. Since n is 3 and arrays are zero-based, j starts at index 2.
  • k: set equal to the last index of nums1. Since nums1 has a length of m + n, and arrays are zero-based, k starts at m + n - 1. 
let i = m - 1;
let j = n - 1;
let k = nums1.length - 1;
Enter fullscreen mode Exit fullscreen mode

Once our pointers are initialized, we enter the while loop.

The while loop condition:

Since we'll be decrementing both i and j on each pass, we need to make sure neither pointer has gone past the beginning of its array. So we verify on each iteration that both i and j are greater than or equal to zero:

while (i >= 0 && j >= 0) {
Enter fullscreen mode Exit fullscreen mode

Inside the loop:

We compare nums1[i] and nums2[j]. If nums1[i] is the larger value, we copy it to the index k is pointing to, then decrement both i and k. Otherwise, we copy nums2[j] to index k and decrement both j and k.

  if (nums1[i] > nums2[j]) {
    nums1[k] = nums1[i];
    i--;
  } else {
    nums1[k] = nums2[j];
    j--;
  }
  k--;
}
Enter fullscreen mode Exit fullscreen mode

Handling remaining elements:

It's entirely possible that nums2 has more elements than nums1. If that's the case, once i reaches -1 the while loop exits, and because our condition uses &&, it doesn't matter that j hasn't reached zero yet. Any remaining elements in nums2 would be skipped.

To handle this, we add a second while loop to copy over any remaining nums2 values. Since both arrays started sorted, we can copy them directly in order:

while (j >= 0) {
  nums1[k] = nums2[j];
  j--;
  k--;
}
Enter fullscreen mode Exit fullscreen mode

Because our two while loops are not nested and we never call a sort method, the time complexity improves significantly.

Time complexity: O(m + n)

Conclusion

Both approaches solve the problem, but with different trade-offs. Approach 1 is significantly easier to write and follow - two lines and you're done. But that readability comes at a cost in time complexity. Approach 2 is more involved, and more lines of code means more opportunities for bugs. But the time complexity is far better. Understanding those trade-offs is what allows us to make good decisions about which algorithmic approach to reach for.

...Day 2 coming soon

Top comments (0)