środa, 3 października 2018

Codility Peaks v2

This is the second solution for Codility task, named Peaks.

The idea is simple:
I collect all the "peaks", and meanwhile I notice prefix sum of peak encounters.
I go through possible sizes of division as long, as I find that one, that has at least one peak in every "block" aka division.
============================================

public int solution(int[] A) {
      int r = 0;              // result
      final int N = A.length; // size of input table
      int[] P = new int[N/2]; // peaks
      int pInd = -1;          // last index of peaks table
      int[] S = new int[N];   // sumprefix of peak count
     
      for(int i = 1; i < N-1; i++){
        if(A[i] > A[i-1] && A[i] > A[i+1]){
          P[++pInd] = i;      // remember peak index
          S[i] = S[i-1]+1;    // remember amount of peaks till this idx
        } else {
          S[i] = S[i-1];
        }
      }
      if(pInd == -1) return 0;   // no peaks
      if(pInd ==  0) return 1;   // one peak means one block
     
      S[N-1] = S[N-2];        // filling the last value of S
     
      int minSize = max(N - P[pInd], P[0]+1); // first and last block has to have a peak
      for(int size = minSize; size <=N; size++){
        boolean noPeak = false;
        if(N % size == 0){
          int blocksAmount = N/size;
          for(int blockNb = 1; blockNb < blocksAmount; blockNb++){
            if( !(S[(blockNb+1)*size -1] > S[blockNb*size -1]) ){
              noPeak = true;
              break;
            }
          } // end of loop for blocks
          if (!noPeak) {
            r = N / size;
            break;
          }
        }
      } // end of loop for sizes
     
      return r;
    }

Brak komentarzy:

Prześlij komentarz