Test results - Codility

Tasks Details

medium

1. MaxSquareOnMatrix

Find the side length of the biggest black square in a matrix. In each column, black cells start at the bottom of the matrix and count up.

Task Score

61%

Correctness

100%

Performance

16%

You are given an N × N matrix in which every cell is colored black or white. Columns are numbered from 0 to N-1 (from left to right). This coloring is represented by a non-empty array of integers A. If the K-th number in the array is equal to X then the X lowest cells in the K-th column of the matrix are black. The rest of the cells in the K-th column are white. The task is to calculate the side length of the biggest black square (a square containing only black cells).

Write a function:

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

that, given an array of integers A of length N representing the coloring of the matrix, returns the side length of the biggest black square.

Examples:

1. Given A = [1, 2, 5, 3, 1, 3], the function should return 2. For example, the black square of side 2 contains the two lowest rows of the 1st and 2nd columns (counting from 0).

The picture describes the first example test [1, 2, 5, 3, 1, 3].

2. Given A = [3, 3, 3, 5, 4], the function should return 3. For example, the biggest black square has side 3 and contains the three lowest rows of the last three columns.

The picture describes the second example test [3, 3, 3, 5, 4].

3. Given A = [6, 5, 5, 6, 2, 2], the function should return 4. The biggest black square has side 4 and contains the four lowest rows of the first four columns.

The picture describes the third example test [6, 5, 5, 6, 2, 2].

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..N].

Solution

Programming language used Java 21

Time spent on task 5 minutes

Notes

not defined yet

Code: 10:52:43 UTC, java, autosave

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
    }
}

Code: 10:52:53 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int s=A.length-i+1; // test count

            for(int j=0; j<s; j++){
                int t=0;
                int f=i+1;//square count

                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
        }

        return r;
    }
}

Code: 10:53:08 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int s=A.length-i+1; // test count
            int f=i+1;//square count, no to find

            for(int j=0; j<s; j++){
                int t=0;

                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
        }

        return r;
    }
}

Code: 10:53:18 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i+1; // test count

            for(int j=0; j<s; j++){
                int t=0;

                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
        }

        return r;
    }
}

Code: 10:53:32 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;

                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
        }

        return r;
    }
}

Code: 10:54:04 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
        }

        return r;
    }
}

Code: 10:54:53 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
            if
        }

        return r;
    }
}

Code: 10:55:09 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=t;
                    break;
                }
            }
            
        }

        return r;
    }
}

Code: 10:55:25 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f;
                    break;
                }
            }
            
        }

        return r;
    }
}

Code: 10:55:38 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            
        }

        return r;
    }
}

Code: 10:55:56 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=t) break; //not found
            
        }

        return r;
    }
}

Code: 10:56:01 UTC, java, verify, result: Failed

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=t) break; //not found
        }

        return r;
    }
}

Analysis

Compile error

Solution.java:29: error: cannot find symbol
            if(r!=t) break; //not found
                  ^
  symbol:   variable t
  location: class Solution
1 error

Code: 10:56:27 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=(i+1)) break; //not found
        }

        return r;
    }
}

Code: 10:56:44 UTC, java, autosave

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=f) break; //not found
        }

        return r;
    }
}

Code: 10:57:00 UTC, java, verify, result: Passed

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=f) break; //not found
        }

        return r;
    }
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.008 s

▶

example2
Second example test.

✔

0.008 s

▶

example3
Third example test.

✔

0.008 s

Code: 10:57:10 UTC, java, verify, result: Passed

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=f) break; //not found
        }

        return r;
    }
}

Analysis

expand all Example tests

▶

example1
First example test.

✔

0.008 s

▶

example2
Second example test.

✔

0.008 s

▶

example3
Third example test.

✔

0.012 s

Code: 10:57:16 UTC, java, final, score: 61

show code in pop-up

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

// you can also use imports, for example:
// import java.util.*;

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");

class Solution {
    public int solution(int[] A) {
     int r=0;
        for (int i=0; i<A.length; i++){
            int f=i+1;//square count, no to find
            int s=A.length-i; // test count

            for(int j=0; j<s; j++){
                int t=0;
                for(int k=0; k<f; k++){
                    if(A[j+k]>=f){
                        t++;
                        if(t==f) break;
                    }else{
                        break;
                    }
                }
                if(t==f) {
                    r=f; //square found
                    break;
                }
            }
            if(r!=f) break; //not found
        }

        return r;
    }
}

Analysis summary

The following issues have been detected: timeout errors.

Analysis

Detected time complexity:

O(N ** 2) or O(N ** 2 * log(N))

expand all Example tests

▶

example1
First example test.

✔

0.004 s

▶

example2
Second example test.

✔

0.004 s

▶

example3
Third example test.

✔

0.004 s

expand all Correctness tests

▶

small_corner_cases
Small corner cases. N <= 7.

✔

0.004 s

0.008 s

0.004 s

0.008 s

0.004 s

▶

small_all_distinct_or_all_equal
All numbers are distinct or all are equal. N <= 10.

✔

0.004 s

0.008 s

0.004 s

▶

small_sticking_out_square
Tests with the biggest square surrounded by shorter columns. N <= 10.

✔

0.004 s

0.008 s

0.004 s

▶

small_big_and_small_numbers
Tests with alternating small and big numbers (relatively). N <= 15.

✔

0.004 s

0.008 s

▶

medium_few_monotonic_sequences
Two monotonic sequences or one monotonic and one constant. N <= 75.

✔

0.004 s

0.008 s

▶

medium_local_maximums_and_local_minimums
Tests with local maximums and local minimums. N <= 75.

✔

0.008 s

0.004 s

0.008 s

0.004 s

▶

medium_pyramids
Tests in a form of a three-level pyramid. N <= 75.

✔

0.004 s

0.008 s

expand all Performance tests

▶

big_monotonic_sequences
Various combinations of monotonic and constant sequences. N <= 750.

✔

0.008 s

0.004 s

0.012 s

0.008 s

0.016 s

0.012 s

▶

big_random
Randomly generated tests. N <= 10,000. Score x 2.

✘

TIMEOUT ERROR
running time: 0.360 sec., time limit: 0.128 sec.

0.068 s

0.012 s

0.360 s

TIMEOUT ERROR, running time: 0.360 sec., time limit: 0.128 sec.

0.272 s

TIMEOUT ERROR, running time: 0.272 sec., time limit: 0.128 sec.

▶

very_big_all_types
Mixed tests. Score x 3.

✘

TIMEOUT ERROR
Killed. Hard limit reached: 7.000 sec.

0.152 s

7.000 s