Bounded square sum algorithm

The problem goes as follows:

You are given two arrays of integers a and b, and two integers lower and upper.
Your task is to find the number of pairs (i, j) such that lower ≤ a[i] * a[i] + b[j] * b[j] ≤ upper.
Example:
For a = [3, -1, 9], b = [100, 5, -2], lower = 7, and upper = 99, the output should be boundedSquareSum(a, b, lower, upper) = 4.
There are only four pairs that satisfy the requirement:
If i = 0 and j = 1, then a[0] = 3, b[1] = 5, and 7 ≤ 3 * 3 + 5 * 5 = 9 + 25 = 36 ≤ 99.
If i = 0 and j = 2, then a[0] = 3, b[2] = -2, and 7 ≤ 3 * 3 + (-2) * (-2) = 9 + 4 = 13 ≤ 99.
If i = 1 and j = 1, then a[1] = -1, b[1] = 5, and 7 ≤ (-1) * (-1) + 5 * 5 = 1 + 25 = 26 ≤ 99.
If i = 2 and j = 2, then a[2] = 9, b[2] = -2, and 7 ≤ 9 * 9 + (-2) * (-2) = 81 + 4 = 85 ≤ 99.
For a = [1, 2, 3, -1, -2, -3], b = [10], lower = 0, and upper = 100, the output should be boundedSquareSum(a, b, lower, upper) = 0.
Since the array b contains only one element 10 and the array a does not contain 0, it is not possible to satisfy 0 ≤ a[i] * a[i] + 10 * 10 ≤ 100.

Now, I know there is a brute force way to solve this, but what would be the optimal solution for this problem?

2 Answers

Sort the smaller array using the absolute value of the elements, then for each element in the unsorted array, binary search the interval on the sorted one.

You can break loop when calculation goes higher than upper limit. I will reduce execution time.

function boundedSquareSum(a, b, lower, upper) { let result = 0; a = a.sort((i,j) => Math.abs(i) - Math.abs(j)); b = b.sort((i,j) => Math.abs(i) - Math.abs(j)) for(let i = 0; i < a.length; i++) { let aValue = a[i] ** 2; if(aValue > upper) { break; // Don't need to check further } for(let j = 0; j < b.length; j++) { let bValue = b[j] ** 2; let total = aValue + bValue; if(total > upper) { break; // Don't need to check further } if((total >= lower && total <= upper) ) { result++; } } } return result;
}