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. Consider the following Python function implementing the optimal 4Sum approach. Given the input nums = [1, 0, -1, 0] and target = 0, what is the final returned list of quadruplets?

easy

A. [[-1, 0, 0, 1]]

B. [[0, 0, 0, 0]]

C. [[-1, -1, 1, 1]]

D. []

Solution

1. Step 1: Sort input and build two_sum_map

   Sorted nums = [-1, 0, 0, 1]. Pairs and sums: (-1,0)= -1, (-1,0)= -1, (-1,1)=0, (0,0)=0, (0,1)=1, (0,1)=1.

2. Step 2: Find complementary pairs summing to target=0

   Check sums and their complements: sum1=-1, sum2=1; sum1=0, sum2=0. Combine pairs ensuring no index overlap. Valid quadruplet is [-1,0,0,1].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one quadruplet sums to zero without index overlap [OK]

Hint: Sort and check pairs sums carefully to find quadruplets [OK]

Common Mistakes:

• Confusing indices leading to duplicates or missing quadruplets

2. Given the following code for trapping rain water, what is the value of the variable water returned by trap([2,0,2])?

easy

A. 4

B. 0

C. 2

D. 1

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: Trace iterations

   Iteration 1: height[left]=2, height[right]=2, height[left] not less than height[right], so process right pointer. right_max updated to 2, right moves to 1.
   Iteration 2: left=0, right=1, height[left]=2, height[right]=0, height[left] > height[right], process right pointer.
   height[right]=0 < right_max=2, water += 2 - 0 = 2, right moves to 0.
   Loop ends as left == right.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Water trapped between two height 2 bars with 0 in middle is 2 units [OK]

Hint: Trace pointers and water increments carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer movement
• Confusing which pointer to move
• Incorrectly updating max heights

3. What is the time complexity of the optimal 3Sum solution that sorts the array and uses a hash set for the two-sum complement search for each fixed element?

medium

A. O(n^3) because of nested loops and hash set operations

B. O(n^2) because for each element, we scan the rest with a hash set lookup in O(1)

C. O(n log n) due to sorting and linear two-pointer scans

D. O(n^2 log n) because sorting and hash set insertions dominate

Solution

1. Step 1: Identify sorting cost

   Sorting takes O(n log n), which is dominated by later steps.

2. Step 2: Analyze nested loops and hash set usage

   Outer loop runs n times; inner loop runs up to n times; hash set operations inside inner loop are O(1) each, but overall complexity is O(n^2).

3. Step 3: Clarify complexity of hash set approach

   The hash set approach inside the inner loop leads to O(n^2) complexity, not O(n^3).

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Hash set lookups are O(1), so total is O(n^2) [OK]

Hint: Sorting O(n log n) < O(n²) nested loops dominate [OK]

Common Mistakes:

• Confusing hash set insertions as O(n)
• Thinking sorting dominates
• Assuming triple nested loops remain

4. What is the time complexity of the optimal 4Sum solution that uses a hash map to store all pairs of sums and then finds complementary pairs to form quadruplets?

medium

A. O(n^2 + k^2), where k is the average number of pairs per sum stored in the hash map.

B. O(n^4) because all quadruplets are checked explicitly.

C. O(n^3) due to nested loops over pairs and quadruplets.

D. O(n^2 log n) because sorting dominates the complexity.

Solution

1. Step 1: Analyze pair sum generation

   Generating all pairs sums takes O(n^2) time and space.

2. Step 2: Analyze combining pairs to quadruplets

   For each sum, combining pairs from two lists takes O(k^2) where k is average pairs per sum.

3. Step 3: Consider worst case

   In worst case, k can be O(n), so combining pairs can be O(n^2) per sum, leading to O(n^4) overall.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Worst-case complexity is O(n^4), not O(n^2 + k^2) [OK]

Hint: Worst-case complexity can be O(n^4) due to pair combinations [OK]

Common Mistakes:

• Assuming average case complexity applies to worst case
• Ignoring worst-case pair combination cost

5. Consider the following buggy code for Two Sum II using binary search. Which line contains the subtle bug that may cause incorrect results?

medium

A. Line checking if j != -1

B. Line calling binary_search with left=0 instead of i+1

C. Line returning [i + 1, j + 1]

D. Line calculating complement = target - numbers[i]

Solution

1. Step 1: Identify binary search call parameters

   Binary search should start from i+1 to avoid reusing the same element or previous elements.

2. Step 2: Analyze impact of starting from 0

   Starting from 0 may find the same element at index i, causing incorrect pairs or duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Correct binary search range is i+1 to n-1, not 0 to n-1 [OK]

Hint: Binary search must exclude current index to avoid duplicates [OK]

Common Mistakes:

• Searching entire array instead of subarray
• Off-by-one in indices
• Incorrect complement calculation