# Two Sum Less Than K Problem

## Description

LeetCode Problem 1099. Given an array of integers nums and an integer k, return the maximum s such that there exists i < j with nums[i] + nums[j] = s and s < k. If no such i, j, s exists, return -1.

Example:

``````1
2
3
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.
``````

## Solution

#### Brute Force Approach

A simple solution is to use the `brute force` approach.

We loop through each element x in the array. For each element, we loop through each of the rest elements x’ to see whether (x + x’ < k), and update s if (x + x’ > s).

The time complexity of this approach is O(n2), and the space complexity is O(1).

#### Two Pointer Approach

We can use the `two pointer` approach similar to the `three sum problem`.

We first sort the array in ascending order, the time complexity of this step is O(nlogn).

We then set two pointers l and r pointing to the first and last element of the array, respectively. If the sum of the two elements pointed by l and r are greater or equal to k, that means the right element is too big (even the smallest left element cannot satisfy the requirement), then we move the right element one step to the left. Otherwise, we check whether the sum is larger than s, if so, we update s with the new sum. We then move the left pointer one step to the right.

When l and r meet, we can stop the search.

The time complexity can be reduced to O(nlogn), and the space complexity is O(n).

## Sample C++ Code

This is a C++ implementation of the two pointer approach.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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

int main() {
vector<int> nums={34,23,1,24,75,33,54,8};
int k = 60;
cout << twoSumLessThanK(nums, k) << endl;
}
``````