Target Limited Two Sum

The Problem

Given an array of non-negative integers and a target, find the largest possible sum of two distinct elements that is strictly less than the target. If no such pair exists, return -1.

Input:  arr = [34, 23, 1, 24, 75, 33, 54, 8],  target = 60
Output: 58
Explanation: 34 + 24 = 58 < 60  (best valid sum)

Input:  arr = [10, 20, 30],  target = 15
Output: -1
Explanation: smallest pair sum is 10+20=30 ≥ 15

Examples

Example 1

Input:  arr = [34, 23, 1, 24, 75, 33, 54, 8],  target = 60
Output: 58
Explanation: 34 + 24 = 58 < 60. No pair sums to 59 or higher while staying under 60.

Example 2

Input:  arr = [34, 23, 1, 24, 75, 33, 54, 8],  target = 36
Output: 35
Explanation: 34 + 1 = 35 < 36.

Example 3

Input:  arr = [10, 20, 30],  target = 15
Output: -1
Explanation: All pairs sum to ≥ 30, which is ≥ 15.

Intuition

This is Two Sum with a twist: instead of finding an exact match, we want the closest valid sum from below. The same reduction applies — sort first, then use two pointers — but the decision logic changes slightly.

After sorting:

• If arr[left] + arr[right] < target → this is a valid sum. Record it as a candidate max. Then move left forward to try to find a larger valid sum.
• If arr[left] + arr[right] >= target → this pair is invalid. Move right backward to reduce the sum.

The key insight: when a pair is valid (sum < target), we’ve already found the largest possible sum involving arr[left] (because arr[right] is the max of what’s left). So we greedily move left forward to explore larger pairs.

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Sort["Sort arr"]
  Init["left = 0,  right = n-1,  maxSum = -1"]
  Loop{"left < right?"}
  Calc["sum = arr[left] + arr[right]"]
  Valid{"sum < target?"}
  Record["maxSum = max(maxSum, sum)\nleft++  (try larger sums)"]
  Reduce["right--  (reduce sum below target)"]
  Done(["return maxSum"])

  Sort --> Init --> Loop
  Loop -->|"yes"| Calc --> Valid
  Valid -->|"yes — valid pair"| Record --> Loop
  Valid -->|"no — too large"| Reduce --> Loop
  Loop -->|"no"| Done

Target Limited Two Sum — record the best valid sum on each match, then push left forward to search for something even larger.

Applying the Diagnostic Questions

Q1 — Why “order doesn’t matter, so sorting is permitted”?

Mental model: The problem asks for the largest sum under a threshold. That depends entirely on values — which two values combine to produce the best result within the constraint. A pair (24, 34) giving sum 58 is valid regardless of whether 24 appeared before or after 34 in the input. The answer is a sum, not a position pair.

What breaks if you assumed position mattered? If the problem said “the pair must come from two different halves of the array” or “the second element must appear after the first,” sorting would destroy those positional constraints. Here there is no such constraint — which is why the reduction is safe.

Q3 — Why “both ends give the greedy argument for the largest valid sum”?

Mental model: After sorting, arr[left] is the smallest element and arr[right] is the largest in the remaining window. When arr[left] + arr[right] < target (a valid sum), arr[right] is already the best possible partner for arr[left] — no larger right partner exists. This means arr[left] has already seen its maximum achievable valid sum. Pairing it with any smaller element can only produce a worse result. So record the current sum and move left forward to try a larger anchor.

Concrete trace: sorted [1, 8, 23, 24, 33, 34, 54, 75], target = 60, at step left=3 (24), right=5 (34): sum = 58 < 60. arr[right]=34 is the largest value available for pairing with 24. Moving left to try 33 with 34 gives 67 ≥ 60 — invalid. But 58 was the ceiling for arr[left]=24. Advancing left to 33 asks: “can 33 find a partner that beats 58 while staying under 60?” 33+34=67 — no. Moving right to 33: 33+33 is not possible. The scan continues until pointers cross, having recorded 58 as the best.

What breaks without sorting? Without sorted order, when you find a valid pair you cannot know whether arr[right] is the largest available partner — a larger value might be elsewhere in the unsorted array. The greedy advance of left would be wrong because you’d be discarding arr[left] without knowing it had exhausted its best option. You’d need to scan all remaining values for each left, reverting to O(n²).

Solution

from typing import List

class Solution:
    def target_limited_two_sum(self, arr: List[int], target: int) -> int:
        # Sort the array to enable the two-pointer reduction
        arr.sort()
        n = len(arr)

        # Initialize left pointer at the smallest element
        left   = 0
        # Initialize right pointer at the largest element
        right  = n - 1
        # Track the best valid sum found so far
        maxSum = -1

        # Run while there are unseen pairs remaining
        while left < right:
            total = arr[left] + arr[right]

            if total < target:
                # Valid pair — record it and push left forward to find a larger valid sum
                maxSum = max(maxSum, total)
                left += 1
            else:
                # Sum meets or exceeds target — shrink from the right
                right -= 1

        return maxSum


# --- Test ---
sol = Solution()
print(sol.target_limited_two_sum([34, 23, 1, 24, 75, 33, 54, 8], 60))  # 58
print(sol.target_limited_two_sum([34, 23, 1, 24, 75, 33, 54, 8], 36))  # 35
print(sol.target_limited_two_sum([10, 20, 30], 15))                     # -1
print(sol.target_limited_two_sum([1, 2], 10))                           # 3

Dry Run — Example 1

arr = [34, 23, 1, 24, 75, 33, 54, 8], target = 60

After sort: [1, 8, 23, 24, 33, 34, 54, 75]

Return 58 ✓

Complexity Analysis

Edge Cases

Key Takeaway

Target Limited Two Sum shows that the two-pointer pattern is not just for equality — it works for inequality constraints too. The trick is in the move direction when a valid pair is found: always push left forward (not right) to hunt for a larger valid sum. Moving right backward when invalid reduces the sum toward the valid region.