Teaching Kids Programming – Sum of Two Numbers Less Than Target using Two Pointer Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of integers nums and an integer target, return the sum of the largest pair of numbers in nums whose sum is less than target. You can assume that there is a solution.

Constraints
2 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [5, 1, 2, 3]
target = 4
Output
3
Explanation
Sum of the largest pair of numbers less than 4 is 1 + 2 = 3.

Hints:
Two pointers (left& right) and keep maximizing the result

Bruteforce Algorithm to Get the Two Sum Maximum less than Target

Bruteforcing all possible pairs takes O(N^2) and we then can check the sum of each pair and record the maximum if it is less than target.

1
2
3
4
5
6
7
8
9

class Solution:
    def largestTwoSumLessThanTarget(self, nums, target):
        n = len(nums)
        ans = -math.inf
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] < target:
                    ans = max(ans, nums[i] + nums[j])
        return ans

class Solution:
    def largestTwoSumLessThanTarget(self, nums, target):
        n = len(nums)
        ans = -math.inf
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] < target:
                    ans = max(ans, nums[i] + nums[j])
        return ans

Two Pointer Algorithm to Get the Largest Two Sum less than Target

If we sort the array (which takes O(NLogN) by the way), we can apply two pointer in O(N) time. And move the corresponding pointer respectively.

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

class Solution:
    def largestTwoSumLessThanTarget(self, nums, target):
        nums.sort()
        i, j = 0, len(nums) - 1
        ans = -math.inf
        while i < j:
            x = nums[i] + nums[j]
            if x < target:
                ans = max(ans, x)
                i += 1
            else:
                j -= 1
        return ans

class Solution:
    def largestTwoSumLessThanTarget(self, nums, target):
        nums.sort()
        i, j = 0, len(nums) - 1
        ans = -math.inf
        while i < j:
            x = nums[i] + nums[j]
            if x < target:
                ans = max(ans, x)
                i += 1
            else:
                j -= 1
        return ans

The overall time complexity is O(NLogN) as sorting is dominant.

See also: Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target

See also: Teaching Kids Programming – Lowest Sum of Pair Larger than Target via Two Pointer

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) —