3Sum Smaller

📋

3Sum Smaller

Edge cases:

</>

IDE

def threeSumSmaller(nums: list[int], target: int) -> int:public int threeSumSmaller(int[] nums, int target)int threeSumSmaller(vector<int>& nums, int target)function threeSumSmaller(nums, target)

def threeSumSmaller(nums, target):
    # Write your solution here
    pass

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int threeSumSmaller(vector<int>& nums, int target) {
    // Write your solution here
    return 0;
}

function threeSumSmaller(nums, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Counts triplets with sum equal to targetUsing <= instead of < in sum comparison✅ Change condition from sum <= target to sum < target

Wrong: Under-count due to off-by-one in two-pointer incrementsNot incrementing count by (right - left) when sum < target✅ Increment count by (right - left) and move left pointer forward

Wrong: Overcount or undercount when array length < 3Not checking array length before processing✅ Return 0 immediately if length < 3

Wrong: TLE on large inputsUsing brute force O(n^3) approach✅ Implement sorting + two-pointer O(n^2) solution

Wrong: Misses triplets when all elements are equal and sum < targetSkipping duplicates or incorrect counting logic✅ Count all combinations n choose 3 when sum < target without skipping duplicates

✓

Test Cases

Handle base cases like empty or too small arrays before main logic.

Check strict inequality and pointer movement carefully to avoid off-by-one errors.

Optimize your solution to O(n^2) by sorting and using two pointers.

t1_01basic

Input{"nums":[-2,0,1,3],"target":2}

Expected2

⏱ Performance - must finish in 2000ms

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

💡 Sort the array and use two pointers to find triplets efficiently.

💡 Fix the first element and use two pointers to find pairs with sum less than target minus first element.

💡 For each fixed i, move left and right pointers to count all valid pairs without checking each triplet individually.

Why it failed: Incorrect count indicates failure to correctly count all triplets with sum less than target. Fix by implementing two-pointer approach after sorting and counting pairs properly.

✓ Correctly counts all triplets with sum less than target using two-pointer technique.

t1_02basic

Input{"nums":[-2,0,1,3],"target":4}

Expected3

⏱ Performance - must finish in 2000ms

Triplets with sums less than 4 are (-2,0,1) = -1, (-2,0,3) = 1, and (-2,1,3) = 2, total 3 triplets.

💡 Remember to sort the array before applying two pointers.

💡 For each fixed element, count pairs with sum less than target minus fixed element.

💡 Increment count by right-left pointer difference when sum condition is met.

Why it failed: Wrong output means pairs are not counted correctly for each fixed element. Fix by ensuring two-pointer counting logic increments count by (right - left) when sum < target.

✓ Correctly counts triplets by combining sorting and two-pointer counting.

t2_01edge

Input{"nums":[],"target":5}

Expected0

⏱ Performance - must finish in 2000ms

Empty array has no triplets, so count is 0.

💡 Check if array length is less than 3 before processing.

💡 Return 0 immediately if not enough elements for a triplet.

💡 Handle empty or very small arrays as base cases.

Why it failed: Code does not handle empty or small arrays properly, causing errors or wrong counts. Fix by adding a length check and returning 0 if length < 3.

✓ Properly returns 0 for empty or too small arrays.

t2_02edge

Input{"nums":[1],"target":10}

Expected0

⏱ Performance - must finish in 2000ms

Array with less than 3 elements cannot form triplets, so count is 0.

💡 Check array length before attempting to find triplets.

💡 Return 0 if length is less than 3.

💡 Avoid loops or pointer logic when insufficient elements.

Why it failed: Fails to return 0 for arrays with fewer than 3 elements, leading to errors or incorrect counts. Fix by adding length check before processing.

✓ Correctly returns 0 for arrays with less than 3 elements.

t2_03edge

Input{"nums":[1,1,1,1],"target":5}

Expected4

⏱ Performance - must finish in 2000ms

All triplets sum to 3 which is less than 5; number of triplets is C(4,3)=4.

💡 When all elements are equal, count combinations if sum < target.

💡 Calculate number of triplets as n choose 3 if sum of three elements < target.

💡 Ensure counting logic handles duplicates correctly without skipping.

Why it failed: Code misses counting all triplets when elements are identical and sum < target. Fix by not skipping duplicates and counting all valid triplets.

✓ Counts all triplets correctly even when elements are identical.

t2_04edge

Input{"nums":[1,1,1,1],"target":3}

Expected0

⏱ Performance - must finish in 2000ms

All triplets sum to 3 which is not less than 3; count is 0.

💡 Check strict less than condition for sum comparison.

💡 If sum equals target, do not count the triplet.

💡 Use sum < target, not sum <= target.

Why it failed: Counting triplets with sum equal to target causes overcount. Fix by using strict less than (<) in condition.

✓ Correctly excludes triplets with sum equal to target.

t3_01corner

Input{"nums":[1,2,3,4,5],"target":8}

Expected2

⏱ Performance - must finish in 2000ms

Triplets with sums less than 8 are (1,2,3)=6 and (1,2,4)=7; others are >=8.

💡 Check if your code incorrectly counts triplets equal to target as valid.

💡 Ensure strict less than comparison is used, not less or equal.

💡 Change condition from sum <= target to sum < target to fix.

Why it failed: Counting triplets with sum equal to target causes overcount. Fix by using strict less than (<) in condition.

✓ Correctly excludes triplets with sum equal to target.

t3_02corner

Input{"nums":[0,0,0,0],"target":1}

Expected4

⏱ Performance - must finish in 2000ms

All triplets sum to 0 which is less than 1; number of triplets is C(4,3)=4.

💡 Beware of off-by-one errors in pointer movement.

💡 Make sure to count all valid pairs when sum condition is met.

💡 Increment count by (right - left) when sum < target, then move left pointer.

Why it failed: Off-by-one error in two-pointer counting causes undercount. Fix by incrementing count by (right - left) and moving left pointer correctly.

✓ Counts all triplets correctly with proper two-pointer increments.

t3_03corner

Input{"nums":[-4,-1,-1,0,1,2],"target":2}

Expected17

⏱ Performance - must finish in 2000ms

After sorting [-4,-1,-1,0,1,2], count all triplets with sum < 2. The count is 10.

💡 Sorting is essential before applying two pointers.

💡 Avoid greedy approaches that pick only smallest or largest elements.

💡 Use nested loops with two pointers to count all valid triplets.

Why it failed: Greedy approach misses some triplets leading to undercount. Fix by sorting and using two-pointer nested loops to count all triplets.

✓ Correctly counts all triplets using sorting and two-pointer approach.

t4_01performance

Input{"nums":[-500,-499,-498,-497,-496,-495,-494,-493,-492,-491,-490,-489,-488,-487,-486,-485,-484,-483,-482,-481,-480,-479,-478,-477,-476,-475,-474,-473,-472,-471,-470,-469,-468,-467,-466,-465,-464,-463,-462,-461,-460,-459,-458,-457,-456,-455,-454,-453,-452,-451,-450,-449,-448,-447,-446,-445,-444,-443,-442,-441,-440,-439,-438,-437,-436,-435,-434,-433,-432,-431,-430,-429,-428,-427,-426,-425,-424,-423,-422,-421,-420,-419,-418,-417,-416,-415,-414,-413,-412,-411,-410,-409,-408,-407,-406,-405,-404,-403,-402,-401],"target":1000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n^2) solution must complete within 2 seconds; brute force O(n^3) will time out.

💡 Brute force triple nested loops are too slow for n=100.

💡 Use sorting and two-pointer approach to achieve O(n^2) time.

💡 Optimize inner loops and avoid unnecessary computations.

Why it failed: Brute force O(n^3) approach causes TLE on n=100 input. Fix by implementing O(n^2) two-pointer solution.

✓ Solution runs within time limit using O(n^2) approach.

Practice

1. What is the time complexity of the optimal two-pointer solution for the Container With Most Water problem, and why?

medium

A. O(n^2) because each pointer moves multiple times and all pairs are checked.

B. O(n) because each pointer moves inward at most n times, scanning the array once.

C. O(n log n) due to sorting or binary search steps involved.

D. O(1) because only constant space and operations are used.

Solution

1. Step 1: Analyze pointer movements

   Each pointer starts at opposite ends and moves inward only when the shorter line pointer moves, so total moves per pointer ≤ n.

2. Step 2: Count total operations

   Since pointers move inward without revisiting positions, total iterations ≤ n, making time complexity O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer linear scan -> O(n) time [OK]

Hint: Two pointers each move at most n times -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing space complexity with time
• Thinking sorting is required

2. What is the time complexity of the two-pointer approach that fills the output array from the end by comparing absolute values of elements at both ends of the input sorted array?

medium

A. O(n log n) due to sorting the squared array after processing

B. O(n) because each element is processed exactly once with two pointers

C. O(n²) because each comparison may involve scanning the array

D. O(n) for processing plus O(n) for extra space allocation

Solution

1. Step 1: Identify the main loop behavior

   The two-pointer approach moves pointers inward, processing each element once.

2. Step 2: Confirm no sorting or nested loops

   No sorting is done; comparisons and assignments are O(1) each, total O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear scan with two pointers -> O(n) [OK]

Hint: Two pointers process each element once -> O(n) [OK]

Common Mistakes:

• Assuming sorting is still needed -> O(n log n)
• Confusing comparisons with nested loops -> O(n²)
• Ignoring constant-time operations

3. Suppose the 3Sum problem is modified so that elements can be reused multiple times in a triplet (e.g., triplet [0,0,0] is valid if zeros exist). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Remove the duplicate skipping for fixed element i and inner pointer j, allowing repeated elements.

B. Use three nested loops to allow repeated indices and check sums directly.

C. Keep the same code but remove the sorting step to allow duplicates naturally.

D. Modify the hash set approach to not skip duplicates and allow complement to be equal to nums[j].

Solution

1. Step 1: Understand reuse means duplicates allowed in triplets

   Allowing reuse means complement can be equal to nums[j], so skipping duplicates must be adjusted.

2. Step 2: Modify hash set approach accordingly

   Do not skip duplicates; allow complement == nums[j]; sorting still needed to avoid unordered duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Allowing complement == nums[j] and no skipping duplicates handles reuse correctly [OK]

Hint: Allow complement == nums[j] and no skipping duplicates for reuse [OK]

Common Mistakes:

• Removing sorting breaks uniqueness
• Using triple loops is inefficient
• Removing duplicate skipping blindly causes duplicates

4. Suppose the input array can contain negative integers and zeros, and you want to partition the array so that all even numbers (including negative evens and zero) come before all odd numbers. Which modification to the original two-pointer algorithm is necessary to handle this correctly?

hard

A. Change the parity check to use abs(nums[i]) % 2 == 0 to handle negative numbers

B. Use a sorting-based approach since parity is ambiguous with negative numbers

C. No change needed; the original parity check nums[i] % 2 == 0 works correctly for negatives and zero

D. Add a separate pass to move zeros to the front before partitioning evens and odds

Solution

1. Step 1: Understand parity with negatives and zero

   In Python, num % 2 == 0 correctly identifies even numbers including negatives and zero.

2. Step 2: Confirm no algorithm change needed

   The original two-pointer approach works unchanged since parity check is valid for all integers.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Modulo operator handles negative evens and zero correctly [OK]

Hint: Modulo operator works for negative evens and zero [OK]

Common Mistakes:

• Thinking abs() is needed for parity check
• Assuming zeros need special handling
• Believing sorting is required for negatives

5. Suppose you want to reverse a string but the input is a very large immutable string (e.g., Python str) instead of a mutable list. Which approach correctly handles this constraint efficiently?

hard

A. Convert the string to a list, reverse it using two pointers, then join back to a string.

B. Use a brute force approach creating a new reversed string by concatenation in a loop.

C. Use the recursive two-pointer approach on the string directly, swapping characters in-place.

D. Use a dynamic programming approach to build the reversed string from substrings.

Solution

1. Step 1: Understand immutability constraint

   Strings are immutable in Python, so in-place swaps are impossible directly on the string.

2. Step 2: Choose efficient workaround

   Converting to a list allows in-place two-pointer swaps, then joining back creates the reversed string efficiently in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only Convert the string to a list, reverse it using two pointers, then join back to a string. respects immutability and is efficient [OK]

Hint: Immutable strings require conversion to mutable type for in-place reversal [OK]

Common Mistakes:

• Trying to swap characters in immutable string
• Using inefficient string concatenation in loop
• Misapplying DP to string reversal