Merge Sorted Array
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Merge two sorted lists into the first one, which has spare empty room at its end.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Merging from the front would overwrite values of the first list. What if you start from the back?
- Hint 2The largest remaining value of the two lists belongs in the last free slot.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Two queues of children, each sorted by height, must become one queue standing in a hall that has empty floor space only at the far end. If you start placing the shortest at the front you would push people around. Instead start from the far end: the tallest child of the two queues goes to the last spot, then the next tallest, and so on. Nobody gets disturbed.
- The obvious way
Copy everything into a new list and sort: needs extra memory and extra time.
- The key insight
The free room is at the back, so fill from the back. Compare the biggest unplaced value of each list and write the bigger one into the last free slot, then step inward. Writes land only on free slots or on values already copied, so nothing is lost.
- The algorithm
- Point at the last real value of each list, and at the very last slot of the first list.
- Compare the two pointed values; write the bigger one into the last free slot.
- Move the pointer of the list you took from, and the slot pointer, one step back.
- Stop when the second list is used up; the rest of the first list is already in place.
Watch it run
Examplefirst = [1, 2, 3, _, _, _], second = [2, 5, 6]
Biggest of each list: 3 and 6. The 6 is bigger: place it in the last slot.
first = [1, 2, 3, _, _, 6]
Where people slip
- Loop on the second list only: when it is used up the rest of the first list is already correct.
- Check a >= 0 before reading nums1[a].
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def merge(nums1, m, nums2, n):
a = m - 1 # last real value of nums1
b = n - 1 # last value of nums2
slot = m + n - 1 # last free slot of nums1
while b >= 0:
if a >= 0 and nums1[a] > nums2[b]:
nums1[slot] = nums1[a]
a -= 1
else:
nums1[slot] = nums2[b]
b -= 1
slot -= 1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.