title: Min Average Two Slice Codility
body: <p>A non-empty zero-indexed array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P &lt; Q &lt; N, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice (P, Q) is the sum of A[P] + A[P + 1] + ... + A[Q] divided by the length of the slice. To be precise, the average equals (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).<br/>
  For example, array A such that:</p>
  
  <pre><code>A[0] = 4
  A[1] = 2
  A[2] = 2
  A[3] = 5
  A[4] = 1
  A[5] = 5
  A[6] = 8
  </code></pre>
  
  <p>contains the following example slices:<br/></p>
  
  <ul>
  <li>slice (1, 2), whose average is (2 + 2) / 2 = 2;</li>
  <li>slice (3, 4), whose average is (5 + 1) / 2 = 3;</li>
  <li>slice (1, 4), whose average is (2 + 2 + 5 + 1) / 4 = 2.5.</li>
  </ul>
  
  <p>The goal is to find the starting position of a slice whose average is minimal.</p>
  
  <p>Write a function:</p>
  
  <pre><code>class Solution { public int solution(int[] A); }
  </code></pre>
  
  <p>that, given a non-empty zero-indexed array A consisting of N integers, returns the starting position of the slice with the minimal average. If there is more than one slice with a minimal average, you should return the smallest starting position of such a slice.<br/>
  For example, given array A such that:</p>
  
  <pre><code>A[0] = 4
  A[1] = 2
  A[2] = 2
  A[3] = 5
  A[4] = 1
  A[5] = 5
  A[6] = 8
  </code></pre>
  
  <p>the function should return 1, as explained above.</p>
  
  <p>Assume that:</p>
  
  <ul>
  <li>N is an integer within the range [2..100,000];</li>
  <li>each element of array A is an integer within the range [−10,000..10,000].</li>
  </ul>
  
  <p>Complexity:</p>
  
  <ul>
  <li>expected worst-case time complexity is O(N);</li>
  <li>expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).</li>
  </ul>
  
  <p>Elements of input arrays can be modified.</p>
  
  <hr>
  
  <p>This is my best solution, but obviously not optimal in terms of time complexity. <br/>
  Any ideas?</p>
  
  <pre><code>public int solution(int[] A) {
      int result = 0;
      int N = A.length;
      int [] prefix = new int [N+1];
      for (int i = 1; i &lt; prefix.length; i++) {
          prefix[i] = prefix[i-1] + A[i-1];
      }
      double avg = Double.MAX_VALUE;
      for (int i = 1; i &lt; N; i++) {
          for (int j = i+1; j &lt;=N; j++) {
              double temp = (double)(prefix[j]-prefix[i-1]) /(double)(j-i+1);
              if (temp &lt; avg) {
                  avg = temp;
                  result = i-1;
              }
          }
      }
      return result;
  }
  </code></pre>
  
  <p><a href="https://codility.com/demo/results/demo65RNV5-T36/" rel="noreferrer">https://codility.com/demo/results/demo65RNV5-T36/</a></p>