Teaching Kids Programming – Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Example 1:
Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
– (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
– (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target
– (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

Example 2:
Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
– (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
– (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
– (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
– (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
– (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
– (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
– (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
– (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
– (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
– (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target

Constraints:
1 <= nums.length == n <= 50
-50 <= nums[i], target <= 50

Count Pairs Whose Sum is Less than Target (Brute Force Algorithm)

We can perform a brute force algorithm to check every pair (i, j) where index i is less than j. This is O(N^2).

1
2
3
4
5
6
7
8
9

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[j] + nums[i] < target:
                    ans += 1
        return ans

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        ans = 0
        n = len(nums)
        for i in range(n):
            for j in range(i):
                if nums[j] + nums[i] < target:
                    ans += 1
        return ans

Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)

If we sort the array, which takes O(NLogN) time e.g. via Quick Sort or Merge Sort, then we can apply two pointer algorithm. When the sum is less than the target, we know there are R-L pairs which sum less than target. We accumulate the answer and then move the left pointer to the right (increase the sum). Otherwise, we need to move the right pointer left, to bring down the sum.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        i = 0
        j = len(nums) - 1
        ans = 0
        while i < j:
            if nums[i] + nums[j] < target:
                ans += j - i
                i += 1
            else:
                j -= 1
        return ans

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        nums.sort()
        i = 0
        j = len(nums) - 1
        ans = 0
        while i < j:
            if nums[i] + nums[j] < target:
                ans += j - i
                i += 1
            else:
                j -= 1
        return ans

The two pointer algorithm takes O(N) time to complete when two pointers (Left and Right) meet in the middle. The overall time complexity is dominated by Sorting.

This problem is similar to these Two Sum Variations:

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —