Difficulty: Easy | Acceptance: N/A | Paid: No Topics: Array, Two Pointers, Binary Search, Sorting
Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.
- Examples
- Constraints
- Brute Force
- Sorting + Two Pointers
- Sorting + Binary Search
Examples
Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to get 58. Note that 34 + 24 = 58 < 60.
Input: nums = [10,20,30], k = 15
Output: -1
Explanation: In this case it is not possible to get a pair sum less than 15.
Constraints
1 <= nums.length <= 100
1 <= nums[i] <= 1000
1 <= k <= 2000
Brute Force
Intuition Check every possible pair of numbers in the array to see if their sum is less than k, keeping track of the maximum valid sum found.
Steps
- Initialize a variable max_sum to -1.
- Iterate through the array with index i from 0 to n-1.
- Iterate through the array with index j from i+1 to n-1.
- Calculate the sum of nums[i] and nums[j].
- If the sum is less than k and greater than max_sum, update max_sum.
- Return max_sum.
class Solution:
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
max_sum = -1
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
current_sum = nums[i] + nums[j]
if current_sum < k and current_sum > max_sum:
max_sum = current_sum
return max_sum
Complexity
- Time: O(n²)
- Space: O(1)
- Notes: Simple to implement but inefficient for large arrays.
Sorting + Two Pointers
Intuition By sorting the array, we can use a two-pointer technique to efficiently find the maximum sum less than k. One pointer starts at the beginning (smallest values) and the other at the end (largest values).
Steps
- Sort the array in ascending order.
- Initialize left pointer to 0 and right pointer to n-1.
- Initialize max_sum to -1.
- While left < right:
- Calculate the sum of nums[left] and nums[right].
- If the sum is less than k, update max_sum if this sum is larger, and move the left pointer forward to try to increase the sum.
- If the sum is greater than or equal to k, move the right pointer backward to decrease the sum.
- Return max_sum.
class Solution:
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
nums.sort()
left, right = 0, len(nums) - 1
max_sum = -1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum < k:
max_sum = max(max_sum, current_sum)
left += 1
else:
right -= 1
return max_sum
Complexity
- Time: O(n log n)
- Space: O(1) or O(n) depending on the sorting algorithm.
- Notes: More efficient than brute force. Sorting allows us to make greedy decisions.
Sorting + Binary Search
Intuition After sorting the array, for each element nums[i], we can use binary search to find the largest element nums[j] (where j > i) such that nums[i] + nums[j] < k.
Steps
- Sort the array in ascending order.
- Initialize max_sum to -1.
- Iterate through the array with index i from 0 to n-1:
- Calculate the target value as k - nums[i].
- Perform a binary search on the subarray nums[i+1:] to find the largest element strictly less than target.
- If such an element is found, update max_sum with the sum of nums[i] and that element.
- Return max_sum.
class Solution:
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
max_sum = -1
for i in range(n):
target = k - nums[i]
# Binary search for the largest number < target in nums[i+1:]
left, right = i + 1, n
while left < right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
if left > i + 1:
max_sum = max(max_sum, nums[i] + nums[left - 1])
return max_sum
Complexity
- Time: O(n log n)
- Space: O(1) or O(n) depending on the sorting algorithm.
- Notes: Efficient, but the two-pointer approach is generally slightly faster in practice due to lower constant factors.