# Linear time algorithm for finding shifted max

Assume that we are given an array $A[1..n]$ containing nonnegative integers (not necessarily distinct).

Let $B$ be $A$ sorted in the nonincreasing order. We want to compute $$m = \max_{i\in [n]} B[i]+i.$$

The obvious solution is sorting $A$ and then compute $m$. This gives an algorithm that runs in time $O(n \lg n)$ in the worst case.

Is it possible to do better? Can we compute $m$ in linear time?

My main question is the one above. But it would be interesting to know about the following generalization of the problem.

Let $B$ be $A$ sorted according to some comparison oracle $\leq$ and $f$ a function given by an oracle. Given $A$ and oracles for $\leq$ and $f$, what can we say about the time needed to compute $m = \max_{i \in [n]} f(B[i],i)$?

We can still compute $m$ in $O(n \lg n)$ time. But can we prove a super-linear lower-bound for this generalized case?

If the answer is yes does the lower-bound hold if we assume that $\leq$ is the usual order on integers and $f$ is a "nice" function (monotone, polynomial, linear, etc.)?

We can compute $m$ in linear time.

For simplicity suppose that the arrays are 0 based: $A[0..n-1]$, $B[0..n-1]$. We want to compute $m = \max_i B[i]+i$.

Let $max = \max_i A[i]$. Obviously $max \leq m$.

Let $A[j]$ be $B[k]$ after sorting. If $A[j] \leq max - n$ we have $$B[k] + k \leq B[k] + (n-1) = A[j] + (n-1) \leq (max-n) + (n-1) = max-1 < max \leq m.$$

Therefore we can ignore $A[j]$ when $A[j] \leq max - n$. We only need to consider the numbers in the range $[max-n, max]$.

We can use counting sort to sort the numbers in $A$ which are in the range $[max-n, max]$ in linear time and use the sorted list to compute $m$.

• ... mmm ... but what is the cost of C[x]=C[x]+1 ?!? – Marzio De Biasi Oct 9 '13 at 10:14
• is there a problem with your answer? because it seems fine to me: you are saying we only care about array elements with values in $[M-n, M]$, so we can use counting sort. This works for the general problem whenever $|f(B[i], i) - B[i]| = O(n)$ for all $i$. – Sasho Nikolov Oct 10 '13 at 2:23
• Thanks @Marzio. :) I slightly edited your answer for clarity. Feel free to roll-back my edit or edit further. – Kaveh Oct 10 '13 at 4:47
• This solution seems to work also for any $f(x,i)$ where for all $x$ and $i\leq n$, $|f(x,i)-x| = O(n)$. – Kaveh Oct 10 '13 at 7:54
• @Kaveh: edit is ok! I wrote the answer quickly and I was not even sure of its correcteness :-S – Marzio De Biasi Oct 10 '13 at 14:07

If the array $A$ consists of distinct integers, then $m = \max(A) + 1$, since the distance between adjacent entries in $B$ is at least $1$; the situation is more interesting when they need not be distinct.

For your more general question, imagine a situation in which $f(B[i],j)$ is only "interesting" when $i = j$. It seems possible to construct an adversary argument which forces you to query $f(B[i],i)$ for all $i$ before you can know $\max_i f(B[i],i)$, hence you need to sort $A$ in order to find the answer, which takes $\Omega(n\log n)$ comparisons. (There are some complications since it might be the case that we can test whether $A[i] = B[j]$ in constant rather than linear time by querying $f(A[i],j)$.) This is the case even if $f$ is a (high-degree) polynomial.

• What if A has n - 1 zeros and a single one? Then the answer is n, not 1. – Grigory Yaroslavtsev Oct 9 '13 at 5:07
• Hi Yuval. There can be repeated numbers in $A$. As Grigory said the solution doesn't seem to work. – Kaveh Oct 9 '13 at 5:48
• I think I see your idea for the lower-bound argument: given $A$ we can compute $B$ quickly using the query pairs made to $f$ by an algorithm solving the problem in time $o(n\lg n)$. We can make sure the algorithm queries $f$ on all $(B[i],i)$ but we cannot make sure it doesn't query other pairs. However we can set $f$ for other pairs to be a distinguishable value so we can discard those pairs. – Kaveh Oct 9 '13 at 5:53