How to reduce the time complexity to calculate number of bounded Slices to O(N)?

Question

An integer K and a non-empty zero-indexed array A consisting of N integers are given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A.

A bounded_slice is a slice in which the difference between the maximum and minimum values in the slice is less than or equal to K. More precisely it is a slice, such that max(A[P], A[P + 1], ..., A[Q]) − min(A[P], A[P + 1], ..., A[Q]) ≤ K. The goal is to calculate the number of bounded_slices.

My solution is given below:

int solution(int K, int A[], int N){

    // write your code in C90
    int p, q, max, min, bndSlice = N;

    for(p = 0; p < (N - 1); p++){
        for(q = (p + 1); q < N; q++){
            MaxMinSlice(A, p, q, &max, &min);

            if((max - min) <= K){
                bndSlice++;
            }

            if(bndSlice > 1000000000){
                return 1000000000;
            }
        }
    }        
    return bndSlice;
}
void MaxMinSlice(int A[], int p, int q, int *max, int *min){

    int i;        
    *max = *min = A[p];

    for(i = p; i <= q; i++){
        if(*max < A[i]){
            *max = A[i];
        }

        if(*min > A[i]){
            *min = A[i];
        }
    }
}

How do I reduce the time complexity of the above code to O(N)?

Answer 1

A solution has been posted here:

https://codility.com/media/train/solution-count-bounded-slices.pdf

Answer 2

Your code is O(n^3). There is a simpler way to make it O(n^2 * log n).

Use Range Minimum Query (RMQ) to preprocess your array, so that MaxMinSlice() needs O(1) to query a the difference of maximum and minimum given (p,q).

RMQ is O(n*logn). So the total time is O(n*log n) + O(n^2)

Answer 3

Are the bounded_slices allowed to overlap? I doubt it's possible to get below O(N^2) in that case (assume the trivial case of all array elements being equal, which means every possible slice is bounded, which means you get a set of slices that goes by N^2, which would suggest O(N^2) complexity).

If the bounded_slices are NOT allowed to overlap:

Set P=Q=1. Set min=max=A[P]. Increase Q, adjusting min and max to A[Q], until (max-min)>K. Then, [P..Q-1] are a bounded slice. Set P=Q and repeat from start until you reach N. This needs O(N) operations.

If the bounded slices ARE allowed to overlap, in the above algorithm, set P=P+1 instead of P=Q when you find a bounded slice. But this would need O(N^2) operations.

Answer 4

edited: The solution is wrong (the slices are supposed to overlap)

This code on jsfiddle

/* values N, K and A[] are given */

var number_of_slices = 0, current_max_bound = 0, current_position = 0;
var current_value = A[current_position]; 
var current_max_bound_value;

while (current_max_bound < N) {

  current_max_bound_value = A[current_max_bound];

  if ( Math.abs(current_max_bound_value - current_value) < K ) {

     current_max_bound = current_max_bound + 1;   


  } else {

     number_of_slices = number_of_slices + 1;
     current_max_bound = current_max_bound + 1;
     current_position = current_max_bound;
     current_value = A[current_position];
  }
} 

console.log('result: ' + number_of_slices);