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.

100%

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 1 minutes

Notes

not defined yet

Code: 07:36:55 UTC, java, 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 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

 import java.util.*;

class Solution {
	class Square {
		int height, width;

		Square(int height, int width) {
			this.height = height;
			this.width = width;
		}
	}

	int M = 1;

	void calculateMax(Square a) {
		if (a.height > M && a.width > M)
			M = Math.min(a.height, a.width);
	}

	public int solution(int[] A) {
		Stack<Square> S = new Stack<Square>();

		for (int i = 0; i < A.length; i++) {
			int a = A[i];

			if (S.isEmpty()) {
				S.push(new Square(a, 1));
				continue;
			}
			Square a0 = S.peek();

			if (a > a0.height) {
				S.push(new Square(a, 1));
				continue;
			}
			if (a == a0.height) {
				a0.width++;
				calculateMax(a0);
				continue;
			}
			// a<a0.height
			a0 = S.pop();
			while (!S.isEmpty()) {
				Square a1 = S.peek();
				// a>a1, a replace a0
				if (a > a1.height) {
					a0.height = a;
					a0.width++;
					S.push(a0);
					calculateMax(a0);
					break;
				}
				// a==a1
				if (a == a1.height) {
					a1.width += a0.width + 1;
					calculateMax(a1);
					break;
				}
				// a<a1
				if (a < a1.height) {
					a1.width += a0.width;
					calculateMax(a1);
					a0 = S.pop();
				}
			}
			if (S.isEmpty()) {
				a0.height = a;
				a0.width++;
				S.push(a0);
				calculateMax(a0);
			}
		}

		Square a0 = S.pop();
		while (!S.isEmpty()) {
			S.peek().width += a0.width;
			calculateMax(a0);
			a0 = S.pop();
		}
		return M;
	}
}

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

Code: 07:37:01 UTC, java, verify, result: Passed

 import java.util.*;

class Solution {
	class Square {
		int height, width;

		Square(int height, int width) {
			this.height = height;
			this.width = width;
		}
	}

	int M = 1;

	void calculateMax(Square a) {
		if (a.height > M && a.width > M)
			M = Math.min(a.height, a.width);
	}

	public int solution(int[] A) {
		Stack<Square> S = new Stack<Square>();

		for (int i = 0; i < A.length; i++) {
			int a = A[i];

			if (S.isEmpty()) {
				S.push(new Square(a, 1));
				continue;
			}
			Square a0 = S.peek();

			if (a > a0.height) {
				S.push(new Square(a, 1));
				continue;
			}
			if (a == a0.height) {
				a0.width++;
				calculateMax(a0);
				continue;
			}
			// a<a0.height
			a0 = S.pop();
			while (!S.isEmpty()) {
				Square a1 = S.peek();
				// a>a1, a replace a0
				if (a > a1.height) {
					a0.height = a;
					a0.width++;
					S.push(a0);
					calculateMax(a0);
					break;
				}
				// a==a1
				if (a == a1.height) {
					a1.width += a0.width + 1;
					calculateMax(a1);
					break;
				}
				// a<a1
				if (a < a1.height) {
					a1.width += a0.width;
					calculateMax(a1);
					a0 = S.pop();
				}
			}
			if (S.isEmpty()) {
				a0.height = a;
				a0.width++;
				S.push(a0);
				calculateMax(a0);
			}
		}

		Square a0 = S.pop();
		while (!S.isEmpty()) {
			S.peek().width += a0.width;
			calculateMax(a0);
			a0 = S.pop();
		}
		return M;
	}
}

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

Code: 07:37:07 UTC, java, final, score: 100

 import java.util.*;

class Solution {
	class Square {
		int height, width;

		Square(int height, int width) {
			this.height = height;
			this.width = width;
		}
	}

	int M = 1;

	void calculateMax(Square a) {
		if (a.height > M && a.width > M)
			M = Math.min(a.height, a.width);
	}

	public int solution(int[] A) {
		Stack<Square> S = new Stack<Square>();

		for (int i = 0; i < A.length; i++) {
			int a = A[i];

			if (S.isEmpty()) {
				S.push(new Square(a, 1));
				continue;
			}
			Square a0 = S.peek();

			if (a > a0.height) {
				S.push(new Square(a, 1));
				continue;
			}
			if (a == a0.height) {
				a0.width++;
				calculateMax(a0);
				continue;
			}
			// a<a0.height
			a0 = S.pop();
			while (!S.isEmpty()) {
				Square a1 = S.peek();
				// a>a1, a replace a0
				if (a > a1.height) {
					a0.height = a;
					a0.width++;
					S.push(a0);
					calculateMax(a0);
					break;
				}
				// a==a1
				if (a == a1.height) {
					a1.width += a0.width + 1;
					calculateMax(a1);
					break;
				}
				// a<a1
				if (a < a1.height) {
					a1.width += a0.width;
					calculateMax(a1);
					a0 = S.pop();
				}
			}
			if (S.isEmpty()) {
				a0.height = a;
				a0.width++;
				S.push(a0);
				calculateMax(a0);
			}
		}

		Square a0 = S.pop();
		while (!S.isEmpty()) {
			S.peek().width += a0.width;
			calculateMax(a0);
			a0 = S.pop();
		}
		return M;
	}
}

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

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

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

small_corner_cases
Small corner cases. N <= 7.

✔

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.

✔

▶

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

✔

▶

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

✔

▶

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

✔

0.004 s

0.008 s

0.004 s

▶

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

✔

0.004 s

▶

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

✔

▶

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

✔

0.008 s

0.012 s

0.008 s

▶

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

✔

▶

very_big_all_types
Mixed tests. Score x 3.

✔

0.212 s

0.340 s

0.508 s

0.460 s

0.376 s

0.480 s

0.484 s

0.272 s

0.488 s

10.

0.316 s

11.

0.296 s

12.

0.260 s

13.

0.416 s