Codility Peaks

Posted on January 2, 2014

Last updated on January 3, 2014

Solution to Codility Peaks problem.

First, we need to find all the peaks. Simply iterate through all elements and aggregate all the peaks into \(P\).

Then, we can iterate through the various possible group sizes \(g \in [1,N]\). We need the least \(g\) such that \(g | N\) (then \(\frac{N}{g}\) is maximized) and so that every group of size \(g\) has at least one peak. This can be done by simply iterating through all the peaks \(p \in P\) and checking if every has peak. The 100/100 Java code:

import java.util.*;
class Solution {
  public int solution(int[] A) {
    int N = A.length;

    // Find all the peaks
    ArrayList<Integer> peaks = new ArrayList<Integer>();
    for(int i = 1; i < N-1; i++){
      if(A[i] > A[i-1] && A[i] > A[i+1]) peaks.add(i);
    }

    for(int size = 1; size <= N; size++){
      if(N % size != 0) continue; // skip if non-divisible
      int find = 0;
      int groups = N/size;
      boolean ok = true;
      // Find whether every group has a peak
      for(int peakIdx : peaks){
        if(peakIdx/size > find){
          ok = false;
          break;
        }
        if(peakIdx/size == find) find++;
      }
      if(find != groups) ok = false;
      if(ok) return groups;
    }
    return 0;
  }
}
Codility Peak
Markdown SHA1: 940023d5b562b730ffac1a8ed4b497ddb04e5663