How to find Find max right using stack?

Question

I was solving the question where we need to find rightSpecialValue for each A[i] in given array A. RightSpecialValue is defined below.

RightSpecialValue: For an index i, it is defined as the index j such that A[j]>A[i] and (j>i). If multiple A[j]'s are present in multiple positions, the RightSpecialValue is the minimum value of j. Here RightSpecialValue is the index j and not A[j].

It could be easily solved using by using stack in O(n) but what if it is changed to "If multiple A[j]'s are present in multiple positions, the RightSpecialValue is the maximum value of j. Here RightSpecialValue is the index j and not A[j]."

is there any better solution than O(n^2)?

Answer 1

is there any better solution than O(n^2)?

There is at least a O(log) solution for it:

• Maintain a vector (with direct indexing, to which only elements are pushed, never popped): it will gradually get populated with indices for which it is true that all values after an included index are less than the value at that index.

• Iterate the array from right to left, and for each visited index i do:

  • Perform a binary search in the vector with the current value a[i], so that we find the greatest j on the vector for which a[j] > a[i], if any. Register this j (or a default -1) for this index i as part of the solution.
  • If a[i] is greater than the value at the index that is on the top of the vector, then push i on the vector.

The time complexity of this algorithm is O(log1 + log2 + log3 + ... + log) = O(log).

Answer 2

Yes you could solve this new problem in O(nlogn) by creating a candidates list which is initially empty and holds indexes. Now you go backwards and for each index i you find the smallest a[j] > a[i] by bisection where j are the indexes in the candidates list (the candidates list is sorted ascending). If you didn't find such an index add i to the candidates (and set i to -1 or null or whatever in result). If you found an index j in candidates set result[i] = j.