I'm trying to write a program whose input is an array of integers, and its size. This code has to delete the elements which are smaller than the element to the left. We want to find number of times that we have repeat this action to not be able to delete any more elements. Here is my code, it works but I want it to be faster.

Do you have any idea to make this code faster, or another way that is faster than this?

For example, given the array [10, 9, 7, 8, 6, 5, 3, 4, 2, 1], the function should return 2 because [10,9,7,8,6,5,3,4,2,1] → [10,8,4] → [10]

int numberOfTimes(int array[] , int n) {
    int count = 0;
    int flag = 0;
    int sizeCounter = 0;
    while (true){
        for (int i = 0; i < n-1;   i) {
            if (array[i]<= array[i 1]){
                sizeCounter  ;
                array[sizeCounter] = array[i 1];
            } else{
                flag = 1;
            }
        }
        if (flag == 0)
            return count;

        count  ;
        flag = 0;
        n = (sizeCounter 1);
        sizeCounter = 0;
    }
}

CodePudding user response：

This problem can be solved in O(n) time and O(n) space using "monotonic stack".

For each element of the array we will find the number of "actions/turns" it takes to delete the element. In other words, how many turns have to pass, so that all elements between current element (inclusive) and the closest larger element to the left are deleted.

If we know that number (let's call it turns) then we can find maximum of this value for all elements of our array and we'll know the number of turns it takes to remove all elements from the array that can be removed. We'll have our answer.

Now, how do we find that turns value? It's easy, if we have these turns values computed for all elements to the left of the current element. We just find the closest element that is greater than current element and find the maximum number of turns for every element in between that element and the current element. I.e. if current element is at index i, and closest greater element is at index j (j < i and array[j] > array[i]), turns[i] = max(turns[k] 1), for k in [j 1..i-1].

If we do this naively, finding turns for each element would be O(n). Fortunately, it's easy to see, that when we've found j for some i, we won't ever need to consider elements between j and i ever again. Remember, array[j] > array[i] and everything in between j and i is smaller than array[i]. We're looking for the closest array element that is greater than some value, so, if array[i] is not an answer, the whole [j 1..i-1] range is also not an answer, we can go straight to j.

Having this in mind, we arrive to the monotonic stack. Instead of storing turns for every element of array, we store it only for the strictly decreasing subsequence of array that we've visited so far.

Before adding new element to the stack, first we need to remove every element that is smaller than the current element. Then the top of the stack will be our array[j].

As each element is added to the stack and removed exactly once, amortized cost of finding turns for each element is O(1), so the whole algorithm is O(n). In worst case the size of the stack grows to the same size as the array (if array is strictly decreasing). So the space complexity is O(n).

Here is the code (python):

array = [10, 9, 7, 8, 6, 5, 3, 4, 2, 1]
s = [] # monotonic stack of pairs (array[j],turns[j])
count = 0 # result: number of turns to delete all deletable elements

for el in array:
  # initially assuming current element can be deleted
  turns = 1 
  
  # peeking at the top of the stack
  while len(s) > 0 and s[-1][0] <= el:
    _,t = s.pop()
    turns = max(t 1, turns)

  # corner case: current element is the largest so far, cant be deleted
  if len(s) == 0:
    turns = 0
  s.append( (el, turns) )
  count = max(count, turns)

print(count)

Tests:

[10, 9, 7, 8, 6, 5, 3, 4, 2, 1] → 2
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1, 9] → 3
[10, 9, 7, 8, 6, 5, 3, 4, 2, 1, 11] → 2
[] → 0
[1, 2, 3] → 0
[1, 2, 3, 1] → 1
[10, 1, 2, 3, 4, 5] → 5

UPD: I've just read the comments and I'd like to give kudos to @wLui155, who came up with the same core idea before me.