Find number of int pair in an array that all values between the pair are smaller than or equal to the both

Question

Given an array of integer, find the number of int pair, so that for each pair a_i, a_j, the number between them, i.e. a_(i+1)...a_(j-1) are all smaller than or equal to a_i and a_j.

Obviously: Adjacent integers should be counted, say a_i and a_(i+1). And it's easy to find an O(n^2) algorithm.

My question is that does anyone have a better solution than O(n^2)?

Answer 1

I believe I have it in O(nlogn).

We shouldn't have to worry about adjacent pairs, as there are (always) n-1 of them; thus we can discount them and simply add n-1 to our final result.

Given the array of ints arr of length n, create the following data structures:

1. An array of booleans dir of length n-1, such that dir[i] = arr[i+1] > arr[i]. These are the directions of movement, where true is increasing, false is decreasing.
2. A map toPeak of int -> int, where toPeak.get(index) for all index that represent a descent returns the index of the relative maximum immediately preceding index.
3. A map toValley of int -> int, where toValley.get(index)for all index that represent an ascent returns the index of the relative minimum immediately preceding index.

Then procede with the algorithm:

• Init a counter = n-1 //Account for adjacent pairs here
• Then you can loop over the indices i <- 0...n-1, and at each:
  • If i represents an ascent (dir[i]):
    • Find the valley index v preceding i (lookup in toValley)
    • Find the peak index p preceding v (look up in toPeak)
    • Binary search the region arr[p...v] for the earliest, closest value equal or lesser than arr[i], occuring at index x.
    • Increment counter by (i-x)
• Return counter

Run time is easy to prove - creating each data structure takes O(n), looping over the indices causes n iterations, and each iteration takes log(n) time to binary search (assuming O(1) map lookup).

Correctness is harder, and I'm not sure how it fairs with equivalent values. Thinking about it now.

Answer 2

I would solve it recursively. It is not possible define the complexity... I think. So let us start(for simplify the code I do not collect them but just print on screen):

void check_next(int*my_arr,int count,int cur_max) 
{
  int temp;
  if(!count || (temp=*my_arr) < cur_max)
       return;
   printf("%d\n",*my_arr);
     check_next(++my_arr,--count,temp);         
}
 void main()
{
  check_next(array,sizeof(array)/sizeof(int),array[0]);
} 

Answer 3

This can actually be done in O(n) with 2 stacks.

The trick is to think about how we can find the pairs of some elements while in a single loop. This can be done in a stack implementation reminiscent of the basic bracket stack solution.

First take input into an array of size n elements.

We need to go forward and then backward through the array to cover all cases of pairs.

One stack (lets call it stack_e) is for the elements of the array while the other is for their indexes (stack_i).

Whenever an element is pushed or popped in stack_e, its corresponding index in stack_i is also popped.

Forward:

1. Add first element before loop
2. If current element is greater than the top of stack, add 1 to total count
3. Pop the stack element and compare current element with new stack top and repeat
4. Once current element is smaller than the top stack element or the stack is empty, push the current element to the stack
5. Repeat for all elements in the array

Step 4 makes it so that if there is a greater element ahead of it, the stack pops it and adds 1 to total. However, there also exist pairs while going backward so we should hence take this into consideration.

Backward:

1. Either use 2 separate stacks or reset the same 2 stacks and reuse them
2. Reverse the array
3. Do all the steps of forward

This finds all the pairs from both the front and back side.

Here was is code for the forward steps:

while (current < n) {
        top_element = stackTop(stack_e).val;
        top_index = stackTop(stack_i).val;
        if (array[current] > top_element) {
            while (stack_e->top != NULL && array[current] > top_element) {
                total++;
                sPop(stack_e);
                sPop(stack_i);
                if (stack_e->top != NULL) {
                    top_element = stackTop(stack_e).val;
                    top_index = stackTop(stack_i).val;
                    
                }
            }
        }
        stackPush(stack_e, array[current]);
        stackPush(stack_i, current);
        current++;
    }

Hopefully, the rest may be trivial with this core logic. Good luck!