# LeetCode 1099: Two Sum Less Than K

## Problem Restatement

We are given an integer array `nums` and an integer `k`.

We need to find the maximum sum `nums[i] + nums[j]` where `i < j` and `nums[i] + nums[j] < k`.

Return `-1` if no such pair exists.

The official constraints state that `1 <= nums.length <= 100` and `1 <= nums[i] <= 1000`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array `nums` and integer `k` |
| Output | Maximum sum less than `k`, or `-1` |

Function shape:

```python
def twoSumLessThanK(nums: list[int], k: int) -> int:
    ...
```

## Examples

Example 1:

```python
nums = [34, 23, 1, 24, 75, 33, 54, 8]
k = 60
```

Best pair: `(33, 24)` with sum `57 < 60`.

Answer:

```python
57
```

## Key Insight

Sort the array. Use two pointers at both ends.

If the sum is less than `k`, update the answer and move the left pointer right (to try a larger sum).

If the sum is ≥ `k`, move the right pointer left (to decrease the sum).

## Edge Cases

- Check the smallest and largest valid search values; off-by-one errors usually appear at the boundaries.
- Decide whether the predicate is looking for the first true value, the last true value, or an exact match.
- When the target is absent, the loop should still terminate and return the problem-specific failure value.

## Complexity

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Sorting |
| Space | `O(1)` | Two pointers |

## Common Pitfalls

- Do not mix inclusive and half-open bounds inside the same loop.
- Make sure each branch strictly reduces the search interval.

## Implementation

```python
class Solution:
    def twoSumLessThanK(self, nums: list[int], k: int) -> int:
        nums.sort()
        left, right = 0, len(nums) - 1
        result = -1

        while left < right:
            s = nums[left] + nums[right]
            if s < k:
                result = max(result, s)
                left += 1
            else:
                right -= 1

        return result
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.twoSumLessThanK([34,23,1,24,75,33,54,8], 60) == 57
    assert s.twoSumLessThanK([10,20,30], 15) == -1
    assert s.twoSumLessThanK([254,914,110,900,147,441,209,122,571,942,136,350,160,127,178,839], 200) == 176

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---:|---|
| Standard example | `57` | Best pair below 60 |
| No valid pair | `-1` | All pairs sum ≥ 15 |
| Large array | `176` | Best two elements summing < 200 |