3Sum Smaller

🎯

3Sum Smaller

mediumTWO_POINTERGoogleFacebook

Imagine you want to find how many triplets of prices in a shopping list are cheaper than a certain budget, helping you quickly estimate affordable combinations.

💡 This problem asks for counting triplets with sums less than a target. Beginners often struggle because naive solutions are too slow and they miss how sorting and two pointers can efficiently count valid triplets without enumerating all.

📋

Problem Statement

Given an integer array nums and an integer target, return the number of index triplets i, j, k with 0 <= i < j < k < nums.length such that nums[i] + nums[j] + nums[k] < target.

1 ≤ nums.length ≤ 10^5-10^9 ≤ nums[i] ≤ 10^9-10^9 ≤ target ≤ 10^9

💡

Example

Input"nums = [-2, 0, 1, 3], target = 2"

Output2

The triplets (-2, 0, 1) and (-2, 0, 3) both have sums less than 2: -1 and 1 respectively, so the count is 2.

• Empty array → 0
• Array with less than 3 elements → 0
• All elements equal and sum less than target → count all triplets
• All elements equal and sum greater or equal to target → 0

⚠️

Common Mistakes

Not sorting the array before two pointers

Two-pointer logic fails, incorrect counts or infinite loops

✅ Always sort the array before applying two-pointer technique

Using <= instead of < in while loop for pointers

Pointers may cross or cause invalid index access

✅ Use while(left < right) to ensure valid pairs

Incrementing count by 1 instead of (right - left)

Undercounts valid triplets, failing efficiency and correctness

✅ Add (right - left) when sum < target to count all valid pairs at once

Not handling arrays with less than 3 elements

Index errors or incorrect counts

✅ Check array length and return 0 if less than 3

🧠

Brute Force (Triple Nested Loops)

💡 Starting with brute force helps understand the problem fully by enumerating all triplets, even though it's inefficient for large inputs.

Intuition

Check every possible triplet and count those whose sum is less than the target.

Algorithm

1. Initialize count to 0.
2. Use three nested loops to pick every triplet (i, j, k) with i < j < k.
3. Calculate the sum of nums[i], nums[j], nums[k].
4. If sum < target, increment count.
5. Return count after all triplets are checked.

💡 The triple nested loops make it easy to understand but hard to optimize without sorting or pointers.

</>

Code

def threeSumSmaller(nums, target):
    count = 0
    n = len(nums)
    for i in range(n - 2):
        for j in range(i + 1, n - 1):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] < target:
                    count += 1
    return count

# Driver code
if __name__ == '__main__':
    print(threeSumSmaller([-2, 0, 1, 3], 2))  # Output: 2

Line Notes

count = 0Initialize counter to track valid triplets

for i in range(n - 2)Outer loop picks first element of triplet

for j in range(i + 1, n - 1)Middle loop picks second element after i

for k in range(j + 1, n)Inner loop picks third element after j

if nums[i] + nums[j] + nums[k] < targetCheck if current triplet sum is less than target

count += 1Increment count for valid triplet

return countReturn total count after checking all triplets

public class Solution {
    public static int threeSumSmaller(int[] nums, int target) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] + nums[k] < target) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 0, 1, 3};
        System.out.println(threeSumSmaller(nums, 2)); // Output: 2
    }
}

Line Notes

int count = 0;Initialize count to zero

for (int i = 0; i < n - 2; i++)Outer loop selects first element

for (int j = i + 1; j < n - 1; j++)Second loop selects second element after i

for (int k = j + 1; k < n; k++)Innermost loop selects third element after j

if (nums[i] + nums[j] + nums[k] < target)Check if sum of triplet is less than target

count++;Increment count for valid triplet

return count;Return total count after all triplets checked

#include <iostream>
#include <vector>
using namespace std;

int threeSumSmaller(vector<int>& nums, int target) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] < target) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {-2, 0, 1, 3};
    cout << threeSumSmaller(nums, 2) << endl; // Output: 2
    return 0;
}

Line Notes

int count = 0;Initialize count to track valid triplets

for (int i = 0; i < n - 2; i++)Outer loop picks first element

for (int j = i + 1; j < n - 1; j++)Second loop picks second element after i

for (int k = j + 1; k < n; k++)Inner loop picks third element after j

if (nums[i] + nums[j] + nums[k] < target)Check if sum of triplet is less than target

count++;Increment count for valid triplet

return count;Return total count after checking all triplets

function threeSumSmaller(nums, target) {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                if (nums[i] + nums[j] + nums[k] < target) {
                    count++;
                }
            }
        }
    }
    return count;
}

// Test
console.log(threeSumSmaller([-2, 0, 1, 3], 2)); // Output: 2

Line Notes

let count = 0;Initialize count to zero

for (let i = 0; i < n - 2; i++)Outer loop picks first element

for (let j = i + 1; j < n - 1; j++)Second loop picks second element after i

for (let k = j + 1; k < n; k++)Inner loop picks third element after j

if (nums[i] + nums[j] + nums[k] < target)Check if sum of triplet is less than target

count++;Increment count for valid triplet

return count;Return total count after checking all triplets

⏱

Complexity

TimeO(n^3)

SpaceO(1)

Three nested loops each iterate up to n, resulting in O(n^3) time. No extra space besides counters.

💡 For n=20, this means 20*19*18 = 6840 operations, which is okay, but for n=1000, it's 1 billion operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sorting + Two Pointers

💡 Sorting the array allows us to use two pointers to efficiently count valid triplets without enumerating all, drastically improving performance.

Intuition

Fix one element, then use two pointers to find pairs that together with the fixed element have sum less than target.

Algorithm

1. Sort the array.
2. Initialize count to 0.
3. For each index i from 0 to n-3, fix nums[i].
4. Set two pointers: left = i+1, right = n-1.
5. While left < right:
6. Calculate current sum = nums[i] + nums[left] + nums[right].
7. If sum < target, all elements between left and right form valid triplets with i, so add (right - left) to count and move left forward.
8. Else, move right backward to reduce sum.
9. Return count.

💡 The key insight is that when sum < target, all pairs between left and right pointers are valid, so we count them at once.

</>

Code

def threeSumSmaller(nums, target):
    nums.sort()
    count = 0
    n = len(nums)
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]
            if curr_sum < target:
                count += right - left
                left += 1
            else:
                right -= 1
    return count

# Driver code
if __name__ == '__main__':
    print(threeSumSmaller([-2, 0, 1, 3], 2))  # Output: 2

Line Notes

nums.sort()Sorting enables two-pointer technique

for i in range(n - 2)Fix first element of triplet

left, right = i + 1, n - 1Initialize two pointers for remaining elements

while left < rightLoop until pointers meet

curr_sum = nums[i] + nums[left] + nums[right]Calculate current triplet sum

if curr_sum < targetIf sum less than target, all pairs between left and right are valid

count += right - leftAdd all valid pairs at once

left += 1Move left pointer forward to find new pairs

else: right -= 1Sum too large, move right pointer backward to reduce sum

return countReturn total count of valid triplets

import java.util.Arrays;

public class Solution {
    public static int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1, right = n - 1;
            while (left < right) {
                int currSum = nums[i] + nums[left] + nums[right];
                if (currSum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 0, 1, 3};
        System.out.println(threeSumSmaller(nums, 2)); // Output: 2
    }
}

Line Notes

Arrays.sort(nums);Sort array to apply two-pointer approach

for (int i = 0; i < n - 2; i++)Fix first element

int left = i + 1, right = n - 1;Initialize two pointers

while (left < right)Loop until pointers cross

int currSum = nums[i] + nums[left] + nums[right];Calculate sum of triplet

if (currSum < target)If sum less than target, count all pairs between left and right

count += right - left;Add number of valid pairs at once

left++;Move left pointer forward

else { right--; }Sum too large, move right pointer backward

return count;Return total count

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int threeSumSmaller(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            int currSum = nums[i] + nums[left] + nums[right];
            if (currSum < target) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {-2, 0, 1, 3};
    cout << threeSumSmaller(nums, 2) << endl; // Output: 2
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array for two-pointer technique

for (int i = 0; i < n - 2; i++)Fix first element

int left = i + 1, right = n - 1;Initialize two pointers

while (left < right)Loop until pointers meet

int currSum = nums[i] + nums[left] + nums[right];Calculate current triplet sum

if (currSum < target)If sum less than target, count all pairs between left and right

count += right - left;Add all valid pairs at once

left++;Move left pointer forward

else { right--; }Sum too large, move right pointer backward

return count;Return total count

function threeSumSmaller(nums, target) {
    nums.sort((a, b) => a - b);
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        let left = i + 1, right = n - 1;
        while (left < right) {
            const currSum = nums[i] + nums[left] + nums[right];
            if (currSum < target) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
    }
    return count;
}

// Test
console.log(threeSumSmaller([-2, 0, 1, 3], 2)); // Output: 2

Line Notes

nums.sort((a, b) => a - b);Sort array to enable two-pointer approach

for (let i = 0; i < n - 2; i++)Fix first element

let left = i + 1, right = n - 1;Initialize two pointers

while (left < right)Loop until pointers meet

const currSum = nums[i] + nums[left] + nums[right];Calculate sum of triplet

if (currSum < target)If sum less than target, count all pairs between left and right

count += right - left;Add all valid pairs at once

left++;Move left pointer forward

else { right--; }Sum too large, move right pointer backward

return count;Return total count

⏱

Complexity

TimeO(n^2)

SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n). The outer loop runs n times, and the inner two-pointer loop runs O(n) total per iteration, resulting in O(n^2) time.

💡 For n=1000, this means about 1 million operations, which is efficient enough for interviews.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for this problem.

🧠

Sorting + Two Pointers with Early Termination

💡 An optimization that stops early when the smallest possible sum with the fixed element is already greater or equal to target, saving unnecessary iterations.

Intuition

If the sum of the fixed element and the next two smallest elements is >= target, no further triplets with this fixed element can be valid.

Algorithm

1. Sort the array.
2. Initialize count to 0.
3. For each index i from 0 to n-3:
4. If nums[i] + nums[i+1] + nums[i+2] >= target, break early as no further triplets can be valid.
5. Set left = i+1, right = n-1.
6. While left < right:
7. Calculate sum = nums[i] + nums[left] + nums[right].
8. If sum < target, add (right - left) to count and move left forward.
9. Else, move right backward.
10. Return count.

💡 Early termination avoids unnecessary loops when no valid triplets remain, improving runtime in some cases.

</>

Code

def threeSumSmaller(nums, target):
    nums.sort()
    count = 0
    n = len(nums)
    for i in range(n - 2):
        if nums[i] + nums[i + 1] + nums[i + 2] >= target:
            break
        left, right = i + 1, n - 1
        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]
            if curr_sum < target:
                count += right - left
                left += 1
            else:
                right -= 1
    return count

# Driver code
if __name__ == '__main__':
    print(threeSumSmaller([-2, 0, 1, 3], 2))  # Output: 2

Line Notes

nums.sort()Sort array to enable two-pointer technique

for i in range(n - 2)Fix first element

if nums[i] + nums[i + 1] + nums[i + 2] >= targetEarly termination check to skip unnecessary iterations

breakStop loop early if no valid triplets possible

left, right = i + 1, n - 1Initialize two pointers

while left < rightLoop until pointers meet

curr_sum = nums[i] + nums[left] + nums[right]Calculate current triplet sum

if curr_sum < targetIf sum less than target, count all pairs between left and right

count += right - leftAdd all valid pairs at once

left += 1Move left pointer forward

else: right -= 1Sum too large, move right pointer backward

return countReturn total count

import java.util.Arrays;

public class Solution {
    public static int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] + nums[i + 1] + nums[i + 2] >= target) {
                break;
            }
            int left = i + 1, right = n - 1;
            while (left < right) {
                int currSum = nums[i] + nums[left] + nums[right];
                if (currSum < target) {
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {-2, 0, 1, 3};
        System.out.println(threeSumSmaller(nums, 2)); // Output: 2
    }
}

Line Notes

Arrays.sort(nums);Sort array for two-pointer approach

for (int i = 0; i < n - 2; i++)Fix first element

if (nums[i] + nums[i + 1] + nums[i + 2] >= target)Early termination condition

break;Stop loop early if no valid triplets remain

int left = i + 1, right = n - 1;Initialize two pointers

while (left < right)Loop until pointers meet

int currSum = nums[i] + nums[left] + nums[right];Calculate current triplet sum

if (currSum < target)If sum less than target, count all pairs between left and right

count += right - left;Add all valid pairs at once

left++;Move left pointer forward

else { right--; }Sum too large, move right pointer backward

return count;Return total count

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int threeSumSmaller(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] + nums[i + 1] + nums[i + 2] >= target) {
            break;
        }
        int left = i + 1, right = n - 1;
        while (left < right) {
            int currSum = nums[i] + nums[left] + nums[right];
            if (currSum < target) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
    }
    return count;
}

int main() {
    vector<int> nums = {-2, 0, 1, 3};
    cout << threeSumSmaller(nums, 2) << endl; // Output: 2
    return 0;
}

Line Notes

sort(nums.begin(), nums.end());Sort array for two-pointer technique

for (int i = 0; i < n - 2; i++)Fix first element

if (nums[i] + nums[i + 1] + nums[i + 2] >= target)Early termination condition

break;Stop loop early if no valid triplets remain

int left = i + 1, right = n - 1;Initialize two pointers

while (left < right)Loop until pointers meet

int currSum = nums[i] + nums[left] + nums[right];Calculate current triplet sum

if (currSum < target)If sum less than target, count all pairs between left and right

count += right - left;Add all valid pairs at once

left++;Move left pointer forward

else { right--; }Sum too large, move right pointer backward

return count;Return total count

function threeSumSmaller(nums, target) {
    nums.sort((a, b) => a - b);
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n - 2; i++) {
        if (nums[i] + nums[i + 1] + nums[i + 2] >= target) {
            break;
        }
        let left = i + 1, right = n - 1;
        while (left < right) {
            const currSum = nums[i] + nums[left] + nums[right];
            if (currSum < target) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
    }
    return count;
}

// Test
console.log(threeSumSmaller([-2, 0, 1, 3], 2)); // Output: 2

Line Notes

nums.sort((a, b) => a - b);Sort array for two-pointer approach

for (let i = 0; i < n - 2; i++)Fix first element

if (nums[i] + nums[i + 1] + nums[i + 2] >= target)Early termination condition

break;Stop loop early if no valid triplets remain

let left = i + 1, right = n - 1;Initialize two pointers

while (left < right)Loop until pointers meet

const currSum = nums[i] + nums[left] + nums[right];Calculate current triplet sum

if (currSum < target)If sum less than target, count all pairs between left and right

count += right - left;Add all valid pairs at once

left++;Move left pointer forward

else { right--; }Sum too large, move right pointer backward

return count;Return total count

⏱

Complexity

TimeO(n^2)

SpaceO(1) or O(n) depending on sorting

Same as previous approach but with early break to skip unnecessary iterations.

💡 Early termination can save time when array is large and target is small, but worst-case remains O(n^2).

Interview Verdict: Accepted

This micro-optimization shows deeper understanding and can improve runtime in some cases.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the two-pointer approach (Approach 2) is the best balance of clarity and efficiency to code.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Two Pointers	O(n^2)	O(1) or O(n) for sorting	No	N/A	Code this approach in 95% of interviews
3. Sorting + Two Pointers with Early Termination	O(n^2) best case better	O(1) or O(n)	No	N/A	Mention as optimization if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to communicate your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force approach and its inefficiency.Step 3: Introduce sorting and two pointers to optimize.Step 4: Code the two-pointer solution carefully.Step 5: Discuss possible optimizations like early termination.Step 6: Test your code with edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force, coding accuracy, and handling edge cases.

Common Follow-ups

• What if we want to return the triplets instead of count? → Use similar two-pointer approach but store triplets.
• How to handle duplicates? → Skip duplicates after sorting to avoid repeated triplets.

💡 Follow-ups test your ability to adapt the solution and handle real-world constraints like duplicates or output format.

🔍

Pattern Recognition

When to Use

1) Problem asks for triplets or k-sum combinations; 2) Counting or finding sums less than/greater than target; 3) Input array can be sorted; 4) Two pointers can be applied to reduce complexity.

Signature Phrases

triplets with sum less than targetcount number of tripletssorted array and two pointers

NOT This Pattern When

Problems requiring subsets without ordering or those needing dynamic programming for optimization

Similar Problems

3Sum - find triplets that sum to zero3Sum Closest - find triplet sum closest to target

Practice

1. Consider the following code snippet implementing the 3Sum Closest algorithm. What is the returned value when the input is nums = [-1, 2, 1, -4] and target = 1?

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == target:
                return current_sum
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1
            else:
                right -= 1
    return closest_sum

print(threeSumClosest([-1, 2, 1, -4], 1))

easy

A. 1

B. 4

C. -1

D. 2

Solution

1. Step 1: Sort the array

   Sorted nums = [-4, -1, 1, 2]

2. Step 2: Trace iterations

   i=0: left=1, right=3 current_sum = -4 + (-1) + 2 = -3 (closest_sum init = -4+-1+1 = -4) Update closest_sum to -3 current_sum < target(1), left++ -> left=2 current_sum = -4 + 1 + 2 = -1 Update closest_sum to -1 current_sum < target, left++ -> left=3 (loop ends) i=1: left=2, right=3 current_sum = -1 + 1 + 2 = 2 abs(2-1)=1 < abs(-1-1)=2, update closest_sum=2 current_sum > target, right-- -> right=2 (loop ends) Return closest_sum = 2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected closest sum 2 [OK]

Hint: Sorting and pointer moves yield closest sum 2 [OK]

Common Mistakes:

• Returning initial sum without updates
• Off-by-one pointer increments
• Confusing current_sum with closest_sum

2. The following code attempts to implement the optimal 4Sum solution. Which line contains a subtle bug that can cause quadruplets with repeated indices to be included, violating problem constraints?

from typing import List
from collections import defaultdict

def fourSum(nums: List[int], target: int) -> List[List[int]]:
    nums.sort()
    n = len(nums)
    two_sum_map = defaultdict(list)
    res = set()
    for i in range(n):
        for j in range(i + 1, n):
            two_sum_map[nums[i] + nums[j]].append((i, j))
    for sum1 in two_sum_map:
        sum2 = target - sum1
        if sum2 not in two_sum_map:
            continue
        list1 = two_sum_map[sum1]
        list2 = two_sum_map[sum2]
        for (i, j) in list1:
            for (k, l) in list2:
                # BUG: Missing index overlap check
                quad = tuple(sorted([nums[i], nums[j], nums[k], nums[l]]))
                res.add(quad)
    return [list(quad) for quad in sorted(res)]

medium

A. Line that combines pairs into quadruplets without checking index overlap.

B. Line that appends pairs to two_sum_map.

C. Line that sorts the input array.

D. Line that returns the final list of quadruplets.

Solution

1. Step 1: Identify where index overlap is checked

   The code must ensure indices i,j,k,l are distinct to avoid repeated elements.

2. Step 2: Locate missing check

   The nested loops combining pairs lack any condition verifying indices are unique, allowing invalid quadruplets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing index overlap check causes subtle bug [OK]

Hint: Check index overlap before adding quadruplets [OK]

Common Mistakes:

• Forgetting index uniqueness check in pair combinations

3. Consider the following buggy code for merging two sorted arrays in-place. Which line contains the subtle bug that causes missing elements in the final merged array?

def merge(nums1, m, nums2, n):
    i = m - 1
    j = n - 1
    k = m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    # Missing copying remaining nums2 elements

nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)

medium

A. Line 12: Missing while loop to copy remaining nums2 elements

B. Line 9: nums1[k] = nums2[j]

C. Line 4: i = m - 1

D. Line 7: if nums1[i] > nums2[j]:

Solution

1. Step 1: Analyze the main merging loop

   The main loop merges elements from the back correctly but stops when either i or j is negative.

2. Step 2: Identify missing step

   There is no loop copying remaining elements from nums2 if any remain, causing missing elements in nums1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Without copying leftover nums2 elements, final array is incomplete [OK]

Hint: Always copy leftover nums2 elements after main loop [OK]

Common Mistakes:

• Forgetting leftover nums2 copy
• Overwriting nums1 elements too early

4. Identify the bug in the following code snippet for removing elements equal to val from nums in-place:

medium

A. The end pointer is not decremented after swapping, causing infinite loop

B. The start pointer is incremented even when a swap occurs

C. The condition in the while loop should be start < end, not start <= end

D. Swapping elements without checking if nums[end] is also val

Solution

1. Step 1: Analyze pointer updates after swap

   After swapping nums[start] and nums[end], end must be decremented to exclude the swapped val at the end.

2. Step 2: Consequence of missing end decrement

   Without end--, the loop may repeatedly swap the same elements, causing infinite loop or incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing end decrement after swap breaks loop progress [OK]

Hint: Always decrement end after swapping val to end [OK]

Common Mistakes:

• Forgetting to decrement end after swap
• Incrementing start incorrectly after swap

5. Suppose the 4Sum problem is modified so that elements can be reused multiple times in quadruplets (i.e., indices can repeat). Which modification to the optimal hash map approach correctly handles this variant?

hard

A. Remove the index overlap check and allow all pairs to combine freely.

B. Use the same hash map approach but skip sorting the array to allow duplicates.

C. Modify the pair combination step to allow pairs with overlapping indices and remove index checks, but ensure quadruplets are sorted and unique.

D. Switch to brute force four nested loops since hash map approach cannot handle reuse.

Solution

1. Step 1: Understand reuse means indices can repeat

   Index overlap check must be removed or relaxed to allow repeated elements.

2. Step 2: Adjust pair combination logic

   Allow pairs with overlapping indices but still sort quadruplets and use a set to avoid duplicates.

3. Step 3: Evaluate other options

   Removing sorting breaks duplicate handling; brute force is inefficient; simply removing checks without sorting leads to duplicates.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allow index overlap but keep sorting and deduplication [OK]

Hint: Allow index overlap but keep sorting and deduplication [OK]

Common Mistakes:

• Removing sorting causes duplicates
• Assuming brute force is only solution