Target Limited Two Sum: Finding the Best Pair Below a Limit

Target Limited Two Sum

Let's solve a classic problem about working with arrays. An array is just a list of numbers stored in a row, where each number sits at a position called an index. The first number is at index 0, the next at index 1, and so on.

The Problem

You are given:

• An array arr made of non-negative integers (numbers that are zero or bigger — never negative).
• A single number called target.

Your job: pick two different numbers from the array, add them together, and find the largest sum that is still strictly less than the target.

The phrase *strictly less than* is important. It means the sum must be below the target — it cannot be equal to it. So if target = 60, a sum of 59 is fine, but a sum of 60 is not allowed.

If you cannot find any pair whose sum stays under the target, you return -1 to signal "no valid pair exists."

What "two elements at different indices" means

You must use two numbers sitting at different positions in the array. You are not allowed to take one number and add it to itself. For example, you can pair the value at index 0 with the value at index 3, but you cannot pair index 2 with index 2.

This is allowed even if two positions happen to hold the same value. The rule is about positions, not about the values being different.

Walking Through Example 1

Input: arr = [34, 23, 1, 24, 75, 33, 54, 8], target = 60
Output: 58

We need two numbers whose sum is as big as possible but still under 60.

• Try 34 + 24 = 58. Is 58 less than 60? Yes!
• Could we do better? Something like 59? Let's check other pairs. 34 + 33 = 67 — too big, it goes over 60. 54 + 8 = 62 — also too big. 34 + 23 = 57 — valid, but smaller than 58.

So the closest we can get without reaching 60 is 58, using the numbers 34 and 24. That is the answer.

Walking Through Example 2

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

Now the target is much smaller, so most pairs will be too big.

• 34 + 1 = 35. Is 35 less than 36? Yes!
• Anything closer to 36? We would need a sum of 35 or… well, 35 is already the best possible here. Bigger pairs like 34 + 23 = 57 shoot way past 36.

So the answer is 35, using 34 and 1.

How to Think About Solving It

The simplest approach is to check every possible pair:

1. Take the first number and pair it with every number after it.
2. Then take the second number and pair it with every number after it.
3. Keep going until all pairs have been tried.

For each pair, add the two numbers. If the sum is less than the target, remember it — but only keep it if it is bigger than the best sum you have found so far.

At the end, if you found at least one valid sum, return the largest one. If you never found any, return -1.

The key takeaways: always compare sums against the target using "strictly less than," and always keep track of the maximum valid sum as you go.