Codility - Peaks

This is the first solution of the peaks task form Codility platform:

Idea is to determine min and max size of possible block, then go through peaks and increase minimum size of the block if some peak is "out of the division". Additionally there is a list of forbidden value of sizes to avoid situation that increasing minimum size on one peak would negatively interfere with any of previous peaks.

It's very long in implementation, but intuitive, very fast && maybe original. Faster than widely published version with checking all the peaks in a loop of consecutive size of the block, if one don't use prefix sum for counting blocks. Of course 100% in Codility test.

Here is a code:


public int solution(int[] A) {
    int r;
    final int N = A.length;
    int[] B = new int[N]; // space between peaks +1
    int[] P = new int[N]; // peaks idxs
    int iP;               // max index of values in table P
    int max_bl, min_bl;
    List<Integer> list_impossible_min = new ArrayList<>();
    int[] min_max_ip = new int[3]; // temporary storage for variables

    // detemine B, P, iP, max_bl, min_bl
    getMinMaxBl(A, B, P, min_max_ip);
    min_bl = min_max_ip[0];
    max_bl = min_max_ip[1];
    iP     = min_max_ip[2];
   
    if(iP == -1){       // no peaks
      return 0;
    } else if(iP == 0){ // one peak
      return 1;
    }

    // applaying last block size
    int last_bl = N-1 -P[iP] + 1;
   
    if( last_bl > min_bl){
      min_bl = last_bl;}
    if(last_bl > B[P[iP]]){
      B[P[iP]] = last_bl;}

    // applying condition of possible divide
    while ((N % min_bl) != 0) {
      min_bl++;}
    while ((N % max_bl) != 0) {
      max_bl++;}


    for (int i = 1; i <= iP; i++) {
      int idx_peak = P[i];
      if (B[idx_peak] > min_bl) {   
        int pp = P[i-1]; // previous peak
       
        int a = (idx_peak + 1) / min_bl;
        int b = a * min_bl;
        if (b != (idx_peak + 1)) { // border of division is in between peaks
          if (b - pp > min_bl) {   // border of division is too far from pp

            // seraching for first possible new min_bl
            for (int j = min_bl + 1; j <= max_bl; j++) {
              a = (idx_peak + 1) / j;
              b = a * j;

              if (list_impossible_min.isEmpty() || !list_impossible_min.contains(j)) {
                if (N % j == 0 && (b - pp <= j)) {
                  min_bl = j;
                  break;
                }
              }
            }
          }
        }
        for (int j = min_bl + 1; j <= B[idx_peak]; j++) {
          a = (idx_peak + 1) / j;
          b = a * j;

          if (N % j != 0 || ((pp + j < idx_peak) && ( b*a-pp > j))) {
            if (pp + j < idx_peak) {
              if (list_impossible_min.isEmpty() || !list_impossible_min.contains(j)) {
                list_impossible_min.add(j);
              }
            }
          }
        }
      }
    }
    r = N / min_bl;

    return r;
  }

  private void getMinMaxBl(int[] A, int[] B, int[] P, int[] min_max_ip) {
    int N = A.length;
    int f_peak = -1, l_peak = -1;
    int iP = -1, min_bl = 0, max_bl = 0;

    // detemine max_bl, min_bl
    // first min_bl & max_bl
    for (int i = 1; i < N - 1; i++) {
      if (peak(A, i)) {
        max_bl = i+1;
        min_bl = i+1;
        f_peak = i;
        l_peak = i;
        B[i]   = i+1;
        P[++iP] = i;
        break;
      }
    }
    if(f_peak > 0){
      for(int i = f_peak+2; i < N-1; i++){
        int t_max_block;
        int t_min_block;
        if (peak(A, i)) {
          t_max_block = i - l_peak; // covers cells max empty space + 1 for peak
          t_min_block = (t_max_block + 1)/2; // covers two peaks + space between
          if((t_max_block+1)%2 != 0){
            t_min_block++;
          }
          min_bl = max(min_bl, t_min_block);
          max_bl = max(max_bl, t_max_block);
          B[i]   = t_max_block;
          l_peak = i;
          P[++iP] = i;
        }
      }
    }
    min_max_ip[0] = min_bl;
    min_max_ip[1] = max_bl;
    min_max_ip[2] = iP;
  }

  boolean peak(int[] A, int i) {
    return A[i] > A[i - 1] && A[i] > A[i + 1];
  }