Two Sum Less Than K

Intuition

• What tripped me up here was that I thought I had to find a smart way to stop the iteration of the pointers. No, just use a max heap and keep track of the max difference that is less than k, and just use the number line to notice that:
  • If your sum is > k, by doing right—, you are getting a lesser number since your array is sorted.

Runtime

• $O(N)$ due to a 2 pointer approach in which each of the pointers can only go N elements at most.

Code

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        i = 0
        j = len(nums) - 1
 
        heap = []
        while i < j:
            cur_sum = nums[i] + nums[j]
            if cur_sum < k:
                heappush(heap, -cur_sum)
                i += 1
            else:
                j -= 1
        
        if not heap:
            return -1
            
        return -heap[0]

Notes

---

References

https://leetcode.com/problems/two-sum-less-than-k/