Tasks Details
medium
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
100%
Correctness
100%
Performance
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].](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/max_square_on_matrix/static/images/auto/a239141bf78ea877bfd84d5b6c5d27eb.png)
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].](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/max_square_on_matrix/static/images/auto/f93c01c901739dfbca08e866359484f2.png)
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].](https://codility-frontend-prod.s3.amazonaws.com/media/task_static/max_square_on_matrix/static/images/auto/149f2bd0051e4c8106205b1ab023e4d5.png)
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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 1 minutes
Notes
not defined yet
Code: 07:34:37 UTC,
java,
autosave
Code: 07:34:42 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
class Solution {
public int solution(int[] A) {
int S[] = new int[A.length];
int Q[] = new int[A.length];
int s = -1;
int m = 1;
for (int i = 0; i < A.length; i++) {
int a = A[i];
if (s == -1) {
s++;
S[s] = a;
Q[s] = 1;
continue;
}
int a0 = S[s];
if (a0 < a) {
s++;
S[s] = a;
Q[s] = 1;
continue;
}
if (a0 == a) {
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
continue;
} else { // drop
if (s == 0) {
S[s] = a; // replace
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
continue;
} else { // a0>a1
while (s > 0) {
int a_1 = S[s - 1];
if (a_1 < a) {
S[s] = a; // replace
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
break;
} else if (a_1 == a) {
Q[s - 1] += Q[s];
Q[s] = 0;
s--;
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
break;
} else { // a_1>a
Q[s - 1] += Q[s];
Q[s] = 0;
s--;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
}
}
if (s == 0) {
if (S[s] > a) {
Q[s]++;
S[s] = a;
} else if (S[s] == a) {
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
} else if (S[s] < a) {
s++;
S[s] = a;
Q[s] = 1;
}
}
}
}
}
while (s > 0) {
Q[s - 1] += Q[s];
s--;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
}
return m;
}
}
Analysis
Code: 07:34:50 UTC,
java,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
class Solution {
public int solution(int[] A) {
int S[] = new int[A.length];
int Q[] = new int[A.length];
int s = -1;
int m = 1;
for (int i = 0; i < A.length; i++) {
int a = A[i];
if (s == -1) {
s++;
S[s] = a;
Q[s] = 1;
continue;
}
int a0 = S[s];
if (a0 < a) {
s++;
S[s] = a;
Q[s] = 1;
continue;
}
if (a0 == a) {
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
continue;
} else { // drop
if (s == 0) {
S[s] = a; // replace
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
continue;
} else { // a0>a1
while (s > 0) {
int a_1 = S[s - 1];
if (a_1 < a) {
S[s] = a; // replace
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
break;
} else if (a_1 == a) {
Q[s - 1] += Q[s];
Q[s] = 0;
s--;
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
break;
} else { // a_1>a
Q[s - 1] += Q[s];
Q[s] = 0;
s--;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
}
}
if (s == 0) {
if (S[s] > a) {
Q[s]++;
S[s] = a;
} else if (S[s] == a) {
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
} else if (S[s] < a) {
s++;
S[s] = a;
Q[s] = 1;
}
}
}
}
}
while (s > 0) {
Q[s - 1] += Q[s];
s--;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
}
return m;
}
}
Analysis
Code: 07:34:55 UTC,
java,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
class Solution {
public int solution(int[] A) {
int S[] = new int[A.length];
int Q[] = new int[A.length];
int s = -1;
int m = 1;
for (int i = 0; i < A.length; i++) {
int a = A[i];
if (s == -1) {
s++;
S[s] = a;
Q[s] = 1;
continue;
}
int a0 = S[s];
if (a0 < a) {
s++;
S[s] = a;
Q[s] = 1;
continue;
}
if (a0 == a) {
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
continue;
} else { // drop
if (s == 0) {
S[s] = a; // replace
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
continue;
} else { // a0>a1
while (s > 0) {
int a_1 = S[s - 1];
if (a_1 < a) {
S[s] = a; // replace
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
break;
} else if (a_1 == a) {
Q[s - 1] += Q[s];
Q[s] = 0;
s--;
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
break;
} else { // a_1>a
Q[s - 1] += Q[s];
Q[s] = 0;
s--;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
}
}
if (s == 0) {
if (S[s] > a) {
Q[s]++;
S[s] = a;
} else if (S[s] == a) {
Q[s]++;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
} else if (S[s] < a) {
s++;
S[s] = a;
Q[s] = 1;
}
}
}
}
}
while (s > 0) {
Q[s - 1] += Q[s];
s--;
if (Q[s] > m && S[s] > m)
m = Q[s] > S[s] ? S[s] : Q[s];
}
return m;
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N * log(N)) or O(N)
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.012 s
OK
6.
0.008 s
OK
7.
0.012 s
OK
8.
0.008 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
small_sticking_out_square
Tests with the biggest square surrounded by shorter columns. N <= 10.
Tests with the biggest square surrounded by shorter columns. N <= 10.
✔
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.012 s
OK
4.
0.004 s
OK
small_big_and_small_numbers
Tests with alternating small and big numbers (relatively). N <= 15.
Tests with alternating small and big numbers (relatively). N <= 15.
✔
OK
1.
0.004 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
medium_few_monotonic_sequences
Two monotonic sequences or one monotonic and one constant. N <= 75.
Two monotonic sequences or one monotonic and one constant. N <= 75.
✔
OK
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
medium_local_maximums_and_local_minimums
Tests with local maximums and local minimums. N <= 75.
Tests with local maximums and local minimums. N <= 75.
✔
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.004 s
OK
4.
0.004 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
1.
0.004 s
OK
2.
0.008 s
OK
expand all
Performance tests
1.
0.004 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
1.
0.032 s
OK
2.
0.016 s
OK
3.
0.032 s
OK
4.
0.032 s
OK
1.
0.160 s
OK
2.
0.276 s
OK
3.
0.256 s
OK
4.
0.232 s
OK
5.
0.256 s
OK
6.
0.256 s
OK
7.
0.256 s
OK
8.
0.208 s
OK
9.
0.260 s
OK
10.
0.252 s
OK
11.
0.212 s
OK
12.
0.204 s
OK
13.
0.240 s
OK