Is Two Sum Less Than K easy or hard?

Two Sum Less Than K is classified as an easy problem. The main challenge is recognizing that sorting enables efficient pair scanning with two pointers, a common pattern used across many array problems.

Two Sum Less Than K Python/Java solution

In Python or Java, the typical solution sorts the array first and then applies two pointers. Move the right pointer when the sum is too large and move the left pointer when the sum is valid to search for a larger candidate. This approach is concise and runs in O(n log n) time.

How to solve Two Sum Less Than K in O(n)?

A pure O(n) solution is not possible for arbitrary unsorted arrays because the elements must be organized to efficiently compare candidate pairs. Sorting enables structured comparisons, after which the two pointers technique finds the answer in O(n). The overall complexity becomes O(n log n).

What is the best approach for Two Sum Less Than K?

The best approach is sorting the array and using the two pointers technique. After sorting, place one pointer at the start and one at the end, then adjust them based on whether the current sum is less than or greater than k. This produces the optimal pair in a single linear scan after sorting, giving O(n log n) time and O(1) extra space.

Is Two Sum Less Than K asked at Google/Amazon/Meta?

Two Sum variations frequently appear in interviews at companies like Amazon, Google, and Meta. This specific variation tests understanding of sorting, two pointers, and pair optimization under constraints. It is commonly used as an easy warm‑up or early screening problem.

What data structure is used in Two Sum Less Than K?

The problem primarily uses arrays along with algorithmic techniques such as sorting, binary search, and the two pointers pattern. No additional complex data structures are required, which keeps the space complexity minimal.

What is the time complexity of Two Sum Less Than K?

The optimal solution runs in O(n log n) time due to the sorting step. After sorting, the two pointer scan runs in O(n). Space complexity is O(1) if the sort is in-place, though some language implementations may use O(log n) stack space.

Description Hints 2 Solution Video 13:10

1099. Two Sum Less Than K

Easy61.9% acceptance1 companyPremium elsewhere, free here

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.

Example 1:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

Example 2:

Input: nums = [10,20,30], k = 15
Output: -1
Explanation: In this case it is not possible to get a pair sum less that 15.

Constraints:

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

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

What if we have the array sorted?

Hint 2

Loop the array and get the value A[i] then we need to find a value A[j] such that A[i] + A[j] < K which means A[j] < K - A[i]. In order to do that we can find that value with a binary search.

13:10

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution