Solution
Approach 1: Sort
Intuition and Algorithm
For all elements like A[i] = v
, let's write the indices i
in sorted order of their values v
. For example with A[0] = 7, A[1] = 2, A[2] = 5, A[3] = 4
, we can write the order of indices i=1, i=3, i=2, i=0
.
Then, whenever we write an index i
, we know there was a ramp of width i  min(indexes_previously_written)
(if this quantity is positive). We can keep track of the minimum of all indexes previously written as m
.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: , depending on the implementation of the sorting function.
Approach 2: Binary Search Candidates
Intuition
Consider i
in decreasing order. We want to find the largest j
with A[j] >= A[i]
if it exists.
Thus, the candidates for j
are decreasing: if there is j1 < j2
and A[j1] <= A[j2]
then we strictly prefer j2
.
Algorithm
Let's keep a list of these candidates j
. For example, with A = [0,8,2,7,5]
, the candidates for i = 0
would be candidates = [(v=5, i=4), (v=7, i=3), (v=8, i=1)]
. We keep the list of candidates
in decreasing order of i
and increasing order of v
.
Now we can binary search to find the largest j
with A[j] >= A[i]
: it's the first one in this list of candidates with v >= A[i]
.
Complexity Analysis

Time Complexity: , where is the length of
A
. 
Space Complexity: .
Analysis written by: @awice.