How do you solve 3Sum Smaller?

Sort nums. For each index i, use two pointers left and right to find pairs where nums[i] + nums[left] + nums[right] < target. When the sum is less than target, all elements between left and right form valid pairs with i, so increment count by right - left and move left pointer forward. Otherwise, move right pointer backward. Return total count after processing all i.

What pattern does 3Sum Smaller use?

The Pattern: Two Pointers (Sorted Array Pair Counting) The Heuristic: When counting pairs or triplets with sum constraints in a sorted array, fix one element and use two pointers to efficiently count all valid pairs by exploiting the sorted order to skip unnecessary checks.

3Sum Smaller | Two Pointers

Q: What is the time complexity of 3Sum Smaller?

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

Q: What pattern does 3Sum Smaller use?

The Pattern: Two Pointers (Sorted Array Pair Counting) The Heuristic: When counting pairs or triplets with sum constraints in a sorted array, fix one element and use two pointers to efficiently count all valid pairs by exploiting the sorted order to skip unnecessary checks.

Problem

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.

0 ≤ nums.length ≤ 3500
−10⁵ ≤ nums[i] ≤ 10⁵
−10⁵ ≤ target ≤ 10⁵

Example

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

Output: 2

The triplets that satisfy the condition are (-2,0,1) with sum -1 < 2 and (-2,0,3) with sum 1 < 2. The brute-force approach would check all triplets, which is O(n^3). The key insight is to sort the array and use two pointers to efficiently count valid pairs for each fixed first element.

Approach

Straightforward Solution

A brute-force triple nested loop checks all triplets, resulting in O(n^3) time complexity, which is too slow for large inputs.

Core Observation

The problem requires counting triplets with sums less than a target, which suggests exploring combinations efficiently. Sorting the array allows leveraging the order to prune search space.

Path to Optimal

Sorting the array enables a two-pointer approach for the inner two elements. Fixing one element, the two pointers scan from both ends inward to count all pairs that satisfy the sum condition in O(n) time per fixed element, reducing total complexity to O(n^2).

Optimal Approach

Preview

Sort nums. For each index i, use two pointers left and right to find pairs where nums[i] + nums[left] + nums[right] < target…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n^2)

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

Space

O(1)

Sorting is done in-place, and only a few variables are used for pointers and counters, resulting in O(1) auxiliary space.

Solution

Python

1class Solution:
  def threeSumSmaller(self, nums: list[int], target: int) -> int:
      nums.sort()
      count = 0
5
      for i in range(len(nums) - 2):
          left = i + 1
          right = len(nums) - 1
9
          while left < right:
              total = nums[i] + nums[left] + nums[right]
12
              if total < target:
                  count += right - left
                  left += 1
              else:
                  right -= 1
18
      return count

Step-by-Step Solution

1

Sort the Array and Initialize the Count

3nums.sort()
4count = 0

Objective

To prepare the input for efficient two-pointer traversal and set up the accumulator for valid triplets.

Key Insight

Sorting the array is essential because it allows the two-pointer technique to work by leveraging the order of elements. Initializing the count variable sets up the accumulator for the total number of valid triplets found.

Interview Quick-Check

Core Logic

Sorting enables the two-pointer approach by ensuring that increasing the left pointer increases the sum and decreasing the right pointer decreases the sum.

Common Pitfalls & Bugs

Forgetting to sort the array breaks the logic of the two-pointer approach, leading to incorrect counts.

2

Iterate Over the Array Fixing the First Element of Triplets

To select each element as the fixed first element and find pairs that complete triplets with sums less than the target.

3

Use Two Pointers to Count Valid Pairs for Each Fixed Element

To efficiently count all pairs between left and right pointers that, combined with the fixed element, have sums less than the target.

4

Return the Total Count of Valid Triplets

To output the final count of all triplets with sums less than the target after processing the entire array.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 14 Critical

count += right - left

Increment count by the number of valid pairs between left and right pointers.

Because the array is sorted, if the sum with nums[right] is less than target, all elements between left and right pointers paired with the fixed element satisfy the condition, allowing O(1) counting of multiple triplets.

Line 3 Critical

nums.sort()

Sort the input array in ascending order.

Sorting is crucial because it enables the two-pointer technique by ensuring that moving pointers predictably increases or decreases the sum, allowing efficient pruning of the search space.

Line 13 Critical

if total < target:

Check if the current sum is less than the target.

This condition identifies when all pairs between left and right pointers form valid triplets, enabling bulk counting.

Full line-by-line criticality + rationale for all 13 lines available on Pro.

Test Your Understanding

Why can we add right - left to the count when the sum of nums[i] + nums[left] + nums[right] is less than the target?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct 3Sum Smaller from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the 3Sum Smaller drill

or drill a free problem

1	`class Solution:`
2	`def threeSumSmaller(self, nums: list[int], target: int) -> int:`
3	`nums.sort()`
4	`count = 0`
5
6	`for i in range(len(nums) - 2):`
7	`left = i + 1`
8	`right = len(nums) - 1`
9
10	`while left < right:`
11	`total = nums[i] + nums[left] + nums[right]`
12
13	`if total < target:`
14	`count += right - left`
15	`left += 1`
16	`else:`
17	`right -= 1`
18
19	`return count`