title: Counting bounded slice codility
body: <p>I have recently attended a programming test in codility, and the question is to find the Number of bounded slice in an array..</p>
  
  <p>I am just giving you breif explanation of the question.</p>
  
  <p>A Slice of an array said to be a Bounded slice if Max(SliceArray)-Min(SliceArray)&lt;=K.</p>
  
  <p>If Array [3,5,6,7,3] and K=2 provided .. the number of bounded slice is 9,</p>
  
  <p>first slice (0,0) in the array Min(0,0)=3 Max(0,0)=3 Max-Min&lt;=K result 0&lt;=2 so it is bounded slice</p>
  
  <p>second slice (0,1) in the array Min(0,1)=3 Max(0,1)=5 Max-Min&lt;=K result 2&lt;=2 so it is bounded slice</p>
  
  <p>second slice (0,2) in the array Min(0,1)=3 Max(0,2)=6 Max-Min&lt;=K result 3&lt;=2 so it is not bounded slice</p>
  
  <p>in this way you can find that there are nine bounded slice.</p>
  
  <p>(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3), (4, 4).</p>
  
  <p>Following is the solution i have provided</p>
  
  <pre><code>private int FindBoundSlice(int K, int[] A)
  {
      int BoundSlice=0;
      Stack&lt;int&gt; MinStack = new Stack&lt;int&gt;();
      Stack&lt;int&gt; MaxStack = new Stack&lt;int&gt;();
  
  
  
  
      for (int p = 0; p &lt; A.Length; p++)
      {
          MinStack.Push(A[p]);
          MaxStack.Push(A[p]);
          for (int q = p; q &lt; 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&lt;int&gt; Min,Stack&lt;int&gt; Max)
  {
      if (Min.Peek() &gt; P)
      {
          Min.Pop();
          Min.Push(P);
      }
  
      if (Min.Peek() &gt; Q)
      {
          Min.Pop();
          Min.Push(Q);
      }
  
      if (Max.Peek() &lt; P)
      {
          Max.Pop();
          Max.Push(P);
      }
  
      if (Max.Peek() &lt; Q)
      {
          Max.Pop();
          Max.Push(Q);
      }
  
      if (Max.Peek() - Min.Peek() &lt;= K)
          return true;
      else
          return false;
  }
  </code></pre>
  
  <p>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). </p>
  
  <p>Maximum Time Complexity allowed O(N).
  Maximum Space Complexity allowed O(N).</p>