Test results - Codility

Tasks Details

hard

1. FloodedIsland

Count the number of islands on consecutive days.

100%

Not assessed

The city of Codicity is located at the seaside. The city area comprises N plots located along a boulevard on one side of the city. Each plot is flat, but different plots have different heights above the sea level. The relative heights of the consecutive plots are given in the form of a non-empty array A of N integers.

The sea level changes constantly and many plots are sometimes under water. Water levels on consecutive days are given in the form of a non-empty array B of M integers.

A slice of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. An island is a slice of consecutive plots that rise above the water’s surface. The plots on either side of each island are under water. More precisely, if the level of the water is K, then an island is a slice (P, Q) in which the level of each plot A[P], A[P + 1], ..., A[Q] is greater than K. Both of the adjacent plots should also be under water; that is:

P = 0 or A[P − 1] ≤ K

Q = N − 1 or A[Q + 1] ≤ K

The goal is to calculate the number of islands on consecutive days.

For example, given the following arrays A and B:

A[0] = 2 B[0] = 0 A[1] = 1 B[1] = 1 A[2] = 3 B[2] = 2 A[3] = 2 B[3] = 3 A[4] = 3 B[4] = 1

We have the following number of islands on consecutive days:

on the first day there is only 1 island: (0, 4),

on the second day there are 2 islands: (0, 0) and (2, 4),

on the third day there are 2 islands: (2, 2) and (4, 4),

on the fourth day there aren't any islands,

on the fifth day there are 2 islands: (0, 0) and (2, 4).

Write a function:

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

that, given a non-empty array A of N integers and a non-empty array B of M integers, returns a sequence consisting of M integers representing the number of islands on consecutive days.

Result array should be returned as an array of integers.

For example, given:

A[0] = 2 B[0] = 0 A[1] = 1 B[1] = 1 A[2] = 3 B[2] = 2 A[3] = 2 B[3] = 3 A[4] = 3 B[4] = 1

the function should return the array [1, 2, 2, 0, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..30,000];

each element of arrays A and B is an integer within the range [0..100,000].

Solution

Programming language used C#

Total time used 2 minutes

Effective time used 2 minutes

Notes

not defined yet

Task timeline

Code: 23:21:40 UTC, cs, verify, result: Passed

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

using System;
using System.Linq;

public class Solution
{
    private const int MAXIMUM_LENGTH = 30000;

    public int[] solution(int[] A, int[] B)
    {
        if (A == null)
            throw new ArgumentNullException("A");

        if (B == null)
            throw new ArgumentNullException("B");

        if (A.Length < 1 || A.Length > MAXIMUM_LENGTH)
            throw new ArgumentOutOfRangeException("A");

        if (B.Length < 1 || B.Length > MAXIMUM_LENGTH)
            throw new ArgumentOutOfRangeException("B");

        int maximumLevel = new[] { A.Max(), B.Max() }.Max();

        // Calculate islands at each water level
        var islands = new int[maximumLevel + 1];
        int previousHeight = 0;

        foreach (int height in A)
        {
            // Look for peaks
            if (height > previousHeight)
            {
                // We have a new island at all heights from the height to the previous height
                // For now we mark the range and fill it in later
                islands[height - 1]++;

                if (previousHeight > 0)
                    islands[previousHeight - 1]--;
            }

            previousHeight = height;
        }

        // Fill in the ranges
        for (int i = islands.Length - 2; i >= 0; i--)
            islands[i] = islands[i] + islands[i + 1];

        var result = new int[B.Length];

        // Look up the results
        for (int i = 0; i < B.Length; i++)
            result[i] = islands[B[i]];

        return result;
    }
}

Analysis

▶

example
example test

✔

Code: 23:22:25 UTC, cs, verify, result: Passed

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

using System;
using System.Linq;

public class Solution
{
    private const int MAXIMUM_LENGTH = 30000;

    public int[] solution(int[] A, int[] B)
    {
        if (A == null)
            throw new ArgumentNullException("A");

        if (B == null)
            throw new ArgumentNullException("B");

        if (A.Length < 1 || A.Length > MAXIMUM_LENGTH)
            throw new ArgumentOutOfRangeException("A");

        if (B.Length < 1 || B.Length > MAXIMUM_LENGTH)
            throw new ArgumentOutOfRangeException("B");

        int maximumLevel = new[] { A.Max(), B.Max() }.Max();

        // Calculate islands at each water level
        var islands = new int[maximumLevel + 1];
        int previousHeight = 0;

        foreach (int height in A)
        {
            // Look for peaks
            if (height > previousHeight)
            {
                // We have a new island at all heights from the height to the previous height
                // For now we mark the range and fill it in later
                islands[height - 1]++;

                if (previousHeight > 0)
                    islands[previousHeight - 1]--;
            }

            previousHeight = height;
        }

        // Fill in the ranges
        for (int i = islands.Length - 2; i >= 0; i--)
            islands[i] = islands[i] + islands[i + 1];

        var result = new int[B.Length];

        // Look up the results
        for (int i = 0; i < B.Length; i++)
            result[i] = islands[B[i]];

        return result;
    }
}

Analysis

▶

example
example test

✔

Code: 23:22:31 UTC, cs, final, score: 100

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

using System;
using System.Linq;

public class Solution
{
    private const int MAXIMUM_LENGTH = 30000;

    public int[] solution(int[] A, int[] B)
    {
        if (A == null)
            throw new ArgumentNullException("A");

        if (B == null)
            throw new ArgumentNullException("B");

        if (A.Length < 1 || A.Length > MAXIMUM_LENGTH)
            throw new ArgumentOutOfRangeException("A");

        if (B.Length < 1 || B.Length > MAXIMUM_LENGTH)
            throw new ArgumentOutOfRangeException("B");

        int maximumLevel = new[] { A.Max(), B.Max() }.Max();

        // Calculate islands at each water level
        var islands = new int[maximumLevel + 1];
        int previousHeight = 0;

        foreach (int height in A)
        {
            // Look for peaks
            if (height > previousHeight)
            {
                // We have a new island at all heights from the height to the previous height
                // For now we mark the range and fill it in later
                islands[height - 1]++;

                if (previousHeight > 0)
                    islands[previousHeight - 1]--;
            }

            previousHeight = height;
        }

        // Fill in the ranges
        for (int i = islands.Length - 2; i >= 0; i--)
            islands[i] = islands[i] + islands[i + 1];

        var result = new int[B.Length];

        // Look up the results
        for (int i = 0; i < B.Length; i++)
            result[i] = islands[B[i]];

        return result;
    }
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(N + M + max(max(A), max(B)))

▶

example
example test

✔

▶

simple1
first simple test

✔

▶

min_max
min and max values

✔

▶

triple
three elements

✔

▶

extreme_small
only one element

✔

▶

small_random
random small sequences, length = ~500

✔

▶

medium_random
random medium sequences, length = ~10,000

✔

▶

large_random
random lare sequences, length = ~30,000

✔

▶

large_range
[10001, 10002, ..., 40000], length = ~30,000

✔

▶

exteme_large
all the same values

✔