Problem Description

You are given an integer array nums with 0-based indexing (length n) and an integer target. Your task is to count how many pairs of indices (i, j) satisfy the following conditions:

• i is less than j (i.e., 0 <= i < j < n)
• The sum of the elements at these indices is less than the target (i.e., nums[i] + nums[j] < target)

The solution uses a sorting and binary search approach. After sorting the array, for each element at position j, it uses binary search to find how many elements before position j can form valid pairs with nums[j]. Specifically, it finds the leftmost position where nums[i] >= target - nums[j], which means all positions before this can form valid pairs with the current element.

For example, if nums = [1, 2, 3, 4] and target = 5:

• When j = 1 (element is 2), we search for elements less than 5 - 2 = 3 before position 1, which gives us element at index 0 (value 1)
• When j = 2 (element is 3), we search for elements less than 5 - 3 = 2 before position 2, which gives us element at index 0 (value 1)
• When j = 3 (element is 4), we search for elements less than 5 - 4 = 1 before position 3, which gives us no valid elements

The total count accumulates all valid pairs found for each position j.

Intuition

The key insight is that once we sort the array, we can efficiently find valid pairs using the sorted order property.

Think about it this way: if we fix the second element of the pair at position j, we need to find all elements at positions i < j such that nums[i] + nums[j] < target. This is equivalent to finding all nums[i] < target - nums[j].

In a sorted array, all elements less than a certain value form a contiguous segment at the beginning. So instead of checking every element before position j one by one (which would be inefficient), we can use binary search to quickly find the boundary - the first position where nums[i] >= target - nums[j]. Everything before this boundary forms a valid pair with nums[j].

Why does this work? Because in a sorted array:

• If nums[i] + nums[j] < target for some i, then all indices smaller than i will also satisfy this condition (since those elements are even smaller)
• We can find this "cutoff point" in logarithmic time using binary search

By iterating through each possible second element j and using binary search to count valid first elements, we transform what could be an O(n²) brute force approach into an O(n log n) solution. The sorting step takes O(n log n) and then we perform n binary searches, each taking O(log n) time.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The solution implements the sorting and binary search strategy in a clean and efficient manner.

Step 1: Sort the array

nums.sort()

We start by sorting the input array in ascending order. This enables us to use binary search later.

Step 2: Initialize counter

ans = 0

This variable will accumulate the total count of valid pairs.

Step 3: Iterate through each potential second element

for j, x in enumerate(nums):

We iterate through the sorted array, treating each element at position j as the second element of potential pairs. The variable x holds the value nums[j].

Step 4: Binary search for valid first elements

i = bisect_left(nums, target - x, hi=j)

For each position j, we use bisect_left to find the leftmost position in the range [0, j) where we could insert target - x while maintaining sorted order. This gives us the index of the first element that is greater than or equal to target - x.

The hi=j parameter ensures we only search in the range [0, j), which guarantees i < j as required by the problem.

Step 5: Count valid pairs

ans += i

All indices from 0 to i-1 contain elements that are less than target - x, meaning nums[k] + nums[j] < target for all k in [0, i). So we add i to our answer (since there are i valid indices: 0, 1, 2, ..., i-1).

Step 6: Return the result

return ans

After processing all possible second elements, we return the total count.

The time complexity is O(n log n) for sorting plus O(n log n) for n binary searches, giving overall O(n log n). The space complexity is O(1) if we don't count the sorting space (or O(n) depending on the sorting algorithm used).

Example Walkthrough

Let's walk through a concrete example with nums = [3, 1, 5, 2] and target = 6.

Step 1: Sort the array After sorting: nums = [1, 2, 3, 5]

Step 2: Process each element as the second element of a pair

When j = 0 (nums[j] = 1):

• We need to find elements before index 0 where nums[i] + 1 < 6
• This means finding nums[i] < 5 in range [0, 0)
• Since the range is empty, no valid pairs exist
• Count: 0

When j = 1 (nums[j] = 2):

• We need to find elements before index 1 where nums[i] + 2 < 6
• This means finding nums[i] < 4 in range [0, 1)
• Binary search for 4 in [1] returns index 1 (where 4 would be inserted)
• All elements from index 0 to 0 (just element 1) are valid
• Count: 1 valid pair → (0,1) which represents (1,2)

When j = 2 (nums[j] = 3):

• We need to find elements before index 2 where nums[i] + 3 < 6
• This means finding nums[i] < 3 in range [0, 2)
• Binary search for 3 in [1, 2] returns index 2 (where 3 would be inserted)
• All elements from index 0 to 1 (elements 1 and 2) are valid
• Count: 2 valid pairs → (0,2) and (1,2) which represent (1,3) and (2,3)

When j = 3 (nums[j] = 5):

• We need to find elements before index 3 where nums[i] + 5 < 6
• This means finding nums[i] < 1 in range [0, 3)
• Binary search for 1 in [1, 2, 3] returns index 0 (where 1 is located)
• No elements before index 0 satisfy the condition
• Count: 0 valid pairs

Total count: 0 + 1 + 2 + 0 = 3

The three valid pairs in the original array are:

• (1, 2) with sum 1 + 2 = 3 < 6
• (1, 3) with sum 1 + 3 = 4 < 6
• (2, 3) with sum 2 + 3 = 5 < 6

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity consists of two main parts:

• Sorting the array nums.sort() takes O(n × log n) time
• The for loop iterates through all n elements, and for each element, it performs a binary search using bisect_left() which takes O(log n) time. This gives us O(n × log n) for the loop
• Overall: O(n × log n) + O(n × log n) = O(n × log n)

Space Complexity: O(log n)

The space complexity is determined by:

• The sorting algorithm (typically Timsort in Python) uses O(log n) space for its recursive call stack
• The bisect_left() function uses O(1) space as it's implemented iteratively
• Other variables (ans, i, j, x) use O(1) space
• Overall: O(log n)

Where n is the length of the array nums.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to limit the binary search range

The Problem: A common mistake is using bisect_left(nums, target - nums[j]) without the hi=j parameter. This searches the entire array instead of just the elements before position j.

Why it's wrong:

• It violates the constraint i < j by potentially finding indices greater than or equal to j
• It can count the same element pairing with itself when nums[j] + nums[j] < target
• It may double-count pairs (counting both (i,j) and (j,i) as separate pairs)

Incorrect Code:

for j, x in enumerate(nums):
    i = bisect_left(nums, target - x)  # Wrong! Searches entire array
    ans += i

Correct Solution:

for j, x in enumerate(nums):
    i = bisect_left(nums, target - x, hi=j)  # Correct! Only searches [0, j)
    ans += i

Pitfall 2: Using bisect_right instead of bisect_left

The Problem: Using bisect_right would find the rightmost position where we could insert target - x, which gives us one position too far.

Why it's wrong: If there are elements exactly equal to target - nums[j], we don't want to include them since nums[i] + nums[j] would equal target, not be less than it.

Incorrect Code:

i = bisect_right(nums, target - x - 1, hi=j)  # Trying to compensate with -1

Correct Solution:

i = bisect_left(nums, target - x, hi=j)  # Finds first element >= target - x

Pitfall 3: Incorrect handling when all elements before j are valid

The Problem: Not understanding what bisect_left returns when all elements in the search range are valid pairs.

Example scenario: If nums = [1, 2, 8], target = 10, and we're at j = 2 (element 8):

• We search for elements < 10 - 8 = 2 in range [0, 2)
• bisect_left returns 1 (the position where 2 would be inserted)
• This correctly indicates that only index 0 (element 1) forms a valid pair

Key Understanding: bisect_left returns the count of elements strictly less than the search value, which is exactly what we need.