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)?
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:
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.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𝑛).