how many consecutive elements are smaller before each item in the array

Question

Given an array of N < 10 000 elements, for each position i in the array, find (in the most efficient way) how many consecutive elements starting from it's left ( i.e from position i-1 to 0) are smaller or equal to array[i].

here's an example:

Array: 4 3 6 1 1 2 8 5 9
Res:   0 0 2 0 1 2 6 0 8
( pos 0 (element 4) -> 0 consecutive elements before it,
  pos 1 (element 3) -> 0 consecutive elements before it smaller than 3 (4>3)
  pos 2 (element 6) -> 2 consecutive elements before it smaller than 6 (4,3)
  and so on..
)

I would assume it's a dynamic programming question since it says in the problem 'the most efficient way' and in the solution it says there's an O(n) solution.

The O(n^2) solution is straightforward, two loops, counting the elements.

Here's my thought about how the 0(n). One would assume:

for (int i = 1; i < array.Length; i++) {
   if (array[i-1] > array[i])
   {
      c [i] = 0;
   }
   else {
      c [i] = c [i - 1] + MAGIC_FORMULA;
   }
}

Obviously, if I find an element greater than the next one, the result is clearly 0 (no numbers smaller than it on the left). But what does the previous result tell me so I can use dynamic programming? I can't find any recurrence for that case. Also, that formula would have to be obtainable in O(1) for the whole solution to be O(n), right? Thought about using a hashset, but couldn't figure it out. Thought about using some modified version of kadane's algorithm, but no luck.

I'm dying to understand the O(n) solution. I've thought about the O(n) solution all day and I'm really stuck.

I'm not native so any help making this question better/more understandable would be really appreciated.

Answer 1

There is a linear solution, however it doesn't use dynamic programming, but rather a simple loop and a stack. First you can make the following observation: computing "the number of consecutive elements smaller or equal than c[i]" is almost the same task as finding "the greater index j <= i such that c[j] > c[i]".

The idea is as follows: for each i (sweeping from left i = 0 to right i = n - 1), we maintain the set of all indices j such that c[j] > c[k] for all j < k < i. This set can be stored in a stack, the lowest values at the top. When you read c[i], you pop elements until you get an index j such that c[j] > c[i]. This is the wanted index. Then you can push i on the stack.

Example: s is the stack. Here ans[i] will be max{j <= i | c[j] > c[i]}. ans[i] will be -1 if the previous set is empty.

i    0 1 2 3 4 5 6 7 8
c[i] 4 3 6 1 1 2 8 5 9
------------------------
i = 0:
    - s = []:     ans[0] = -1
    - push i:     s = [0]
i = 1:
    - s = [0]:    c[1] < c[0] -> ans[1] = 1
    - push i:     s = [0, 1]
i = 2:
    - s = [0, 1]: c[2] >= c[1] -> pop
      s = [0]:    c[2] >= c[0] -> pop
      s = []:     ans[2] = -1
    - push i:     s = [2]
i = 3:
    - s = [2]:    c[3] < c[2] -> ans[3] = 2
    - push i:     s = [2, 3]
i = 4:
    - s = [2, 3]: c[4] >= c[3] -> pop
      s = [2]:    c[4] < c[2] -> ans[4] = 2
    - push i:     s = [2, 4]
i = 5
    - s = [2, 4]: c[5] >= c[3] -> pop
      s = [2]:    c[5] < c[2] -> ans[5] = 2
    - push i:     s = [2, 5]
i = 6
    - s = [2, 5]: c[6] >= c[5] -> pop    
      s = [2]:    c[6] >= c[2] -> pop
      s = [] ->   ans[6] = -1
    - push i:     s = [6]
i = 7
    - s = [6]:    c[7] < c[6] -> ans[7] = 6
    - push i:     s = [6, 7]
i = 8
    - s = [6, 7]: c[8] >= c[7] -> pop
      s = [6]:    c[8] >= c[6] -> pop
      s = [] ->   ans[8] = -1
    - push i:     s = [8]