Today, I tackled my first LeetCode challenge to improve my understanding of algorithms with the help of my AI friend, Claude. The problem seemed straightforward: merge two sorted arrays into one. The catch? I had to modify the first array in-place instead of returning a new one.
The Problem
We're given two sorted arrays: nums1 and nums2. nums1 has extra space (filled with zeros) to accommodate nums2. We also get the actual lengths of both arrays (m and n). The challenge is to merge these arrays in sorted order, directly modifying nums1.
Example:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Expected: [1,2,2,3,5,6]
The Learning Journey
Initially, I struggled with the approach. Claude noticed my confusion and suggested something counterintuitive: "Let's start from the end of the arrays." This was my first aha moment. Instead of trying to merge from the beginning (which would require shifting elements), we could use those zero placeholders in nums1 to our advantage.
pointer1 = m - 1 // Last real element in nums1
pointer2 = n - 1 // Last element in nums2
pointer3 = m + n - 1 // Last position in combined array
Where I really got stuck was understanding the while loop logic I intuitively wanted to use. I went to Claude and explained my logic and together we arrived at:
Compare the last elements of both actual arrays
Place the larger one at the end of nums1
Move the relevant pointers backward
Repeat until we've placed all nums2 elements
The Breakthrough
What finally made it click was seeing the code state at each iteration. Here's what I learned about approaching merge sort problems:
When merging sorted arrays in-place, work backwards
Use multiple pointers to track positions
Compare elements and place them from largest to smallest
Keep track of which elements have been placed by moving pointers
Final Thoughts
What started as a confusing algorithm turned into a valuable lesson about array manipulation. More importantly, leveraging Claude as a guide(not a ‘do this challenge for me’ bot) helped me understand that sometimes the best approach isn't the most obvious one. Starting from the end meant we never had to worry about overwriting values we still needed.
Tomorrow's challenge awaits; but until then, I think I’ll have Claude recommend a small learning project to apply this algorithm!