September 9, 2018
Hey Developer,
I am bringing you another high quality Java solution. This time, I am solving the Peaks problem which can be found here.
My solution has a runtime of O(N * log(log(N)) ) and space complexity of O(N), this is considered an efficient solution by Codility. I first saw this solution written in python on stackoverflow by GnomeDePlume, found here, and decided to rewrite it in Java and optimize how fast you can understand what’s going on.
Explanation:
The first thing we are going to do is take advantage of an auxiliary array to store information about our peaks. In this array we will store how many peaks there are to the left of an index. This will help us determine if a block contains a peak in constant time. This is what the array of peaks would look like for our example problem.
peaks = { 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 2, 3 }
index = 0 1 2 3 4 5 6 7 8 9 10 11
There is 1 peak to the left of index 4. There are 2 peaks to the left of index 6, and there are 3 peaks to the left of index 11. Lets continue with the example problem and see how we can use this array.
When our divisor is 3, and the block size is 4, this is what our loop for checking each block for peaks will look like:
If any of the above were equal, then we would know that there is no peak in that block.
The second important point I want to talk about is how the runtime is calculated for this problem. If we imagine that we are to remove this block of code:
if (N % blockSize != 0)
continue;
Then we are performing the for loop below from 3 to N, which is exactly like Exercise 10.3 in this Codility lesson. Then the runtime would be O(N * log(N)). However, our runtime is reduced by Sqrt(N) since we are only looking at divisors of N. With the reduced number of iterations in our for loop, this problem is exactly like the Sieve of Eratosthenes problem in this lesson.
According to Codility the runtime is then O(N * log(log(N)) ).
Below is the code for my Java solution.
class Solution { public int solution(int[] A) { // number of elements in A int N = A.length; // if A is of size less than 3, there is no way to have a peak if (N < 3) return 0; // initialize array of peaks int [] peaks = new int [N]; // compute a list of 'peaks to the left' in O(n) time // starts at 2 because element at i = 0 cannot be a peak for (int i = 2; i < N; i++) { peaks[i] = peaks[i-1]; // check if there was a peak to the left, add it to the count if (A[i-1] > A[i-2] && A[i-1] > A[i] ) { peaks[i] += 1; } } // O(N), however since we are only performing computation for divisors of N, this is reduced to O(Sqrt(N)) // starts at 3 because we cannot have blocks of size 1 or 2 and still have peaks in every block for (int blockSize = 3; blockSize <= N; blockSize++) { // if i is not a divisor of N if (N % blockSize != 0) continue; // flag to indicate that we have a peak in each block boolean valid = true; int blockIndex = blockSize; // O(N/blockSize) // iterate through all the blocks while (blockIndex != N) { // if the block does not contain a peak if (peaks[blockIndex] == peaks[blockIndex-blockSize]) { valid = false; break; } // check next block blockIndex += blockSize; } // this checks if we have 1 big block with at least 1 peak OR it checks the last block if (blockIndex == N && peaks[blockIndex - 1] == peaks[blockIndex-blockSize]) { valid = false; } // return the divisor that produced the block size we just checked // we can return here because our algorithm checks biggest divisor to smallest divisor if (valid) { return N/blockSize; } } return 0; } }