3
$\begingroup$

Does someone know how to solve the below?

Assume that the array $A$ is already sorted. And show an $O(n)$-time algorithm that determines whether or not there exist indices $i,j,k$ such that

$A[i] + 4A[j] = A[i] + 5A[k] = 0$.

I came up with an algorithm that uses two double for-loop for each i, j and i,k. But the complexity will be $O(n^2)$..

$\endgroup$
  • $\begingroup$ By substracting A[i] from each equation we have 4A[j] = 5A[k] = -A[i]. By iterating through i, we can do a binary search in each iteration to look for -A[i]/4 and another binary search to look for -A[i]/5, which yields a O(n log n) algorithm. An interesting question would be if we can do it faster. $\endgroup$ – Albert Hendriks Jul 16 at 12:00
  • $\begingroup$ @AlbertHendriks Thanks for your comment! Wow, didn't think about using a binary search! Thanks! $\endgroup$ – Christine Watson Jul 16 at 12:05
  • $\begingroup$ It would be interesting to see though if O(n) is possible, as your question states. Maybe something with remembering the last step(s) of the previous binary search, so that we can have O(1) amortized complexity of each binary search. $\endgroup$ – Albert Hendriks Jul 16 at 12:11
  • $\begingroup$ @AlbertHendriks No binary search needed at all for $O(n)$. $\endgroup$ – orlp Jul 16 at 13:38
2
$\begingroup$

As per a comment of Albert Hendriks, we need to find $i, j, k$ such that $-A[i] = 4A[j] = 5A[k]$.

We can actually do this in a single linear pass. We sweep $i$ from the left, such that $-A[i]$ can only get smaller. We sweep $j, k$ from the right for each possible $i$. But when the left hand side can only get smaller, we don't need to check any $j$ or $k$ again that are bigger than our current $j, k$ since $A$ is sorted, thus our $j, k$ can only ever decrease giving $O(n)$ instead of $O(n^2)$.

In Python:

i = 0
j = k = len(A) - 1

while i < len(A):
   while j >= 0 and -A[i] < 4*A[j]:
       j -= 1

   while k >= 0 and -A[i] < 5*A[k]:
       k -= 1

   if -A[i] == 4*A[j] == 5*A[k]:
       return (i, j, k)

   i += 1

return None
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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