Counting bounded slice codility

Question

I have recently attended a programming test in codility, and the question is to find the Number of bounded slice in an array..

I am just giving you breif explanation of the question.

A Slice of an array said to be a Bounded slice if Max(SliceArray)-Min(SliceArray)<=K.

If Array [3,5,6,7,3] and K=2 provided .. the number of bounded slice is 9,

first slice (0,0) in the array Min(0,0)=3 Max(0,0)=3 Max-Min<=K result 0<=2 so it is bounded slice

second slice (0,1) in the array Min(0,1)=3 Max(0,1)=5 Max-Min<=K result 2<=2 so it is bounded slice

second slice (0,2) in the array Min(0,1)=3 Max(0,2)=6 Max-Min<=K result 3<=2 so it is not bounded slice

in this way you can find that there are nine bounded slice.

(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).

Following is the solution i have provided

private int FindBoundSlice(int K, int[] A)
{
    int BoundSlice=0;
    Stack<int> MinStack = new Stack<int>();
    Stack<int> MaxStack = new Stack<int>();




    for (int p = 0; p < A.Length; p++)
    {
        MinStack.Push(A[p]);
        MaxStack.Push(A[p]);
        for (int q = p; q < A.Length; q++)
        {
            if (IsPairBoundedSlice(K, A[p], A[q], MinStack, MaxStack))
                BoundSlice++;
            else
                break;
        }
    }

    return BoundSlice;
}

private bool IsPairBoundedSlice(int K, int P, int Q,Stack<int> Min,Stack<int> Max)
{
    if (Min.Peek() > P)
    {
        Min.Pop();
        Min.Push(P);
    }

    if (Min.Peek() > Q)
    {
        Min.Pop();
        Min.Push(Q);
    }

    if (Max.Peek() < P)
    {
        Max.Pop();
        Max.Push(P);
    }

    if (Max.Peek() < Q)
    {
        Max.Pop();
        Max.Push(Q);
    }

    if (Max.Peek() - Min.Peek() <= K)
        return true;
    else
        return false;
}

But as per codility review the above mentioned solution is running in O(N^2), can anybody help me in finding the solution which runs in O(N).

Maximum Time Complexity allowed O(N). Maximum Space Complexity allowed O(N).

Answer 1

Disclaimer

It is possible and I demonstrate it here to write an algorithm that solves the problem you described in linear time in the worst case, visiting each element of the input sequence at a maximum of two times.

This answer is an attempt to deduce and describe the only algorithm I could find and then gives a quick tour through an implementation written in Clojure. I will probably write a Java implementation as well and update this answer but as of now that task is left as an excercise to the reader.

EDIT: I have now added a working Java implementation. Please scroll down to the end.

EDIT: Notices that PeterDeRivaz provided a sequence ([0 1 2 3 4], k=2) making the algorithm visit certain elements three times and probably falsifying it. I will update the answer at later time regarding that issue.

Unless I have overseen something trivial I can hardly imagine significant further simplification. Feedback is highly welcome.

_{(I found your question here when googling for codility like exercises as a preparation for a job test there myself. I set myself aside half an hour to solve it and didn't come up with a solution, so I was unhappy and spent some dedicated hammock time - now that I have taken the test I must say found the presented exercises significantly less difficult than this problem).}

Observations

For any valid bounded slice of size we can say that it is divisible into the triangular number of size bounded sub-slices with their individual bounds lying within the slices bounds (including itself).

Ex. 1: [3 1 2] is a bounded slice for k=2, has a size of 3 and thus can be divided into (3*4)/2=6 sub-slices:

    [3 1 2]      ;; slice 1
  [3 1] [1 2]    ;; slices 2-3
[3]   [1]   [2]  ;; slices 4-6

Naturally, all those slices are bounded slices for k.

When you have two overlapping slices that are both bounded slices for k but differ in their bounds, the amount of possible bounded sub-slices in the array can be calculated as the sum of the triangular numbers of those slices minus the triangular number of the count of elements they share.

Ex. 2: The bounded slices [4 3 1] and [3 1 2] for k=2 differ in bounds and overlap in the array [4 3 1 2]. They share the bounded slice [3 1] (notice that overlapping bounded slices always share a bounded slice, otherwise they could not overlap). For both slices the triangular number is 6, the triangular number of the shared slice is (2*3)/2=3. Thus the array can be divided into 6+6-3=9 slices:

      [4 3 1]   [3 1 2]         ;; 1-2 the overlapping slices 
  [4 3]  6  [3 1]  6  [1 2]     ;; 3-5 two slices and the overlapping slice
[4]     [3]   3   [1]     [2]   ;; 6-9 single-element slices

As observable, the triangle of the overlapping bounded slice is part of both triangles element count, so that is why it must be subtracted from the added triangles as it otherwise would be counted twice. Again, all counted slices are bounded slices for k=2.

Approach

The approach is to find the largest possible bounded slices within the input sequence until all elements have been visited, then to sum them up using the technique described above.

A slice qualifies as one of the largest possible bounded slices (in the following text often referred as one largest possible bounded slice which shall then not mean the largest one, only one of them) if the following conditions are fulfilled:

• It is bounded
• It may share elements with two other slices to its left and right
• It can not grow to the left or to the right without becoming unbounded - meaning: If it is possible, it has to contain so many elements that its maximum-minimum=k

By implication a bounded slice does not qualify as one of the largest possible bounded slices if there is a bounded slice with more elements that entirely encloses this slice

As a goal our algorithm must be capable to start at any element in the array and determine one largest possible bounded slice that contains that element and is the only one to contain it. It is then guaranteed that the next slice constructed from a starting point outside of it will not share the starting element of the previous slice because otherwise it would be one largest possible bounded slice with the previously found slice together (which now, by definition, is impossible). Once that algorithm has been found it can be applied sequentially from the beginning building such largest possible slices until no more elements are left. This would guarantee that each element is traversed two times in the worst case.

Algorithm

Start at the first element and find the largest possible bounded slice that includes said first element. Add the triangular number of its size to the counter. Continue exactly one element after found slice and repeat. Subtract the triangular number of the count of elements shared with the previous slice (found searching backwards), add the triangular number of its total size (found searching forwards and backwards) until the sequence has been traversed. Repeat until no more elements can be found after a found slice, return the result.

Ex. 3: For the input sequence [4 3 1 2 0] with k=2 find the count of bounded slices.

1. Start at the first element, find the largest possible bounded slice: [4 3], count=2, overlap=0, result=3
2. Continue after that slice, find the largest possible bounded slice: [3 1 2], size=3, overlap=1, result=3-1+6=8
3. ... [1 2 0], size=3, overlap=2, result=8-3+6=11
4. result=11

Process behavior

In the worst case the process grows linearly in time and space. As proven above, elements are traversed two times at max. and per search for a largest possible bounded slice some locals need to be stored.

However, the process becomes dramatically faster as the array contains less largest possible bounded slices. For example, the array [4 4 4 4] with k>=0 has only one largest possible bounded slice (the array itself). The array will be traversed once and the triangular number of the count of its elements is returned as the correct result. Notice how this is complementary to solutions of worst case growth O((n * (n+1)) / 2). While they reach their worst case with only one largest possible bounded slice, for this algorithm such input would mean the best case (one visit per element in one pass from start to end).

Implementation

The most difficult part of the implementation is to find a largest bounded slice from one element scanning in two directions. When we search in one direction, we track the minimum and maximum bounds of our search and see how they compare to k. Once an element has been found that stretches the bounds so that maximum-minimum <= k does not hold anymore, we are done in that direction. Then we search into the other direction but use the last valid bounds of the backwards scan as starting bounds.

Ex.4: We start in the array [4 3 1 2 0] at the third element (1) after we have successfully found the largest bounded slice [4 3]. At this point we only know that our starting value 1 is the minimum, the maximum (of the searched largest bounded slice) or between those two. We scan backwards (exclusive) and stop after the second element (as 4 - 1 > k=2). The last valid bounds were 1 and 3. When we now scan forwards, we use the same algorithm but use 1 and 3 as bounds. Notice that even though in this example our starting element is one of the bounds, that is not always the case: Consider the same scenario with a 2 instead of the 3: Neither that 2 or the 1 would be determined to be a bound as we could find a 0 but also a 3 while scanning forwards - only then it could be decided which of 2 or 3 is a lower or upper bound.

To solve that problem here is a special counting algorithm. Don't worry if you don't understand Clojure yet, it does just what it says.

(defn scan-while-around
  "Count numbers in `coll` until a number doesn't pass an (inclusive)
  interval filter where said interval is guaranteed to contain
  `around` and grows with each number to a maximum size of `size`.

  Return count and the lower and upper bounds (inclusive) that were not 
  passed as [count lower upper]."
  ([around size coll]
     (scan-while-around around around size coll))
  ([lower upper size coll]
     (letfn [(step [[count lower upper :as result] elem]
               (let [lower (min lower elem)
                     upper (max upper elem)]
                 (if (<= (- upper lower) size)
                   [(inc count) lower upper]
                   (reduced result))))]
       (reduce step [0 lower upper] coll))))

Using this function we can search backwards, from before the starting element passing it our starting element as around and using k as the size.

Then we start a forward scan from the starting element with the same function, by passing it the previously returned bounds lower and upper.

We add their returned counts to the total count of the found largest possible slide and use the count of the backwards scan as the length of the overlap and subtract its triangular number.

Notice that in any case the forward scan is guaranteed to return a count of at least one. This is important for the algorithm for two reasons:

• We use the resulting count of the forward scan to determine the starting point of the next search (and would loop infinitely with it being 0)
• The algorithm would not be correct as for any starting element the smallest possible largest possible bounded slice always exists as an array of size 1 containing the starting element.

Assuming that triangular is a function returning the triangular number, here is the final algorithm:

(defn bounded-slice-linear
  "Linear implementation"
  [s k]
  (loop [start-index 0
         acc 0]
    (if (< start-index (count s))
      (let [start-elem (nth s start-index)
            [backw lower upper] (scan-while-around start-elem
                                                   k
                                                   (rseq (subvec s 0 
                                                                 start-index)))
            [forw _ _] (scan-while-around lower upper k
                                          (subvec s start-index))]
        (recur (+ start-index forw)
               (-> acc
                   (+ (triangular (+ forw
                                     backw)))
                   (- (triangular backw)))))
      acc)))

(Notice that the creation of subvectors and their reverse sequences happens in constant time and that the resulting vectors share structure with the input vector so no "rest-size" depending allocation is happening (although it may look like it). This is one of the beautiful aspects of Clojure, that you can avoid tons of index-fiddling and usually work with elements directly.)

Here is a triangular implementation for comparison:

(defn bounded-slice-triangular
  "O(n*(n+1)/2) implementation for testing."
  [s k]
  (reduce (fn [c [elem :as elems]]
            (+ c (first (scan-while-around elem k elems))))
          0
          (take-while seq
                      (iterate #(subvec % 1) s))))

Both functions only accept vectors as input.

I have extensively tested their behavior for correctness using various strategies. Please try to prove them wrong anyway. Here is a link to a full file to hack on: https://www.refheap.com/32229

Here is the algorithm implemented in Java (not tested as extensively but seems to work, Java is not my first language. I'd be happy about feedback to learn)

public class BoundedSlices {
    private static int triangular (int i) {
        return ((i * (i+1)) / 2);
    }
    public static int solve (int[] a, int k) {
        int i = 0;
        int result = 0;

        while (i < a.length) {
            int lower = a[i];
            int upper = a[i];
            int countBackw = 0;
            int countForw = 0;

            for (int j = (i-1); j >= 0; --j) {
                if (a[j] < lower) {
                    if (upper - a[j] > k)
                        break;
                    else
                        lower = a[j];
                }
                else if (a[j] > upper) {
                    if (a[j] - lower > k)
                        break;
                    else
                        upper = a[j];
                }
                countBackw++;
            }

            for (int j = i; j <a.length; j++) {
                if (a[j] < lower) {
                    if (upper - a[j] > k)
                        break;
                    else
                        lower = a[j];
                }
                else if (a[j] > upper) {
                    if (a[j] - lower > k)
                        break;
                    else
                        upper = a[j];
                }
                countForw++;
            }
            result -= triangular(countBackw);
            result += triangular(countForw + countBackw);
            i+= countForw;
        }
        return result;
    }
}