How do you solve Count Pairs Whose Sum is Less than Target on LeetCode?

Count Pairs Whose Sum is Less than Target (LeetCode #2824) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: By sorting the array first, we can use a two-pointer technique to efficiently count pairs. This reduces the number of comparisons needed.

What is the time complexity of Count Pairs Whose Sum is Less than Target?

The optimal solution for Count Pairs Whose Sum is Less than Target runs in O(n log n) time and uses O(1) space. The sorting step takes O(n log n), and the two-pointer traversal takes O(n), making the overall complexity O(n log n).

What algorithm or data structure is used to solve Count Pairs Whose Sum is Less than Target?

Count Pairs Whose Sum is Less than Target uses the following concepts: Array, Two Pointers, Binary Search, Sorting. The recommended patterns to study are: Hash Map, Array.

Count Pairs Whose Sum is Less than Target — LeetCode #2824 (Easy)

Tags: Array, Two Pointers, Binary Search, Sorting

Related patterns: Hash Map, Array

Brute Force approach

Time complexity: O(n²). Space complexity: O(1).

The brute-force approach checks every possible pair of indices in the array to see if their sum is less than the target. This is straightforward but inefficient for larger inputs.

This complexity arises because we check every possible pair in the array, leading to n(n-1)/2 comparisons, which is O(n²).

Step 1: Initialize a counter to 0 to keep track of valid pairs.
Step 2: Use two nested loops to iterate through all pairs (i, j) where i < j.
Step 3: For each pair, check if nums[i] + nums[j] < target. If true, increment the counter.
Step 4: Return the counter after checking all pairs.

For nums = [-1, 1, 2, 3, 1] and target = 2: 1. i=0, j=1: -1 + 1 = 0 < 2 (count=1) 2. i=0, j=2: -1 + 2 = 1 < 2 (count=2) 3. i=0, j=3: -1 + 3 = 2 (not counted) 4. i=0, j=4: -1 + 1 = 0 < 2 (count=3) 5. i=1, j=2: 1 + 2 = 3 (not counted) 6. i=1, j=3: 1 + 3 = 4 (not counted) 7. i=1, j=4: 1 + 1 = 2 (not counted) 8. i=2, j=3: 2 + 3 = 5 (not counted) 9. i=2, j=4: 2 + 1 = 3 (not counted) 10. i=3, j=4: 3 + 1 = 4 (not counted) Final count = 3.

Optimal Solution approach

Time complexity: O(n log n). Space complexity: O(1).

By sorting the array first, we can use a two-pointer technique to efficiently count pairs. This reduces the number of comparisons needed.

The sorting step takes O(n log n), and the two-pointer traversal takes O(n), making the overall complexity O(n log n).

Step 1: Sort the array nums.
Step 2: Initialize two pointers, one at the start (left) and one at the end (right) of the array.
Step 3: While left < right, check if nums[left] + nums[right] < target. If true, all pairs from left to right are valid, so add (right - left) to the count and move left pointer up. Otherwise, move the right pointer down.

For nums = [-1, 1, 2, 3, 1] and target = 2: 1. Sort nums: [-1, 1, 1, 2, 3] 2. left=0, right=4: -1 + 3 = 2 (not counted, move right) 3. left=0, right=3: -1 + 2 = 1 < 2 (count += 3, left=1) 4. left=1, right=3: 1 + 2 = 3 (not counted, move right) 5. left=1, right=2: 1 + 1 = 2 (not counted, move right) Final count = 3.

Common Mistakes

Mistake 1
Mistake 2

Interview Tips

Tip 1
Tip 2
Tip 3

#2824

Count Pairs Whose Sum is Less than Target

Easy

Array↗Two Pointers↗Binary Search↗Sorting↗Hash Map↗Array↗

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

By sorting the array first, we can use a two-pointer technique to efficiently count pairs. This reduces the number of comparisons needed.

⚙️

Algorithm

3 steps

1Step 1: Sort the array nums.
2Step 2: Initialize two pointers, one at the start (left) and one at the end (right) of the array.
3Step 3: While left < right, check if nums[left] + nums[right] < target. If true, all pairs from left to right are valid, so add (right - left) to the count and move left pointer up. Otherwise, move the right pointer down.

solution.py14 lines

1# Full working Python code
2
3def countPairs(nums, target):
4    nums.sort()
5    count = 0
6    left, right = 0, len(nums) - 1
7    while left < right:
8        if nums[left] + nums[right] < target:
9            count += (right - left)
10            left += 1
11        else:
12            right -= 1
13    return count
14

ℹ

Complexity note: The sorting step takes O(n log n), and the two-pointer traversal takes O(n), making the overall complexity O(n log n).

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.