Merge Sorted Array
Two sorted guest lists have to become one. nums1 holds m guests in sorted order, followed by n slots set to 0 that are only placeholders for the newcomers. nums2 holds the n newcomers in sorted order. Put everyone into a single sorted list of m + n values and return it. Equal values may come in either order, and a real 0 can appear among the guests and the newcomers. Limits: m >= 0, n >= 0, 1 <= m + n <= 600000, nums1.length = m + n, nums2.length = n, -1000000000 <= value <= 1000000000. Think about: which end of nums1 has room that nothing is using yet? Example (nums1 = [2,6,9,0,0], m = 3, nums2 = [4,5], n = 2): guests 2, 6, 9 and newcomers 4, 5 the 4 and the 5 both slot in between the 2 and the 6 answer: [2, 4, 5, 6, 9]
You have two sorted lists, and the first one has empty room waiting at its end so the merged list can live there. Interviewers like it because the obvious left-to-right merge keeps overwriting values it hasn't read yet. The classic trap is the finish: when one side runs out, the other side's leftovers still have to land in the right place. Expect up to 600,000 values in total, each from -1,000,000,000 to 1,000,000,000.
Examples
You write
merge_sorted_array(nums1: List[int], m: int, nums2: List[int], n: int)
Example 1
- Input
- nums1 = [2,6,9,0,0], m = 3, nums2 = [4,5], n = 2
- returns
- [2,4,5,6,9]
Example 2
- Input
- nums1 = [0,0], m = 0, nums2 = [2,5], n = 2
- returns
- [2,5]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Merge Sorted Array ready to code. It is free, and the editor needs no account.
The pattern behind it
Two Pointers
I reach for it when
- The array is sorted, or you can sort it.
- You need a pair, a triple or a palindrome.
Say this before you type. Say what each pointer means and what a move to the left or right rules out.
All 26 Two Pointers problemsArrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.