Problem explanation

The problem is quite straightforward. You are given an array 'A' of integers and an integer 'K'. Your task is to find two numbers in the array whose sum is less than 'K' and closest to 'K'. If no such pair exists, you should return -1.

For example, given A = [34,23,1,24,75,33,54,8] and K = 60, the maximum possible pair sum less than 60 is 58 (given by the sum of 34 and 24).

In another example, A = [10,20,30] and K = 15, there is no pair of numbers that sum to less than 15. Hence, the output should be -1.

Solution approach

The solution uses a two pointer method to find the pair of numbers. It first sorts the array in ascending order and initializes two pointers, one at the beginning (l) and the other at the end (r) of the array.

It then enters a while loop and checks if the sum of the numbers pointed by l and r is less than K. If it is, it checks if this sum is greater than the current maximum sum ans and if so, updates ans. It then increments l to check the next pair.

If the sum of the numbers pointed by l and r is greater than or equal to K, it means that we cannot find a pair whose sum is less than K by including the number at r. Hence, it decrements r.

The while loop continues until l is no longer less than r.

Python solution

1
2 python
3class Solution:
4    def twoSumLessThanK(self, nums: List[int], k: int) -> int:
5        nums.sort()
6        l = 0
7        r = len(nums) - 1
8        ans = -1
9        
10        while l < r:
11            if nums[l] + nums[r] < k:
12                ans = max(ans, nums[l] + nums[r])
13                l += 1
14            else:
15                r -= 1
16                
17        return ans

C++ solution

1
2 cpp
3class Solution {
4public:
5    int twoSumLessThanK(vector<int>& nums, int k) {
6        sort(nums.begin(), nums.end());
7
8        int l = 0;
9        int r = nums.size() - 1;
10        int ans = -1;
11        
12        while (l < r) {
13            if (nums[l] + nums[r] < k) {
14                ans = max(ans, nums[l] + nums[r]);
15                l++;
16            } else {
17                r--;
18            }
19        }
20
21        return ans;
22    }
23};

JavaScript solution

1
2 js
3class Solution {
4    twoSumLessThanK(nums, k) {
5        nums.sort((a, b) => a - b);
6        
7        let l = 0;
8        let r = nums.length - 1;
9        let ans = -1;
10        
11        while (l < r) {
12            if (nums[l] + nums[r] < k) {
13                ans = Math.max(ans, nums[l] + nums[r]);
14                l++;
15            } else {
16                r--;
17            }
18        }
19        
20        return ans;
21    }
22};

Java solution

1
2 java
3class Solution {
4    public int twoSumLessThanK(int[] nums, int K) {
5        Arrays.sort(nums);
6        
7        int l = 0, r = nums.length - 1, ans = -1;
8        
9        while (l < r) {
10            if (nums[l] + nums[r] < K) {
11                ans = Math.max(ans, nums[l] + nums[r]);
12                l++;
13            } else {
14                r--;
15            }
16        }
17        
18        return ans;
19    }
20}

C# solution

1
2 csharp
3public class Solution {
4    public int TwoSumLessThanK(int[] nums, int K) {
5        Array.Sort(nums);
6        
7        int l = 0, r = nums.Length - 1, ans = -1;
8        
9        while (l < r) {
10            if (nums[l] + nums[r] < K) {
11                ans = Math.Max(ans, nums[l] + nums[r]);
12                l++;
13            } else {
14                r--;
15            }
16        }
17        
18        return ans;
19    }
20}

In all solutions, we use a two pointer method to efficiently find the pair of numbers that satisfies the problem conditions. To make this method work, we need to first sort the input array.From there, we initialize the left pointer at the beginning of the array and the right pointer at the end. We continue moving the pointers towards each other until they meet, while constantly checking if the sum of current pair of numbers is below 'K' and whether it is the closest so far.

The logic behind the two pointers technique is that when we sort our array, we know that sum increases when we move from left to right. Therefore, by starting with the largest pair of numbers (rightmost and leftmost), and then decrementing the right pointer if the sum is above 'K' or incrementing the left pointer if below, ensures that we can find the pair that adds up to the maximum value under 'K' in an efficient way.

In terms of algorithm complexity, sorting the array takes up the most time, making our algorithm run in O(nlogn) time where n is the number of elements in the input array. For space complexity, it's O(n) due to the storage used for sorting, or O(1) if the sort is done in-place.

This solution works in Python, C++, JavaScript, Java, and C#, and is efficient for large datasets because of its linear time complexity.

Remember to always verify the solution with multiple test cases to make sure it covers all edge cases. Try it with an empty array, array of one element, array with negative numbers, or an array where all pairs sum up to more than 'K'. Ensure your solution returns the expected results in all these scenarios before considering it correct.

By understanding the problem, following through with the approach, and implementing the solution, you will get a hang of two pointer method that is also a frequent topic in coding interviews, and which can be used in solving other array problems such as 3Sum, trapping rain water, etc.