3Sum Smaller

▶

Steps

setup

Sort the array

The input array is sorted to enable the two-pointer technique. Sorted array: [-2, 0, 1, 3].

💡 Sorting is essential because the two-pointer approach relies on the array being ordered to prune search efficiently.

Line:

nums.sort()

💡 Sorting prepares the array for efficient two-pointer traversal.

setup

Initialize count and start outer loop with i=0

Initialize count to 0. Set i pointer at index 0 to fix the first element of triplets.

💡 The outer loop fixes one element at a time to find pairs with two pointers.

Line:

count = 0
n = len(nums)
for i in range(n - 2):

💡 Starting the first iteration with i=0 to explore triplets starting with nums[0].

compare

Check early termination condition for i=0

Check if nums[i] + nums[i+1] + nums[i+2] >= target. Here, -2 + 0 + 1 = -1 < 2, so continue.

💡 Early termination avoids unnecessary work if the smallest triplet sum starting at i is already too large.

Line:

if nums[i] + nums[i + 1] + nums[i + 2] >= target:
    break

💡 The smallest possible sum with i=0 is less than target, so valid triplets may exist.

setup

Initialize left and right pointers for i=0

Set left pointer to i+1=1 and right pointer to n-1=3 to find pairs with nums[i].

💡 Left and right pointers scan the subarray to find pairs that form valid triplets with nums[i].

Line:

left, right = i + 1, n - 1

💡 Pointers are positioned to explore all pairs between left and right indices.

compare

Calculate current sum with i=0, left=1, right=3

Calculate sum = nums[0] + nums[1] + nums[3] = -2 + 0 + 3 = 1.

💡 Sum of the current triplet is compared to target to decide pointer moves.

Line:

curr_sum = nums[i] + nums[left] + nums[right]

💡 Current sum is less than target, so all triplets with left fixed and right between left and right pointers are valid.

insert

Sum < target: add (right - left) to count and move left pointer

Since sum=1 < target=2, add right - left = 3 - 1 = 2 to count. Then increment left to 2.

💡 All pairs between left and right pointers with current i form valid triplets, so count them at once.

Line:

if curr_sum < target:
    count += right - left
    left += 1

💡 This step shows how the algorithm counts multiple triplets efficiently without checking each explicitly.

compare

Calculate current sum with i=0, left=2, right=3

Calculate sum = nums[0] + nums[2] + nums[3] = -2 + 1 + 3 = 2.

💡 Check if the new triplet sum is less than target to decide pointer moves.

Line:

curr_sum = nums[i] + nums[left] + nums[right]

💡 Sum equals target, so no triplets with this right pointer are valid; must move right pointer.

shrink

Sum >= target: move right pointer left

Since sum=2 is not less than target=2, decrement right pointer from 3 to 2.

💡 Moving right pointer left tries smaller values to reduce the sum.

Line:

else:
    right -= 1

💡 This step shows how the algorithm shrinks the window when sum is too large.

compare

Check while loop condition left < right for i=0

Now left=2 and right=2, so left is not less than right. Exit while loop for i=0.

💡 The two-pointer search ends when pointers meet or cross.

Line:

while left < right:

💡 No more pairs to check with i=0.

traverse

Increment i to 1 and check early termination

Move i to 1. Check if nums[1] + nums[2] + nums[3] >= target: 0 + 1 + 3 = 4 >= 2, so break outer loop.

💡 Early termination stops the search because all further triplets will be too large.

Line:

for i in range(n - 2):
    if nums[i] + nums[i + 1] + nums[i + 2] >= target:
        break

💡 This step shows how the algorithm avoids unnecessary work by pruning.

reconstruct

Return final count

All valid triplets counted. Return count = 2 as the final answer.

💡 The count represents the number of triplets with sum smaller than target.

Line:

return count

💡 The algorithm efficiently counted valid triplets without enumerating all combinations.

def threeSumSmaller(nums, target):
    nums.sort()  # STEP 1
    count = 0  # STEP 2
    n = len(nums)
    for i in range(n - 2):  # STEP 2
        if nums[i] + nums[i + 1] + nums[i + 2] >= target:  # STEP 3, 10
            break
        left, right = i + 1, n - 1  # STEP 4
        while left < right:  # STEP 9
            curr_sum = nums[i] + nums[left] + nums[right]  # STEP 5,7
            if curr_sum < target:  # STEP 6
                count += right - left  # STEP 6
                left += 1  # STEP 6
            else:
                right -= 1  # STEP 8
    return count  # STEP 11

📊

3Sum Smaller - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the two-pointer technique efficiently counts valid triplets without checking all combinations.

setup

-2

0

0

1

1

2

3

3

Result: 0

setup

i

-2

0

0

1

1

2

3

3

Result: 0

compare

i

-2

0

0

1

1

2

3

3

Result: 0

setup

i

-2

0

left

0

1

1

2

right

3

3

Result: 0

compare

i

-2

0

left

0

1

1

2

right

3

3

Result: 0

move_left

i

-2

0

0

1

left

1

2

right

3

3

Result: 2

compare

i

-2

0

0

1

left

1

2

right

3

3

Result: 2

move_right

i

-2

0

0

1

right

1

2

3

3

Result: 2

compare

i

-2

0

0

1

right

1

2

3

3

Result: 2

compare

-2

0

i

0

1

1

2

3

3

Result: 2

record

-2

0

0

1

1

2

3

3

Result: 2

Key Takeaways

✓ The two-pointer technique efficiently counts multiple valid triplets at once by leveraging the sorted array.

This insight is hard to see from code alone because it requires understanding how the pointers represent ranges of valid pairs.

✓ Early termination based on the smallest possible triplet sum saves computation by pruning impossible cases.

Seeing the early break condition in action clarifies why the algorithm is faster than brute force.

✓ Pointer movements depend on comparing the current sum to the target, guiding whether to move left or right pointers.

Watching each pointer move step-by-step reveals the logic behind shrinking or expanding the search window.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. You are given an array representing heights of bars where water can be trapped between bars after raining. Which approach guarantees an optimal O(n) time and O(1) space solution to calculate the total trapped water?

easy

A. Use two pointers starting from opposite ends, updating left_max and right_max while moving inward.

B. Use a greedy approach that always fills the lowest bar first without considering future bars.

C. Use dynamic programming with a 2D table storing water trapped between every pair of bars.

D. Use a brute force nested loop to find max heights on left and right for each bar.

Solution

1. Step 1: Understand problem constraints

   The problem requires calculating trapped water efficiently in linear time and constant space.

2. Step 2: Identify approach matching constraints

   The two pointers approach moves inward from both ends, updating left_max and right_max, allowing O(n) time and O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers approach is known optimal for trapping rain water [OK]

Hint: Two pointers from ends -> O(n) time, O(1) space [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with 2D tables for this problem
• Thinking greedy fill lowest bar always works

3. Examine the following code snippet for 3Sum. Which line contains a subtle bug that can cause duplicate triplets in the output?

medium

A. Line 6: Missing check to skip duplicates for fixed element i

B. Line 10: Incorrect calculation of complement

C. Line 14: Not sorting triplet before appending

D. Line 16: Missing increment of j after skipping duplicates

Solution

1. Step 1: Identify duplicate handling for fixed element

   Line 6 lacks the check to skip duplicate nums[i], causing repeated triplets.

2. Step 2: Verify other lines

   Complement calculation and triplet sorting are correct; j increment after skipping duplicates is present.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Skipping duplicates for i is essential to avoid duplicate triplets [OK]

Hint: Skipping duplicates for fixed i prevents repeated triplets [OK]

Common Mistakes:

• Forgetting to skip duplicates for i
• Assuming sorting triplet is unnecessary
• Misplacing complement calculation

4. What is the time complexity of the optimal two-pointer forward approach for comparing two strings with backspaces, each of length n and m respectively?

medium

A. O(n * m)

B. O(n^2 + m^2)

C. O(n + m)

D. O(max(n, m) * log(max(n, m)))

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm processes each string once with a single pass using two pointers, so each character is visited at most once.

2. Step 2: Combine complexities for both strings

   Processing both strings independently takes O(n) and O(m), so total time is O(n + m).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass per string, no nested loops [OK]

Hint: Two pointers scan each string once -> O(n + m) [OK]

Common Mistakes:

• Assuming nested loops cause O(n*m)
• Confusing space complexity with time
• Thinking backspace processing requires DP or sorting

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