Test results - Codility

Tasks Details

medium

1. FloodDepth

Find the maximum depth of water in mountains after a huge rainfall.

100%

You are helping a geologist friend investigate an area with mountain lakes. A recent heavy rainfall has flooded these lakes and their water levels have reached the highest possible point. Your friend is interested to know the maximum depth in the deepest part of these lakes.

We simplify the problem in 2-D dimensions. The whole landscape can be divided into small blocks and described by an array A of length N. Each element of A is the altitude of the rock floor of a block (i.e. the height of this block when there is no water at all). After the rainfall, all the low-lying areas (i.e. blocks that have higher blocks on both sides) are holding as much water as possible. You would like to know the maximum depth of water after this entire area is flooded. You can assume that the altitude outside this area is zero and the outside area can accommodate infinite amount of water.

For example, consider array A such that:

A[0] = 1 A[1] = 3 A[2] = 2 A[3] = 1 A[4] = 2 A[5] = 1 A[6] = 5 A[7] = 3 A[8] = 3 A[9] = 4 A[10] = 2

The following picture illustrates the landscape after it has flooded:

The gray area is the rock floor described by the array A above and the blue area with dashed lines represents the water filling the low-lying areas with maximum possible volume. Thus, blocks 3 and 5 have a water depth of 2 while blocks 2, 4, 7 and 8 have a water depth of 1. Therefore, the maximum water depth of this area is 2.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A consisting of N integers, returns the maximum depth of water.

Given array A shown above, the function should return 2, as explained above.

For the following array:

A[0] = 5 A[1] = 8

the function should return 0, because this landscape cannot hold any water.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..100,000];

each element of array A is an integer within the range [1..100,000,000].

Solution

Programming language used Java 8

Time spent on task 1 minutes

Notes

not defined yet

Code: 00:07:57 UTC, java, autosave

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181

import java.util.*;

class Main {

    public static void main(String[] args) {
        /*
        test(2, 1, 3, 2, 1, 2, 1, 5 ,3, 3, 4, 2);
        test(1, 3, 1, 2);
        test(0, 1, 3, 2);
        test(1, 2, 1, 3);
        test(6, 3, 1, 10, 4, 20);
        test(5, 1, 9, 8, 7, 4, 8, 7, 10, 31, 2);
        test(1, 2, 2, 1, 3);
        test(1, 4, 1, 2, 2, 2, 1);
        test(80, 100, 150, 90, 95, 80, 85, 70, 75, 87, 77, 170);
        */

        test(0, 32962652, 2217965, 72313941, 14691530, 39142192, 97354201, 96142270, 91954953, 35446581, 77520091, 13937685, 41554817, 32587248, 4646743, 53623030, 86101472, 34269214, 66708533, 43638041, 48567921, 48567921);

        //randomTest(1, 100000000, 20);
    }

    private static void test(int expected, int... args) {
        int result = new Solution().solution(args);
        if (expected != result) {
            System.out.println("FAIL");
            System.out.print(result);

            for (int arg : args) {
                System.out.print(", " + arg);
            }

            System.out.println();
        }
    }

    private static void randomTest(int min, int max, int size) {
        Random random = new Random();
        int[] A = new int[size];

        for (int i=0; i<size; i++) {
            A[i] = random.nextInt(max - min + 1) + min;
            System.out.print(A[i] + ", ");
        }

        System.out.println(A[size - 1]);

        int result = new Solution().solution(A);

        System.out.println(result);
    }
}

class Solution {

    private int max;
    private Integer incline;
    private Integer prev;
    private Stack<Pit> pitStack = new Stack<>();
    
    public int solution(int[] A) {
        prev = A[0];
        pitStack.add(new Pit(prev));

        for (int i=1; i<A.length; i++) {
            int a = A[i];
            int delta = a - prev;
            Pit last = pitStack.peek();

            if (changedToDecline(delta)) {
                last.right = prev;
                merge(last);
                checkDepth(last);
                removeInvalid();
                pitStack.add(new Pit(prev));
                incline = -1;

            } else if (changedToIncline(delta)){
                last.setBottom(prev);
                incline = 1;

                if (i == A.length - 1) {
                    checkLastPit(last, a);
                }

            } else if (i == A.length - 1) {
                checkLastPit(last, a);
            }

            prev = a;
        }

        return max;
    }

    private boolean changedToDecline(int delta) {
        return (incline == null && delta < 0) || (incline != null && incline != -1 && delta < 0);
    }

    private boolean changedToIncline(int delta) {
        return (incline == null && delta > 0) || (incline != null && incline != 1 && delta > 0);
    }

    private void merge(Pit pit) {
        if (pit.isMergeable()) {
            checkDepth(pit);
            Pit mergeablePit = pitStack.pop();
            while (!pitStack.isEmpty()) {
                Pit pop = pitStack.pop();
                mergeablePit.left = pop.left;
                mergeablePit.setBottom(pop.bottom);
                checkDepth(mergeablePit);

                if (mergeablePit.left > mergeablePit.right) {
                    break;
                }
            }

            pitStack.add(mergeablePit);
        } 
    }

    private void removeInvalid() {
        if (pitStack.peek().isInvalid()) {
            pitStack.pop();
        }
    }

    private void checkDepth(Pit pit) {
        max = Math.max(max, pit.getDepth());
    }

    private void checkLastPit(Pit pit, int a) {
        pit.right = a;
        merge(pit);
        checkDepth(pit);
    }

    private boolean isMergeable(Pit pit) {
        return pit.right > pit.left;
    }
}

class Pit {

    public Integer left;
    public Integer right;
    public Integer bottom;

    public Pit(int left) {
        this.left = left;
    }

    public int getDepth() {
        if (isInvalid()) {
            return 0;
        } else {
            return Math.min(left, right) - bottom;
        }
    }

    public void setBottom(int bottom) {
        if (this.bottom == null) {
            this.bottom = bottom;
        } else {
            this.bottom = Math.min(this.bottom, bottom);
        }
    }

    public boolean isInvalid() {
        return (left == null || right == null || bottom == null) || (left == bottom || right == bottom);
    }

    public boolean isMergeable() {
        return right > left;
    }

    public String toString() {
        return String.format("%d %d %d", left, right, bottom);
    }
}

Code: 00:08:01 UTC, java, verify, result: Passed

import java.util.*;

class Solution {

    private int max;
    private Integer incline;
    private Integer prev;
    private Stack<Pit> pitStack = new Stack<>();
    
    public int solution(int[] A) {
        prev = A[0];
        pitStack.add(new Pit(prev));

        for (int i=1; i<A.length; i++) {
            int a = A[i];
            int delta = a - prev;
            Pit last = pitStack.peek();

            if (changedToDecline(delta)) {
                last.right = prev;
                merge(last);
                checkDepth(last);
                removeInvalid();
                pitStack.add(new Pit(prev));
                incline = -1;

            } else if (changedToIncline(delta)){
                last.setBottom(prev);
                incline = 1;

                if (i == A.length - 1) {
                    checkLastPit(last, a);
                }

            } else if (i == A.length - 1) {
                checkLastPit(last, a);
            }

            prev = a;
        }

        return max;
    }

    private boolean changedToDecline(int delta) {
        return (incline == null && delta < 0) || (incline != null && incline != -1 && delta < 0);
    }

    private boolean changedToIncline(int delta) {
        return (incline == null && delta > 0) || (incline != null && incline != 1 && delta > 0);
    }

    private void merge(Pit pit) {
        if (pit.isMergeable()) {
            checkDepth(pit);
            Pit mergeablePit = pitStack.pop();
            while (!pitStack.isEmpty()) {
                Pit pop = pitStack.pop();
                mergeablePit.left = pop.left;
                mergeablePit.setBottom(pop.bottom);
                checkDepth(mergeablePit);

                if (mergeablePit.left > mergeablePit.right) {
                    break;
                }
            }

            pitStack.add(mergeablePit);
        } 
    }

    private void removeInvalid() {
        if (pitStack.peek().isInvalid()) {
            pitStack.pop();
        }
    }

    private void checkDepth(Pit pit) {
        max = Math.max(max, pit.getDepth());
    }

    private void checkLastPit(Pit pit, int a) {
        pit.right = a;
        merge(pit);
        checkDepth(pit);
    }

    private boolean isMergeable(Pit pit) {
        return pit.right > pit.left;
    }
}

class Pit {

    public Integer left;
    public Integer right;
    public Integer bottom;

    public Pit(int left) {
        this.left = left;
    }

    public int getDepth() {
        if (isInvalid()) {
            return 0;
        } else {
            return Math.min(left, right) - bottom;
        }
    }

    public void setBottom(int bottom) {
        if (this.bottom == null) {
            this.bottom = bottom;
        } else {
            this.bottom = Math.min(this.bottom, bottom);
        }
    }

    public boolean isInvalid() {
        return (left == null || right == null || bottom == null) || (left == bottom || right == bottom);
    }

    public boolean isMergeable() {
        return right > left;
    }

    public String toString() {
        return String.format("%d %d %d", left, right, bottom);
    }
}

Code: 00:08:06 UTC, java, final, score: 100

import java.util.*;

class Solution {

    private int max;
    private Integer incline;
    private Integer prev;
    private Stack<Pit> pitStack = new Stack<>();
    
    public int solution(int[] A) {
        prev = A[0];
        pitStack.add(new Pit(prev));

        for (int i=1; i<A.length; i++) {
            int a = A[i];
            int delta = a - prev;
            Pit last = pitStack.peek();

            if (changedToDecline(delta)) {
                last.right = prev;
                merge(last);
                checkDepth(last);
                removeInvalid();
                pitStack.add(new Pit(prev));
                incline = -1;

            } else if (changedToIncline(delta)){
                last.setBottom(prev);
                incline = 1;

                if (i == A.length - 1) {
                    checkLastPit(last, a);
                }

            } else if (i == A.length - 1) {
                checkLastPit(last, a);
            }

            prev = a;
        }

        return max;
    }

    private boolean changedToDecline(int delta) {
        return (incline == null && delta < 0) || (incline != null && incline != -1 && delta < 0);
    }

    private boolean changedToIncline(int delta) {
        return (incline == null && delta > 0) || (incline != null && incline != 1 && delta > 0);
    }

    private void merge(Pit pit) {
        if (pit.isMergeable()) {
            checkDepth(pit);
            Pit mergeablePit = pitStack.pop();
            while (!pitStack.isEmpty()) {
                Pit pop = pitStack.pop();
                mergeablePit.left = pop.left;
                mergeablePit.setBottom(pop.bottom);
                checkDepth(mergeablePit);

                if (mergeablePit.left > mergeablePit.right) {
                    break;
                }
            }

            pitStack.add(mergeablePit);
        } 
    }

    private void removeInvalid() {
        if (pitStack.peek().isInvalid()) {
            pitStack.pop();
        }
    }

    private void checkDepth(Pit pit) {
        max = Math.max(max, pit.getDepth());
    }

    private void checkLastPit(Pit pit, int a) {
        pit.right = a;
        merge(pit);
        checkDepth(pit);
    }

    private boolean isMergeable(Pit pit) {
        return pit.right > pit.left;
    }
}

class Pit {

    public Integer left;
    public Integer right;
    public Integer bottom;

    public Pit(int left) {
        this.left = left;
    }

    public int getDepth() {
        if (isInvalid()) {
            return 0;
        } else {
            return Math.min(left, right) - bottom;
        }
    }

    public void setBottom(int bottom) {
        if (this.bottom == null) {
            this.bottom = bottom;
        } else {
            this.bottom = Math.min(this.bottom, bottom);
        }
    }

    public boolean isInvalid() {
        return (left == null || right == null || bottom == null) || (left == bottom || right == bottom);
    }

    public boolean isMergeable() {
        return right > left;
    }

    public String toString() {
        return String.format("%d %d %d", left, right, bottom);
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N)

▶

example1
first example test

✔

▶

example2
second example test

✔

▶

boundary
max-min values and some random tests, N <= 15

✔

0.008 s

0.004 s

0.008 s

0.004 s

0.008 s

0.004 s

0.008 s

▶

triple_permutation
all permutations of three elements [1, 2, 3]

✔

0.008 s

0.004 s

0.008 s

0.004 s

▶

small_functional
small functional tests, N <= 15

✔

0.008 s

0.004 s

0.008 s

0.004 s

0.008 s

▶

small_random
small random tests, N <= 100

✔

▶

multiple_valleys
many small valleys, N <= 100

✔

▶

small_valley
one small valley, N <= 100

✔

▶

medium_tests
medium tests, N <= 600

✔

▶

big_random
random arrays, N ~= 100,000

✔

▶

increasing_decreasing
randomized values which grow when distance from the center decreases, N ~= 100,000

✔

▶

many_multiple_valleys
many small valleys, N ~= 100,000

✔

▶

big_valley
one big valley, N ~= 100,000

✔

▶

big_jagged
one big valley with jagged slopes, N ~= 100,000

✔