Is there a way to solve this in O(n) time?

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.

This sounds like a homework question.
What have you figured out so far?

Yes ArielLeslie it is a practice I was doing from elsewhere and only managed to achieve an O(n^2) solution was wondering if it was possible to bring it down to O(n)

function answer(a,b,lower,upper){

    const pairs = []

    for(i=0; i<a.length; i++){

        for(k=0; k< b.length; k++){

            const cond1 = lower <= (a[i] * a[i]) + (b[j]*b[j])

            const cond2 = upper >= (a[i] * a[i]) + (b[j]*b[j])

            if(cond1&&cond2) pairs.push([a[i],b[j]])



    return pairs;


This is the solution that i came up with but I was looking at the sliding window technique and was wondering how that can be useful or even if it is possible here

Are the arrays you are given already sorted? If not then it seems like you might not be able to get O(n).

hm… well you can do a ton of pre-processing before going into the loops.
Like, it’s clearly only using the squared numbers from each array.
While doing that, filter out numbers that cannot satisfy the conditions.

Once you did that, maybe what you are left offers a better approach.

This topic was automatically closed 182 days after the last reply. New replies are no longer allowed.