Codility Lesson 5

5_Fish.java

// simplier solution and neater
class Solution {
    public int solution(int[] A, int[] B) {
        int[] dFish = new int[A.length];
        int di = -1;
        int upstreamCount = 0;

        for (int i=0; i<A.length; i++) {
            if (B[i] == 1) {
                dFish[++di] = A[i];
            } else {
                while (di >= 0) {
                    if (di < 0 || A[i] < dFish[di])
                        break;
                    di--;
                }

                if (di < 0)
                    upstreamCount++;
            }
        }
        return (di+1) + upstreamCount;
    }
}

// longer solution and perhaps more complicated
class Solution {
    int[] fish;
    private int index = -1;
    
    public int solution(int[] A, int[] B) {
        fish = new int[A.length];
        int alivefish = 0;
        boolean isFirstDownstream = false;
        for (int i=0; i<A.length; i++) {
            if (B[i] == 0) {
                if (!isFirstDownstream) {
                    alivefish += 1;
                } else {
                    if (size(fish) == 0) {
                        alivefish += 1;
                    } else {
                        while(size(fish) > 0 && A[peek(fish)] < A[i])
                            pop(fish);
                        if (size(fish) == 0) alivefish += 1;
                    }
                }
            } else {
                isFirstDownstream = true;
                push(fish, i);
            }
        }
        
        alivefish += size(fish);
        return alivefish;
    }
    
    private void push(int[] a, int i) {
        index++;
        a[index] = i;
    }
    
    private void pop(int[] a) {
        if (index >= 0) index--;
    }
    
    private int peek(int[] a) {
        if (index < 0 || index > (a.length-1)) return -1;
        return a[index];
    }
    
    private int size(int[] a) {
        return (index >= 0)?index+1:0;
    }
}

5_StoneWall.java

// StoneWall (Manhattan Skyline problem)
 
class Solution {
    public int solution(int[] H) {
        int blocks = 0;
        int[] stack = new int[H.length];
        int index = -1;
        
        for (int i=0; i<H.length; i++) {
            while (index >= 0 && stack[index] > H[i])
                index--;
            
            if (index == -1 || stack[index] != H[i]) {
                blocks++;
                stack[++index] = H[i];
            }
        }
        
        return blocks;
    }
}