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
53%
Correctness
100%
Performance
0%
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:
def solution(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 Python
Time spent on task 17 minutes
Notes
not defined yet
Code: 18:01:35 UTC,
java,
autosave
Code: 18:17:25 UTC,
py,
autosave
def solution(A):
max_length = max(max(A),len(A))
matrix = []
for i in A:
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
answer = [0 for i in range(len(matrix))]
max_square = 0
for j in range(len(matrix[0])):
for i in range(len(matrix)):
if int(matrix[i][j]):
answer[i] += int(matrix[i][j])
else:
answer[i] = 0
if max(answer) >= max_square+1:
max_square = max_square_val(answer,max_square)
return(max_square)
def max_square_val(answer,max_square):
max_square+=1
if max_square > len(answer):
return max_square-1
count = 0
for val in answer:
if val >= max_square:
count+=1
else:
count = 0
if count == max_square:
return(max_square)
return max_square-1
Code: 18:17:27 UTC,
py,
verify,
result: Passed
def solution(A):
max_length = max(max(A),len(A))
matrix = []
for i in A:
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
answer = [0 for i in range(len(matrix))]
max_square = 0
for j in range(len(matrix[0])):
for i in range(len(matrix)):
if int(matrix[i][j]):
answer[i] += int(matrix[i][j])
else:
answer[i] = 0
if max(answer) >= max_square+1:
max_square = max_square_val(answer,max_square)
return(max_square)
def max_square_val(answer,max_square):
max_square+=1
if max_square > len(answer):
return max_square-1
count = 0
for val in answer:
if val >= max_square:
count+=1
else:
count = 0
if count == max_square:
return(max_square)
return max_square-1
Analysis
Code: 18:17:45 UTC,
py,
verify,
result: Passed
def solution(A):
max_length = max(max(A),len(A))
matrix = []
for i in A:
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
answer = [0 for i in range(len(matrix))]
max_square = 0
for j in range(len(matrix[0])):
for i in range(len(matrix)):
if int(matrix[i][j]):
answer[i] += int(matrix[i][j])
else:
answer[i] = 0
if max(answer) >= max_square+1:
max_square = max_square_val(answer,max_square)
return(max_square)
def max_square_val(answer,max_square):
max_square+=1
if max_square > len(answer):
return max_square-1
count = 0
for val in answer:
if val >= max_square:
count+=1
else:
count = 0
if count == max_square:
return(max_square)
return max_square-1
Analysis
Code: 18:17:49 UTC,
py,
final,
score:
53
def solution(A):
max_length = max(max(A),len(A))
matrix = []
for i in A:
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
answer = [0 for i in range(len(matrix))]
max_square = 0
for j in range(len(matrix[0])):
for i in range(len(matrix)):
if int(matrix[i][j]):
answer[i] += int(matrix[i][j])
else:
answer[i] = 0
if max(answer) >= max_square+1:
max_square = max_square_val(answer,max_square)
return(max_square)
def max_square_val(answer,max_square):
max_square+=1
if max_square > len(answer):
return max_square-1
count = 0
for val in answer:
if val >= max_square:
count+=1
else:
count = 0
if count == max_square:
return(max_square)
return max_square-1
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(N ** 3) or O(N ** 5) or O(N ** 2 * log(N)) or O(N ** 4) or O(N ** 2)
expand all
Correctness tests
1.
0.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
5.
0.040 s
OK
6.
0.040 s
OK
7.
0.040 s
OK
8.
0.040 s
OK
1.
0.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
4.
0.040 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.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
4.
0.040 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.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
5.
0.040 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.044 s
OK
2.
0.044 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
5.
0.040 s
OK
6.
0.040 s
OK
7.
0.040 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.040 s
OK
2.
0.040 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
5.
0.040 s
OK
6.
0.040 s
OK
7.
0.044 s
OK
1.
0.044 s
OK
2.
0.044 s
OK
expand all
Performance tests
big_monotonic_sequences
Various combinations of monotonic and constant sequences. N <= 750.
Various combinations of monotonic and constant sequences. N <= 750.
✘
TIMEOUT ERROR
running time: 0.284 sec., time limit: 0.176 sec.
running time: 0.284 sec., time limit: 0.176 sec.
1.
0.284 s
TIMEOUT ERROR,
running time: 0.284 sec., time limit: 0.176 sec.
2.
0.308 s
TIMEOUT ERROR,
running time: 0.308 sec., time limit: 0.160 sec.
3.
0.384 s
TIMEOUT ERROR,
running time: 0.384 sec., time limit: 0.160 sec.
4.
0.384 s
TIMEOUT ERROR,
running time: 0.384 sec., time limit: 0.160 sec.
5.
0.332 s
TIMEOUT ERROR,
running time: 0.332 sec., time limit: 0.160 sec.
6.
0.332 s
TIMEOUT ERROR,
running time: 0.332 sec., time limit: 0.160 sec.
big_random
Randomly generated tests. N <= 10,000. Score x 2.
Randomly generated tests. N <= 10,000. Score x 2.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
3.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
4.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
1.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
2.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
3.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
4.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
5.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
6.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
7.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
8.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
9.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
10.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
11.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
12.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError
13.
7.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 7.000 sec.
stderr:
Traceback (most recent call last):
File "exec.py", line 129, in <module>
main()
File "exec.py", line 91, in main
result = solution( A )
File "/tmp/solution.py", line 6, in solution
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
File "/tmp/solution.py", line 6, in <listcomp>
matrix.append([ 0 if j>=i else 1 for j in range(max_length)])
MemoryError