Two Sum Less Than K

Problem#

Given an array nums and integer k, return the maximum sum nums[i] + nums[j] with i != j and the sum strictly less than k. Return -1 if no pair qualifies.

Examples#

nums = [34,23,1,24,75,33,54,8], k = 60 → 58 (34 + 24)
nums = [10,20,30], k = 15 → -1

Constraints#

1 <= nums.length <= 100, 1 <= nums[i] <= 1000, 1 <= k <= 2000.

Approach#

Sort. Use two pointers from both ends: if the sum is below k, record and move the left pointer up; otherwise move the right pointer down.

Solution#

class Solution {
public:
    int twoSumLessThanK(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int l = 0, r = nums.size() - 1, best = -1;
        while (l < r) {
            int s = nums[l] + nums[r];
            if (s < k) {
                best = max(best, s);
                ++l;
            } else {
                --r;
            }
        }
        return best;
    }
};

import "sort"

func twoSumLessThanK(nums []int, k int) int {
  sort.Ints(nums)
  l, r, best := 0, len(nums)-1, -1
  for l < r {
    s := nums[l] + nums[r]
    if s < k {
      if s > best {
        best = s
      }
      l++
    } else {
      r--
    }
  }
  return best
}

from typing import List

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
        nums.sort()
        l, r, best = 0, len(nums) - 1, -1
        while l < r:
            s = nums[l] + nums[r]
            if s < k:
                if s > best:
                    best = s
                l += 1
            else:
                r -= 1
        return best

var twoSumLessThanK = function(nums, k) {
    nums.sort((a, b) => a - b);
    let l = 0, r = nums.length - 1, best = -1;
    while (l < r) {
        const s = nums[l] + nums[r];
        if (s < k) {
            if (s > best) best = s;
            l++;
        } else {
            r--;
        }
    }
    return best;
};

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1, best = -1;
        while (l < r) {
            int s = nums[l] + nums[r];
            if (s < k) {
                best = Math.max(best, s);
                l++;
            } else {
                r--;
            }
        }
        return best;
    }
}

function twoSumLessThanK(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let l = 0, r = nums.length - 1, best = -1;
    while (l < r) {
        const s = nums[l] + nums[r];
        if (s < k) {
            if (s > best) best = s;
            l++;
        } else {
            r--;
        }
    }
    return best;
}

Editorial#

After sorting, two pointers explore the Pareto frontier of pair sums in O(n). When s < k, increasing l is the only way to potentially raise the sum while staying valid; when s >= k, decreasing r is the only way to shrink it.

Complexity#

Time: O(n log n).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#