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:
object Solution { def solution(a: Array[Int]): Int }
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 Scala
Time spent on task 1 minutes
Notes
not defined yet
Code: 18:12:09 UTC,
java,
autosave
import scala.collection.JavaConverters._
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
case class SizeInfo(_max: Int, current: Int) {
def inc = this.copy(current = current + 1)
def max = Math.max(_max, current)
def reset = SizeInfo(max, 0)
}
object Solution {
def solution(a: Array[Int]): Int = {
def hasSquare(side: Int): Boolean = {
val size = a.foldLeft(SizeInfo(0, 0))((size, x) =>
if (x >= side) size.inc else size.reset
)
size.max >= side
}
def binary(l: Int, r: Int): Int =
if (l >= r) l
else {
val m = ((l + r) / 2) + ((l + r) % 2)
if (hasSquare(m))
binary(m, r)
else
binary(l, m - 1)
}
binary(0, a.length)
}
}
Code: 18:12:10 UTC,
java,
verify,
result: Failed
import scala.collection.JavaConverters._
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
case class SizeInfo(_max: Int, current: Int) {
def inc = this.copy(current = current + 1)
def max = Math.max(_max, current)
def reset = SizeInfo(max, 0)
}
object Solution {
def solution(a: Array[Int]): Int = {
def hasSquare(side: Int): Boolean = {
val size = a.foldLeft(SizeInfo(0, 0))((size, x) =>
if (x >= side) size.inc else size.reset
)
size.max >= side
}
def binary(l: Int, r: Int): Int =
if (l >= r) l
else {
val m = ((l + r) / 2) + ((l + r) % 2)
if (hasSquare(m))
binary(m, r)
else
binary(l, m - 1)
}
binary(0, a.length)
}
}
Analysis
Compile error
Solution.java:1: warning: '_' used as an identifier
import scala.collection.JavaConverters._
^
(use of '_' as an identifier might not be supported in releases after Java SE 8)
Solution.java:1: error: ';' expected
import scala.collection.JavaConverters._
^
Solution.java:6: error: '{' expected
case class SizeInfo(_max: Int, current: Int) {
^
Solution.java:7: error: ';' expected
def inc = this.copy(current = current + 1)
^
Solution.java:8: error: ';' expected
def max = Math.max(_max, current)
^
Solution.java:9: error: ';' expected
def reset = SizeInfo(max, 0)
^
Solution.java:12: error: class, interface, or enum expected
object Solution {
^
6 errors
1 warning
Code: 18:12:22 UTC,
scala,
autosave
import scala.collection.JavaConverters._
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
case class SizeInfo(_max: Int, current: Int) {
def inc = this.copy(current = current + 1)
def max = Math.max(_max, current)
def reset = SizeInfo(max, 0)
}
object Solution {
def solution(a: Array[Int]): Int = {
def hasSquare(side: Int): Boolean = {
val size = a.foldLeft(SizeInfo(0, 0))((size, x) =>
if (x >= side) size.inc else size.reset
)
size.max >= side
}
def binary(l: Int, r: Int): Int =
if (l >= r) l
else {
val m = ((l + r) / 2) + ((l + r) % 2)
if (hasSquare(m))
binary(m, r)
else
binary(l, m - 1)
}
binary(0, a.length - 1)
}
}
Code: 18:12:24 UTC,
scala,
verify,
result: Passed
import scala.collection.JavaConverters._
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
case class SizeInfo(_max: Int, current: Int) {
def inc = this.copy(current = current + 1)
def max = Math.max(_max, current)
def reset = SizeInfo(max, 0)
}
object Solution {
def solution(a: Array[Int]): Int = {
def hasSquare(side: Int): Boolean = {
val size = a.foldLeft(SizeInfo(0, 0))((size, x) =>
if (x >= side) size.inc else size.reset
)
size.max >= side
}
def binary(l: Int, r: Int): Int =
if (l >= r) l
else {
val m = ((l + r) / 2) + ((l + r) % 2)
if (hasSquare(m))
binary(m, r)
else
binary(l, m - 1)
}
binary(0, a.length)
}
}
Analysis
Code: 18:12:45 UTC,
scala,
verify,
result: Passed
import scala.collection.JavaConverters._
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
case class SizeInfo(_max: Int, current: Int) {
def inc = this.copy(current = current + 1)
def max = Math.max(_max, current)
def reset = SizeInfo(max, 0)
}
object Solution {
def solution(a: Array[Int]): Int = {
def hasSquare(side: Int): Boolean = {
val size = a.foldLeft(SizeInfo(0, 0))((size, x) =>
if (x >= side) size.inc else size.reset
)
size.max >= side
}
def binary(l: Int, r: Int): Int =
if (l >= r) l
else {
val m = ((l + r) / 2) + ((l + r) % 2)
if (hasSquare(m))
binary(m, r)
else
binary(l, m - 1)
}
binary(0, a.length)
}
}
Analysis
Code: 18:13:00 UTC,
scala,
final,
score:
100
import scala.collection.JavaConverters._
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
case class SizeInfo(_max: Int, current: Int) {
def inc = this.copy(current = current + 1)
def max = Math.max(_max, current)
def reset = SizeInfo(max, 0)
}
object Solution {
def solution(a: Array[Int]): Int = {
def hasSquare(side: Int): Boolean = {
val size = a.foldLeft(SizeInfo(0, 0))((size, x) =>
if (x >= side) size.inc else size.reset
)
size.max >= side
}
def binary(l: Int, r: Int): Int =
if (l >= r) l
else {
val m = ((l + r) / 2) + ((l + r) % 2)
if (hasSquare(m))
binary(m, r)
else
binary(l, m - 1)
}
binary(0, a.length)
}
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N * log(N)) or O(N)
expand all
Correctness tests
1.
0.260 s
OK
2.
0.264 s
OK
3.
0.264 s
OK
4.
0.260 s
OK
5.
0.268 s
OK
6.
0.268 s
OK
7.
0.264 s
OK
8.
0.264 s
OK
1.
0.264 s
OK
2.
0.268 s
OK
3.
0.280 s
OK
4.
0.264 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.284 s
OK
2.
0.264 s
OK
3.
0.268 s
OK
4.
0.264 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.268 s
OK
2.
0.264 s
OK
3.
0.264 s
OK
4.
0.272 s
OK
5.
0.264 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.268 s
OK
2.
0.272 s
OK
3.
0.268 s
OK
4.
0.268 s
OK
5.
0.272 s
OK
6.
0.268 s
OK
7.
0.284 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.268 s
OK
2.
0.272 s
OK
3.
0.288 s
OK
4.
0.284 s
OK
5.
0.272 s
OK
6.
0.268 s
OK
7.
0.272 s
OK
1.
0.272 s
OK
2.
0.268 s
OK
expand all
Performance tests
1.
0.324 s
OK
2.
0.328 s
OK
3.
0.324 s
OK
4.
0.328 s
OK
5.
0.324 s
OK
6.
0.344 s
OK
1.
0.480 s
OK
2.
0.420 s
OK
3.
0.464 s
OK
4.
0.468 s
OK
1.
0.704 s
OK
2.
0.744 s
OK
3.
0.808 s
OK
4.
0.904 s
OK
5.
0.768 s
OK
6.
0.820 s
OK
7.
0.760 s
OK
8.
0.760 s
OK
9.
0.808 s
OK
10.
0.740 s
OK
11.
0.784 s
OK
12.
0.760 s
OK
13.
0.768 s
OK