Merge Sorted Array

📋

Merge Sorted Array

Edge cases:

</>

IDE

def merge(nums1: list[int], m: int, nums2: list[int], n: int) -> None:public void merge(int[] nums1, int m, int[] nums2, int n)void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)function merge(nums1, m, nums2, n)

def merge(nums1, m, nums2, n):
    # Write your solution here
    pass

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    // Write your solution here
}

function merge(nums1, m, nums2, n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,3,0,0,0]Merging forwards overwrites elements in nums1 before they are compared.✅ Merge from the end using two pointers starting at m-1 and n-1, filling nums1 from the back.

Wrong: [0,0,0]Fails to handle m=0 case; does not copy nums2 into nums1.✅ Add condition to copy nums2 into nums1 when m=0.

Wrong: [1,2,3]Fails to merge when n=0; code overwrites or skips merge incorrectly.✅ Return early or skip merge if n=0.

Wrong: [2,2,2,0,0,0]Skips duplicates or overwrites equal elements incorrectly.✅ Handle equality in comparisons by placing nums2 element or nums1 element consistently.

Wrong: Timeout or no outputUses sorting or nested loops leading to O((m+n) log(m+n)) or worse time complexity.✅ Implement two-pointer backwards merge with O(m+n) time complexity.

✓

Test Cases

Focus on handling empty inputs and single-element arrays correctly.

Watch out for greedy merges that overwrite elements; test boundary conditions carefully.

Optimize your solution to linear time using two pointers from the end.

t1_01basic

Input{"nums1":[1,2,2,2,5,6],"m":3,"nums2":[2,5,6],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

We merge nums2 into nums1 in sorted order. Starting from the end avoids overwriting elements.

💡 Try using two pointers starting from the ends of nums1 and nums2.

💡 Use a backwards two-pointer approach to fill nums1 from the back.

💡 Compare nums1[m-1] and nums2[n-1], place the larger at nums1[m+n-1], then move pointers accordingly.

Why it failed: Basic case failed - likely overwriting elements by merging forwards. Fix by merging from the end using two pointers.

✓ Core two-pointer backwards merge logic implemented correctly.

t1_02basic

Input{"nums1":[1,1,2,2,3,3],"m":3,"nums2":[1,2,3],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

nums2 elements are all smaller; merged array is sorted ascending from smallest to largest.

💡 Remember to compare elements from the end to avoid overwriting.

💡 If nums2 element is smaller, place nums1 element at the end and move pointer.

💡 Continue until all elements from nums2 are merged into nums1.

Why it failed: Incorrect order or overwritten elements - fix by merging from the back and carefully moving pointers.

✓ Correctly merged when nums2 elements are smaller than nums1's.

t2_01edge

Input{"nums1":[1,2,3],"m":0,"nums2":[1,2,3],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

m=0 means nums1 has no valid elements; nums1 should become nums2.

💡 Check if m is zero and handle copying nums2 directly.

💡 No elements in nums1 to merge, so just copy nums2 into nums1.

💡 Ensure the merge logic handles m=0 without accessing nums1 elements.

Why it failed: Fails when m=0 - code tries to access nums1 elements that don't exist. Fix by adding condition to copy nums2 when m=0.

✓ Correctly handles empty nums1 initial elements.

t2_02edge

Input{"nums1":[1,2,3],"m":3,"nums2":[],"n":0}

Expectednull

⏱ Performance - must finish in 2000ms

n=0 means nums2 is empty; nums1 remains unchanged.

💡 If nums2 is empty, no merge needed.

💡 Check if n=0 and return early or skip merging.

💡 Ensure code does not overwrite nums1 when nums2 is empty.

Why it failed: Fails when n=0 - code overwrites nums1 or accesses nums2 elements. Fix by skipping merge if n=0.

✓ Correctly handles empty nums2 input.

t2_03edge

Input{"nums1":[2,2,2,2,2,2],"m":3,"nums2":[2,2,2],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

All elements equal; merged array contains duplicates correctly.

💡 Duplicates should be preserved in the merged array.

💡 Ensure merge logic does not skip equal elements.

💡 When elements are equal, place nums2 element first or follow consistent rule.

Why it failed: Fails to preserve duplicates - code may skip equal elements. Fix by handling equality correctly in comparisons.

✓ Duplicates preserved correctly in merged array.

t2_04edge

Input{"nums1":[-3,-2,-2,2,3],"m":2,"nums2":[-2,2,3],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

Mix of negative and positive numbers; merged array sorted correctly.

💡 Handle negative numbers correctly in comparisons.

💡 Merge from the end to avoid overwriting.

💡 Ensure final array is sorted including negative and positive values.

Why it failed: Fails to handle negative numbers correctly, resulting in wrong order. Fix comparison logic to handle all integer values.

✓ Correctly merges arrays with negative and positive numbers.

t3_01corner

Input{"nums1":[1,2,2,3,4,6],"m":3,"nums2":[2,4,6],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

Interleaved elements test; catches greedy approach that merges forwards and overwrites.

💡 Greedy forward merge overwrites nums1 elements incorrectly.

💡 Use two pointers from the end to avoid overwriting.

💡 Merge backwards comparing nums1[m-1] and nums2[n-1].

Why it failed: Greedy forward merge overwrites elements causing incorrect order. Fix by merging from the end with two pointers.

✓ Correctly merges interleaved elements using backwards two-pointer approach.

t3_02corner

Input{"nums1":[1,2,3,4],"m":3,"nums2":[4],"n":1}

Expectednull

⏱ Performance - must finish in 2000ms

Tests exact boundary condition where n=1 and m+n equals nums1 length.

💡 Check boundary conditions carefully when n=1.

💡 Ensure pointers do not go out of bounds.

💡 Merge last element of nums2 correctly at the end of nums1.

Why it failed: Off-by-one error causes last element to be misplaced or overwritten. Fix pointer indices and loop conditions.

✓ Handles exact boundary condition correctly.

t3_03corner

Input{"nums1":[-3,-2,-2,2,3],"m":2,"nums2":[-2,2,3],"n":3}

Expectednull

⏱ Performance - must finish in 2000ms

Mix of negative and positive numbers; merged array sorted correctly.

💡 Handle negative numbers correctly in comparisons.

💡 Merge from the end to avoid overwriting.

💡 Ensure final array is sorted including negative and positive values.

Why it failed: Fails to handle negative numbers correctly, resulting in wrong order. Fix comparison logic to handle all integer values.

✓ Correctly merges arrays with negative and positive numbers.

t4_01performance

Input{"nums1":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],"m":100,"nums2":[100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199],"n":100}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, m=100; O(m+n) = O(200) must complete within 2 seconds.

💡 Optimal solution is O(m+n) time using two pointers backwards.

💡 Avoid sorting or copying entire arrays.

💡 Use in-place merge from the end to achieve linear time.

Why it failed: TLE due to O((m+n) log(m+n)) sorting or O(m*n) nested loops. Fix by using two-pointer backwards merge O(m+n).

✓ Algorithm runs in O(m+n) time confirming optimal complexity.

Practice

1. You are given two strings that may contain the backspace character '#'. After processing all backspaces, you need to determine if the resulting strings are equal. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Sort both strings after removing backspaces and then compare them.

B. Use a brute force approach by building the final strings with stacks and then compare them.

C. Use dynamic programming to track the state of each character after backspaces.

D. Use two pointers starting from the end of both strings, simulating backspaces on the fly without extra space.

Solution

1. Step 1: Understand the problem constraints

   The problem requires comparing two strings after applying backspace operations, which can be done efficiently by simulating the effect of backspaces without reconstructing the entire string explicitly.

2. Step 2: Identify the optimal approach

   Using two pointers from the end of both strings allows skipping characters affected by backspaces on the fly, achieving O(n + m) time and O(1) extra space, which is optimal compared to building stacks or using DP.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two pointers from the end simulate backspaces efficiently [OK]

Hint: Two pointers from end simulate backspaces efficiently [OK]

Common Mistakes:

• Assuming DP is needed for backspace processing
• Using sorting which changes character order
• Building full strings with stacks uses extra space

2. You are given an array representing heights of vertical lines on the x-axis. You want to find two lines that together with the x-axis form a container, such that the container holds the maximum amount of water. Which algorithmic approach guarantees finding the optimal solution in O(n) time?

easy

A. Two pointers starting at opposite ends, moving the pointer at the shorter line inward.

B. Brute force by checking all pairs of lines and calculating their container area.

C. Dynamic programming to store maximum areas for subproblems of line pairs.

D. Greedy approach moving the pointer at the taller line inward to maximize area.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding two lines that maximize the container area, which depends on the minimum height and the distance between lines.

2. Step 2: Analyze algorithmic approaches

   Brute force (checking all pairs) is O(n²), dynamic programming is unnecessary and inefficient here, and moving the pointer at the taller line can miss optimal solutions. The two-pointer approach moving the pointer at the shorter line inward guarantees checking all promising pairs efficiently in O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer approach with shorter line pointer movement -> O(n) optimal [OK]

Hint: Two pointers move inward from ends, shorter line pointer moves [OK]

Common Mistakes:

• Moving pointer at taller line instead of shorter line
• Using DP unnecessarily
• Assuming greedy on taller line pointer works

3. You are given an unsorted array and a number k. The task is to find a subset of k elements such that the difference between the maximum and minimum elements in this subset is minimized. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Use a greedy approach by always picking the smallest element and then the next closest elements without sorting.

B. Sort the array and use a sliding window of size k to find the minimum difference between the first and last elements in each window.

C. Use dynamic programming to store minimum differences for all subsets of size k.

D. Use brute force to generate all subsets of size k and compute their differences.

Solution

1. Step 1: Understand the problem constraints

   Finding a subset of k elements with minimum max-min difference requires contiguous elements after sorting.

2. Step 2: Identify the optimal approach

   Sorting the array places elements in ascending order, so the minimum difference subset must be a contiguous window of size k. Sliding window efficiently checks all such windows.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + sliding window is classic for minimum range in subsets [OK]

Hint: Sort then slide window to find minimal range [OK]

Common Mistakes:

• Trying greedy without sorting misses optimal subsets
• Using DP unnecessarily complicates the problem
• Brute force is correct but impractical

4. Examine the following code snippet for the 3Sum Smaller problem. It is almost correct but contains one subtle bug. Identify the line with the bug.

medium

A. Line 2: nums.sort()

B. Line 7: if nums[i] + nums[i + 1] + nums[i + 2] >= target:

C. Line 9: while left <= right:

D. Line 12: count += right - left

Solution

1. Step 1: Understand pointer loop condition

   The two-pointer loop should run while left < right to avoid pointers crossing and invalid indices.

2. Step 2: Identify bug in loop condition

   Using while left <= right allows left and right to be equal, causing curr_sum to be computed with same index twice, leading to incorrect counts or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Changing to while left < right fixes the bug [OK]

Hint: Two-pointer loops must use strict inequality to avoid overlap [OK]

Common Mistakes:

• Using <= instead of < in two-pointer loops
• Forgetting to sort before two pointers
• Incrementing count incorrectly

5. Suppose the array is not sorted and you want to remove duplicates in-place with O(1) extra space. Which modification to the two-pointer approach is correct?

hard

A. Scan the array multiple times with nested loops to remove duplicates.

B. Use two pointers without sorting, comparing elements directly to remove duplicates.

C. Use a hash set to track duplicates and overwrite duplicates in-place.

D. Sort the array first, then apply the two-pointer approach.

Solution

1. Step 1: Understand constraints

   Two-pointer approach relies on sorted array to detect duplicates in one pass.

2. Step 2: Identify correct modification

   Sorting first ensures duplicates are adjacent, enabling two-pointer removal in O(n log n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting enables two-pointer approach on unsorted input [OK]

Hint: Two-pointer requires sorted array; sort first if unsorted [OK]

Common Mistakes:

• Trying two-pointer without sorting
• Using extra space violating constraints