Merge Sorted Array
Explore how to merge two sorted arrays into one sorted array while maintaining non-decreasing order. This lesson helps you understand the k-way merge pattern, guiding you through the process of merging nums2 into nums1 in-place, optimizing your approach for coding interviews involving array manipulation.
We'll cover the following...
Statement
You are given two integer arrays, nums1 and nums2, both sorted in non-decreasing order. You are also given two integers, m and n, representing the number of elements in nums1 and nums2, respectively.
Your task is to merge the elements of nums2 into nums1 so that nums1 becomes a single array sorted in non-decreasing order.
The merged result is stored in nums1, which has a total length of m + n. The first m positions contain the initial elements, the last n positions are placeholders (initialized to 0), and nums2 contains the n elements to merge.
Constraints:
nums1.lengthnums2.length-
nums1[i],nums2[j]
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Merge Sorted Array
What is the output if the following arrays and values of and are given as input?
nums1 = [1, 2, 7, 92, 0, 0, 0], m = 4
nums2 = [3, 4, 5], n = 3
[1, 2, 3, 4, 5, 7, 92]
[1, 2, 7, 92, 3, 4, 5]
[3, 4, 5, 1, 2, 7, 92]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
public class MergeSorted{public static int[] mergeSorted(int[] nums1, int m, int[] nums2, int n) {// Replace this placeholder return statement with your codeint[] list = new int[]{};return list;}}