701868. Pair with largest sum which is less than K in the array
Easy
Pair with largest sum which is less than K in the array
Summary
Given an array and a value K, find a pair of elements in the array that has the maximum sum which is less than K. The problem involves arrays and data structures, requiring a combination of algorithmic thinking and computational efficiency.
Detailed Explanation
To solve this problem, we can start by sorting the array in ascending order. This will allow us to efficiently iterate through the array and find pairs with sums that are less than K.
Here's a step-by-step breakdown of the solution:
- Sort the array in ascending order.
- Initialize two pointers, one at the beginning of the array (i) and one at the end of the array (j).
- Calculate the sum of the elements at indices i and j (sum = arr[i] + arr[j]).
- If the sum is less than K, update the maximum sum if necessary.
- Move the pointers towards each other based on whether the current sum is greater or less than K. If the sum is greater than K, move the pointer at the higher value closer to the middle. If the sum is less than K, move both pointers closer to the middle.
- Continue iterating until the pointers meet in the middle.
The time complexity of this solution is O(n log n) due to the sorting step, where n is the length of the array. The space complexity is O(1), as we only use a constant amount of space to store the pointers and sum.
+---------------+
| i | j |
+---------------+
^ ^
| |
| arr[0] |
| arr[n-1] |
v v
+---------------+
Optimized Solutions
Java
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {10, 2, 5, 3};
int K = 7;
int maxSum = findMaxSumLessThanK(arr, K);
System.out.println("Maximum sum less than " + K + ": " + maxSum);
}
public static int findMaxSumLessThanK(int[] arr, int K) {
Arrays.sort(arr);
int i = 0;
int j = arr.length - 1;
int maxSum = Integer.MIN_VALUE;
while (i < j) {
int sum = arr[i] + arr[j];
if (sum >= K) {
j--;
} else {
maxSum = Math.max(maxSum, sum);
i++;
}
}
return maxSum;
}
}