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

So, apparently, after 5 years since when the original question was posted, I found this problem while preparing for my Algorithms class. This is, to this day, the only solution I've found on the internet. It took me quite a bit of time to code the solution, so I am posting it here. Somebody might need it later. My code is written in Python3 and is refactored to the best of my abilities.

from collections import  deque

def less_then_count(arr):
    stack = deque()
    ans = [0] * len(arr)    
  
    for i in range(len(arr)):
        while len(stack)>0 and arr[i] >= arr[stack[-1]]:
            stack.pop()
        ans[i] = i
        if len(stack) > 0:
            ans[i] -= stack[-1]+1
        stack.append(i)
    
    return ans

print(*less_then_count([1,2,4,2,5]))
print(*less_then_count([4, 3, 6, 1, 1, 2, 8, 5, 9]))

Answer 2

(Editors/moderators please read my last comment on the selected answer to the question, before deleting this one.)

Stack operations

In our first example of aggregate analysis, we analyze stacks that have been aug- mented with a new operation. Section 10.1 presented the two fundamental stack operations, each of which takes O(1) time:

PUSH(S, x) pushes object x onto stack S.

POP(S) pops the top of stack S and returns the popped object.

Since each of these operations runs in O(1) time, let us consider the cost of each to be 1. The total cost of a sequence of n PUSH and POP operations is therefore n, and the actual running time for n operations is therefore (n).

Now we add the stack operation MULTIPOP(S,k), which removes the k top objects of stack S, or pops the entire stack if it contains fewer than k objects. In the following pseudocode, the operation STACK-EMPTY returns TRUE if there are no objects currently on the stack, and FALSE otherwise.

What is the running time of MULTIPOP(S, k) on a stack of s objects? The actual running time is linear in the number of POP operations actually executed, and thus it suffices to analyze MULTIPOP in terms of the abstract costs of 1 each for PUSH and POP. The number of iterations of the while loop is the number min(s,k) of objects popped off the stack. For each iteration of the loop, one call is made to POP in line 2. Thus, the total cost of MULTIPOP is min(s, k), and the actual running time is a linear function of this cost.

Let us analyze a sequence of n PUSH, POP, and MULTIPOP operations on an ini- tially empty stack. The worst-case cost of a MULTIPOP operation in the sequence is O(n), since the stack size is at most n. The worst-case time of any stack opera- tion is therefore O(n), and hence a sequence of n operations costs O(n2), since we may have O(n) MULTIPOP operations costing O(n) each. Although this analysis is correct, the O(n2) result, obtained by considering the worst-case cost of each operation individually, is not tight.

Using aggregate analysis, we can obtain a better upper bound that considers the entire sequence of n operations. In fact, although a single MULTIPOP operation can be expensive, any sequence of n PUSH, POP, and MULTIPOP operations on an initially empty stack can cost at most O(n). Why? Each object can be popped at most once for each time it is pushed. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP, is at most the number of PUSH operations, which is at most n. For any value of n, any sequence of n PUSH, POP, and MULTIPOP operations takes a total of O(n) time. The average cost of an operation is O(n)/n = O(1). In aggregate analysis, we assign the amortized cost of each operation to be the average cost. In this example, therefore, all three stack operations have an amortized cost of O(1).

Answer 3

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]