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

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a list of integers nums and an integer target. Return the lowest sum of pair of numbers that is greater than target. You can assume that a solution exists.

Constraints
2 ≤ n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [1, 3, 5, 9, 13]
target = 8
Output
10
Explanation
We pick 1 and 9

Hints:
Consider sorting the list and fixing the smaller number of the pair.
sorting, binarysearch or two pointer approach

Lowest Sum of Pair Larger than Target via Bruteforce Algorithnm

We can bruteforce the pair of numbers in O(N^2) time, and then compute the lowest sum that is larger than the target.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def lowestSumLargerThanTarget(self, nums, target):
        ans = math.inf
        n = len(nums)
        for i in range(n):
            for j in range(i):
                x = nums[i] + nums[j]
                if x > target:
                    ans = min(ans, x)
        return ans

class Solution:
    def lowestSumLargerThanTarget(self, nums, target):
        ans = math.inf
        n = len(nums)
        for i in range(n):
            for j in range(i):
                x = nums[i] + nums[j]
                if x > target:
                    ans = min(ans, x)
        return ans

Lowest Sum of Pair Larger than Target via Two Pointer

Alternatively, we can sort the array in O(NLogN) time, and apply two pointer algorithm O(N). Moving the right pointer to the left when the sum is larger and also update the lowest sum. Otherwise, move the left pointer to the right when the sum is smaller than the target.

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

class Solution:
    def lowestSumLargerThanTarget(self, nums, target):
        nums.sort()
        left, right = 0, len(nums) - 1
        ans = math.inf
        while left < right:
            x = nums[left] + nums[right]
            if x > target:
                ans = min(ans, x)
                right -= 1
            else:
                left += 1
        return ans

class Solution:
    def lowestSumLargerThanTarget(self, nums, target):
        nums.sort()
        left, right = 0, len(nums) - 1
        ans = math.inf
        while left < right:
            x = nums[left] + nums[right]
            if x > target:
                ans = min(ans, x)
                right -= 1
            else:
                left += 1
        return ans

The overall complexity is O(NLogN) due to sorting. THe space complexity is O(1).

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

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

–EOF (The Ultimate Computing & Technology Blog) —