Merge Sorted Array
excerpt: Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. tags: three-pointers
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.
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]
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Constraints
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -109 <= nums1[i], nums2[i] <= 109
Thinking Process
0 1 2 3 4 5
[1,2,3,0,0,0]
[2,5,6]
0 1 2
index = 5 - 3 = 2
i = 2 to 0
Compare 6 and 3
Save 6 in last spot: [1,2,3,0,0,6]
Decrement k
Compare 5 and 3
Save 5 in the next spot pointed to by k [1,2,3,0,5,6]
Decrement k
Compare 2 and 3
Save 3 in the next spot pointed to by k [1,2,3,3,5,6]
Confused in this case, how should I copy the last number to the nums1?
|
|
Fails for the edge case: merge([2,0], 1, [1], 1)
Working Solution
|
|
To merge two sorted arrays nums1
and nums2
into a single sorted array in-place, you can follow the steps below:
- Initialize Pointers: Create three pointers, one for the current position in
nums1
(ptr1
), one for the current position innums2
(ptr2
), and one for the current position in the final merged array (current
). - Start from the End: Initialize
ptr1
tom - 1
,ptr2
ton - 1
, andcurrent
tom + n - 1
. - Compare and Merge: Compare the elements at
ptr1
andptr2
. Ifnums1[ptr1]
is greater, place it atcurrent
, else placenums2[ptr2]
atcurrent
. Decrement the respective pointers andcurrent
. - Handle Remaining Elements: If there are remaining elements in
nums2
, copy them tonums1
. - Finish:
nums1
now contains the merged sorted array.
Here’s the code:
|
|
Since you are iterating through the two given arrays once, the time complexity is (O(m + n)), where (m) and (n) are the lengths of the given arrays. The space complexity is (O(1)) as the operation is performed in-place.
|
|
|
|
Problem Classification
Array Manipulation: The problem involves manipulating and modifying arrays. Understanding how to work with arrays, including accessing elements, updating elements, and understanding array indices is crucial to solving this problem.
Sorting: The task is to merge two sorted arrays into a single sorted array. This falls into the broad category of sorting problems.
Two-pointers Technique: The problem involves comparing elements from two arrays at a time, often referred to as a “two-pointers” or “two-iterators” technique. This approach is frequently used in array manipulation problems.
In-Place Operations: The problem requires merging the second array into the first one without allocating additional space for another array. This is common in problems that require optimization of space complexity.
These classifications help narrow down the possible approaches and techniques used to solve this type of problem.
Language Agnostic Coding Drills
This provided code is a Python function to merge two sorted arrays. Given two sorted integer arrays A and B, the function merges B into A as one sorted array.
Here’s how we can break it down into smaller learning units:
Arrays (or Lists in Python): Understanding the concept of arrays or lists in Python is crucial to this problem. This includes creating, accessing, and manipulating elements in an array.
Variables and Data Types: There are integer variables in the code that keep track of indexes (a, b, write_index).
Loops (While Loop): This code contains a while loop, which is used to iterate over the elements in arrays A and B.
Conditional Statements (If and Else): There are conditional statements in this code to compare the current elements of A and B.
Index Manipulation: The solution involves manipulating indices of two arrays to merge them in a sorted manner.
Problem-Solving Approach:
Understand the problem: The task is to merge two sorted arrays. Given that the arrays are already sorted, we can leverage this fact in our solution to make the process more efficient.
Define the problem requirements: Given two sorted integer arrays A and B, merge B into A as one sorted array.
Break down the problem: The problem can be broken down into simpler tasks:
- Track the current index for both arrays that we are comparing elements from.
- Compare the current elements of A and B, and place the larger one at the current end of the merged array.
- Repeat this until all elements in B are merged into A.
Develop a solution: The pseudocode for the solution can be written as:
- Start from the end of A and B, compare the current elements a and b.
- If a > b, place a at the end of the merged array and move the pointer of A.
- If b >= a, place b at the end of the merged array and move the pointer of B.
- Repeat this process until all elements in B are merged into A.
Test the solution: The solution should be tested with various inputs to ensure it covers all scenarios. Consider edge cases such as when one or both arrays are empty, and when all elements in B are larger or smaller than all elements in A.
Targeted Drills in Python
- Arrays (or Lists in Python):
|
|
- Variables and Data Types:
|
|
- Loops (While Loop):
|
|
- Conditional Statements (If and Else):
|
|
- Index Manipulation:
|
|
Problem Specific Drill:
Now let’s combine all of these concepts into a drill specific to the problem at hand:
|
|
This drill exercises all the necessary concepts and builds up to the final solution. Each concept is demonstrated in isolation and then integrated into the final solution.