How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Merge two sorted arrays in-place | Meta Coding Question

Quick Overview

Merge two sorted arrays in-place evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Merge two sorted arrays in-place

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

##### Question You are given two sorted integer arrays `nums1` and `nums2`, both sorted in non-decreasing order. - `nums1` has length `m + n`. The first `m` elements hold the sorted data; the last `n` elements are placeholders (for example, zeros) and should be ignored. - `nums2` has length `n` and holds `n` sorted elements. Merge `nums2` into `nums1` so that `nums1` becomes a single array of length `m + n` sorted in non-decreasing order. The interviewer probes the following: 1. **Core merge.** Perform the merge **in-place** inside `nums1`, using only **O(1)** additional space (you may not allocate a new array proportional to the input) and **O(m + n)** time. 2. **Algorithm and direction.** Describe your approach in detail and explain why merging from the *end* (filling the largest elements into the back of `nums1` first) lets you avoid overwriting unprocessed data. Coding may or may not be required — be ready to walk through the logic verbally either way. 3. **Complexity analysis.** State and justify the time and space complexity of your solution. 4. **Edge cases.** Discuss and test cases such as: `nums2` empty (`n = 0`), `nums1` empty (`m = 0`), all elements equal, and when every element of one array is strictly less than every element of the other (so one array is exhausted before the other).

Quick Answer: Merge two sorted arrays in-place evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given two integer arrays `nums1` and `nums2`, both sorted in non-decreasing order, along with two integers `m` and `n`. - `nums1` has length `m + n`. The first `m` elements hold the sorted data; the last `n` slots are placeholders (e.g. zeros) and should be ignored. - `nums2` has length `n` and holds `n` sorted elements. Merge `nums2` into `nums1` so that `nums1` becomes a single array of length `m + n` sorted in non-decreasing order. Do the merge **in-place** inside `nums1`, using only **O(1)** extra space and **O(m + n)** time. Return the merged `nums1`. The key insight is to fill `nums1` from the **back**: by writing the largest remaining element into the last open slot and moving inward, you never overwrite an element of `nums1` you have not yet read, so no temporary copy is needed. **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] ``` **Example 3** ``` Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] ```

Constraints

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 400
-10^9 <= nums1[i], nums2[j] <= 10^9
The first m elements of nums1 and all of nums2 are sorted non-decreasing

Examples

Input: ([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3)

Expected Output: [1, 2, 2, 3, 5, 6]

Explanation: Standard interleave: merging [1,2,3] and [2,5,6] yields [1,2,2,3,5,6].

Input: ([1], 1, [], 0)

Expected Output: [1]

Explanation: nums2 is empty (n=0); nums1 is already complete and unchanged.

Input: ([0], 0, [1], 1)

Expected Output: [1]

Explanation: nums1 has no real elements (m=0); the i>=0 guard prevents reading the placeholder, and nums2 fills the slot.

Input: ([2, 2, 2, 0, 0, 0], 3, [2, 2, 2], 3)

Expected Output: [2, 2, 2, 2, 2, 2]

Explanation: All elements equal; ties are handled consistently and the result stays sorted.

Input: ([4, 5, 6, 0, 0, 0], 3, [1, 2, 3], 3)

Expected Output: [1, 2, 3, 4, 5, 6]

Explanation: Every element of nums2 is smaller, so nums1's data is pushed entirely to the back first.

Input: ([1, 2, 3, 0, 0, 0], 3, [4, 5, 6], 3)

Expected Output: [1, 2, 3, 4, 5, 6]

Explanation: Every element of nums2 is larger; nums2 fills the tail while the nums1 prefix needs no movement.

Input: ([-5, -3, 0, 0, 0], 2, [-10, -2, 7], 3)

Expected Output: [-10, -5, -3, -2, 7]

Explanation: Negative values merge correctly across both arrays.

Hints

A forward merge into nums1[0] would overwrite elements of nums1 you have not yet compared. Which direction avoids that?
Use three pointers: i at the last real element of nums1 (index m-1), j at the last element of nums2 (index n-1), and k at the last slot of nums1 (index m+n-1). Write the larger of nums1[i] and nums2[j] into position k.
Loop only while j >= 0. Once nums2 is exhausted, any remaining nums1 prefix is already in its correct place, so no extra copying is needed. Guard the read with i >= 0 to handle the m = 0 case.

Quick Overview