Problem Description

You are given an array of n integers called nums and an integer target. Your task is to find the number of index triplets (i, j, k) that satisfy the following conditions:

1. The indices must follow the order: 0 <= i < j < k < n
2. The sum of the three elements at these indices must be less than the target: nums[i] + nums[j] + nums[k] < target

For example, if nums = [-2, 0, 1, 3] and target = 2, you would need to find all combinations of three different indices where the sum of the corresponding elements is less than 2.

The key insight is that since we only care about the count of valid triplets and not their actual values or original positions, we can sort the array first. After sorting, we can efficiently use a two-pointer technique:

1. Fix the first element nums[i] by iterating through the array
2. For each fixed i, use two pointers j and k where j starts right after i and k starts at the end of the array
3. When nums[i] + nums[j] + nums[k] < target, all elements between j and k would also form valid triplets with i and j (since the array is sorted). This gives us k - j valid triplets at once
4. Move the pointers accordingly: increment j when the sum is less than target, decrement k when the sum is greater than or equal to target

This approach reduces the time complexity from O(n³) for a brute force solution to O(n²) by cleverly counting multiple valid triplets at once.

Intuition

The brute force approach would be to check all possible triplets using three nested loops, which would take O(n³) time. We need a smarter way to count valid triplets.

The key observation is that the problem asks for counting triplets where the sum is less than a target value. This is a inequality condition, not an equality. When dealing with inequalities and sums, sorting the array often helps because it creates a predictable order that we can exploit.

Once we sort the array, we can think about fixing one element and finding pairs in the remaining array. This reduces the problem from finding triplets to finding pairs with a modified target (target - nums[i]).

For finding pairs with a sum condition in a sorted array, the two-pointer technique is natural. We place one pointer at the start and another at the end. But here's the crucial insight: when we find that nums[i] + nums[j] + nums[k] < target, we don't just count this one triplet. Since the array is sorted, we know that replacing nums[k] with any element between j and k will also satisfy the condition (because those elements are all smaller than nums[k]).

This means when nums[i] + nums[j] + nums[k] < target, we can immediately count k - j valid triplets: (i, j, j+1), (i, j, j+2), ..., (i, j, k). This batch counting is what makes the algorithm efficient.

The pointer movement logic follows naturally: if the current sum is too small, we need to increase it by moving j right (to get a larger value). If the sum is too large, we decrease it by moving k left (to get a smaller value). This ensures we explore all possible valid combinations without redundancy.

Solution Approach

The implementation follows a sorting + two pointers + enumeration pattern:

Step 1: Sort the array

nums.sort()

Sorting takes O(n log n) time and enables the two-pointer technique to work efficiently.

Step 2: Initialize variables

ans, n = 0, len(nums)

We maintain ans to count valid triplets and store the array length in n.

Step 3: Enumerate the first element

for i in range(n - 2):

We iterate i from 0 to n-3 (inclusive) since we need at least 3 elements for a triplet. This fixes the first element of our triplet as nums[i].

Step 4: Two-pointer search for the remaining pair

j, k = i + 1, n - 1

For each fixed i, initialize two pointers:

• j starts at i + 1 (the next element after i)
• k starts at n - 1 (the last element of the array)

Step 5: Process pairs with the two-pointer technique

while j < k:
    x = nums[i] + nums[j] + nums[k]
    if x < target:
        ans += k - j
        j += 1
    else:
        k -= 1

The core logic works as follows:

• Calculate the sum x = nums[i] + nums[j] + nums[k]
• If x < target: All elements between indices j+1 and k would also form valid triplets with i and j because:
  • The array is sorted, so nums[j+1] < nums[j+2] < ... < nums[k]
  • Therefore, nums[i] + nums[j] + nums[j+1], nums[i] + nums[j] + nums[j+2], ..., nums[i] + nums[j] + nums[k] are all less than target
  • This gives us exactly k - j valid triplets
  • Move j right to explore new combinations
• If x >= target: The current sum is too large, so we need to decrease it by moving k left to get a smaller value

Time Complexity: O(n²) - The outer loop runs O(n) times, and for each iteration, the two-pointer search takes O(n) time.

Space Complexity: O(1) - We only use a constant amount of extra space (not counting the space used for sorting, which depends on the implementation).

Example Walkthrough

Let's walk through the solution with nums = [-2, 0, 1, 3] and target = 2.

Step 1: Sort the array The array is already sorted: [-2, 0, 1, 3]

Step 2: Fix the first element and use two pointers

Iteration 1: i = 0 (first element = -2)

• Initialize: j = 1 (points to 0), k = 3 (points to 3)
• Calculate sum: -2 + 0 + 3 = 1 < 2 ✓
  • All triplets with i=0, j=1, and any k from j+1 to 3 are valid
  • Count: k - j = 3 - 1 = 2 valid triplets
  • These are: (-2, 0, 1) and (-2, 0, 3)
  • Move j right: j = 2
• Now j = 2 (points to 1), k = 3 (points to 3)
• Calculate sum: -2 + 1 + 3 = 2 >= 2 ✗
  • Sum is not less than target, move k left: k = 2
• Now j = 2, k = 2, so j >= k, exit inner loop

Iteration 2: i = 1 (first element = 0)

• Initialize: j = 2 (points to 1), k = 3 (points to 3)
• Calculate sum: 0 + 1 + 3 = 4 >= 2 ✗
  • Sum is too large, move k left: k = 2
• Now j = 2, k = 2, so j >= k, exit inner loop

Iteration 3: i = 2 would leave no room for j and k, so we stop.

Total count: 2

The two valid triplets found are:

1. Indices (0, 1, 2): nums[0] + nums[1] + nums[2] = -2 + 0 + 1 = -1 < 2
2. Indices (0, 1, 3): nums[0] + nums[1] + nums[3] = -2 + 0 + 3 = 1 < 2

Note how the algorithm efficiently counted both valid triplets in one step when we found that -2 + 0 + 3 < 2, immediately recognizing that replacing 3 with any smaller element (in this case, 1) would also satisfy the condition.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^2)

The algorithm first sorts the array, which takes O(n log n) time. Then it uses a three-pointer approach:

• The outer loop runs n-2 times, iterating through each possible first element
• For each iteration of the outer loop, the two-pointer technique (with pointers j and k) traverses the remaining array at most once, taking O(n) time
• Therefore, the nested loop structure gives us O(n) * O(n) = O(n^2) time
• The overall time complexity is O(n log n) + O(n^2) = O(n^2), as O(n^2) dominates

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Most efficient sorting algorithms like Python's Timsort (used in sort()) require O(log n) space for the recursion stack or auxiliary space during the sorting process. The algorithm itself only uses a constant amount of extra variables (ans, i, j, k, x), which is O(1). Therefore, the total space complexity is O(log n).

Common Pitfalls

Pitfall 1: Forgetting to Sort the Array

Issue: The two-pointer technique relies on the array being sorted. Without sorting, the algorithm's logic breaks down because we can't make assumptions about elements between the two pointers.

Wrong approach:

def threeSumSmaller(self, nums: List[int], target: int) -> int:
    # Missing nums.sort() - WRONG!
    count = 0
    n = len(nums)
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        while left < right:
            # This logic doesn't work on unsorted arrays
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum < target:
                count += right - left  # Incorrect count for unsorted array
                left += 1
            else:
                right -= 1
    return count

Solution: Always sort the array first before applying the two-pointer technique.

Pitfall 2: Incorrect Counting Logic

Issue: When nums[i] + nums[j] + nums[k] < target, beginners often count only 1 triplet instead of k - j triplets.

Wrong approach:

if current_sum < target:
    count += 1  # WRONG! This only counts one triplet
    left += 1

Why it's wrong: When the sum is less than target with a sorted array, all elements between left and right indices form valid triplets with nums[i] and nums[left]. For example, if nums[i] + nums[left] + nums[right] < target, then:

• (i, left, right) is valid
• (i, left, right-1) is also valid (smaller sum)
• (i, left, right-2) is also valid
• ... and so on until (i, left, left+1)

Solution: Count all valid triplets at once with count += right - left.

Pitfall 3: Edge Case Handling - Array Too Small

Issue: Not checking if the array has at least 3 elements before processing.

Wrong approach:

def threeSumSmaller(self, nums: List[int], target: int) -> int:
    nums.sort()
    count = 0
    n = len(nums)
    # What if n < 3? The loop still runs!
    for i in range(n - 2):  # This could be range(-1) if n = 1
        ...

Solution: Add an early return for arrays with fewer than 3 elements:

def threeSumSmaller(self, nums: List[int], target: int) -> int:
    if len(nums) < 3:
        return 0
    nums.sort()
    # ... rest of the code

Pitfall 4: Pointer Movement Logic Error

Issue: Moving both pointers simultaneously or using wrong conditions for pointer movement.

Wrong approach:

while left < right:
    current_sum = nums[i] + nums[left] + nums[right]
    if current_sum < target:
        count += right - left
        left += 1
        right -= 1  # WRONG! Don't move both pointers

Why it's wrong: When we find a valid sum, we should only move the left pointer to explore new combinations with larger sums. Moving both pointers might skip valid triplets.

Solution: Move only one pointer at a time based on the comparison with target:

• If sum < target: move left pointer right (to increase sum)
• If sum >= target: move right pointer left (to decrease sum)