0
$\begingroup$

There are two sorted arrays A and B containing distinct values. How to find all the pairs $(a,b)$ such that $a \ge 3b$ and a is in A and b is in B. This needs to be done in linear time.

I have tried solving it but it is taking me $n \log n$ time, not $n$. I simply use binary search to look for the value of $b$ corresponding to $a$. But in worst case it will come up as $n \log n$ only.

I have tried to read about it online but found nothing and kind of stuck for the past 2 days. I just want some hints to move in the right direction because I feel that maybe I am missing something very fundamental.

$\endgroup$
4
  • 2
    $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$
    – Raphael
    Commented Mar 3, 2020 at 7:00
  • $\begingroup$ Hint: This is a standard problem; there's plenty of literature on it. But also, if it's homework, you're really supposed to spend thinking on how to solve it, using the tools from class plus some fresh ideas. The lesson is on the way! $\endgroup$
    – Raphael
    Commented Mar 3, 2020 at 7:01
  • $\begingroup$ Do you need to find one pair? output all pairs? count the number of pairs? Please credit the original source where you encountered this problem. $\endgroup$
    – D.W.
    Commented Mar 3, 2020 at 8:01
  • $\begingroup$ I need to find all pairs. $\endgroup$
    – Bajru
    Commented Mar 3, 2020 at 18:44

1 Answer 1

3
$\begingroup$

If you need to list all output pairs, as you say, then the problem can't be solved in any less than quadratic time, for the reason that the output may be of quadratic size. Imagine that $A$ and $B$ are both half the input (say, both length $n$), and \begin{align*} A &= [3n + 1, 3n+2, 3n+3, \ldots, 4n-1, 4n] \\ B &= [1, 2, 3, \ldots, n] \end{align*}

Then the output to your problem is all pairs of an element in $A$ and an element in $B$, and there are $n^2$ such pairs.

Probably there is an additional fact you haven't mentioned, that you don't have to produce all pairs, but you just have to produce a more compact representation of the output (e.g. for each $a \in A$, you only need to produce the maximal $b \in B$ such that $a \ge 3b$).

A hint for this altered version, where you only need the maximal $(a,b)$ pairs:

Imagine you are iterating through both $A$ and $B$ at once, instead of just iterating through $A$ or $B$ separately. So, you are keeping two pointers, one into $A$ and one into $B$. Suppose you have found the maximal pair for $a$, so you know $(a, b)$, and the next element in $A$ after $a$ is $a'$. What should you do?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.