Can anyone share approach to solve this problem ? I was not able to do that during the test.
We don't actually need binary search. Just sort and record the 2 largest elements. O(nlogn)
It is a 2-pointer question. Sort by index. 1 pointer went from highest A[i]
and the other pointer went from the lowest A[i]
. As long as the sum is not more than threshold, we advance the low pointer and record the largest 2 elements. Why not just the largest? It is because we have to take care of the fact that we can't choose an index twice, so we record the largest 2 elements. Use the largest element when the value doesn't match, the second largest element when they do match.
Java (Tested with bruteforce sol)
static int solve(int[] A, int[] B, int threshold){
int n = A.length, max = 0, ans = 0, secMax = 0;
int[] idx = IntStream.range(0, n).boxed().sorted(Comparator.comparingInt(o -> A[o])).mapToInt(o -> o).toArray();
for (int i = n-1, j = 0; i >= 0; i--){
while(j < n && A[idx[i]]+A[idx[j]] <= threshold){
if (B[idx[j]]>max){
secMax=max;
max=B[idx[j]];
}else if (B[idx[j]]>secMax){
secMax=B[idx[j]];
}
j++;
}
if (max > 0 && secMax > 0){
int val = max==B[idx[i]]?secMax:max;
ans = Math.max(ans, val + B[idx[i]]);
}
}
return ans;
}