Find square area - programming exercise

Given an array with strings of 0s and 1s, write a function that determines the area of the largest square that only contains 1s.

For example, the input may be ["00101", "11101", "11111", "11111", "01001"], which would represent the following matrix:

> 0 0 1 0 1
> 1 1 1 0 1
> 1 1 1 1 1
> 1 1 1 1 1
> 0 1 0 0 1

For this input the biggest square of 1s is 3x3, so your function should return 9.

2x2 square process

 

 

We imagine a 2x2 square, which will be used to iterate through a helper array.

This helper array stores computed values which indicate what is the maximum square lenght that can be formed when a certain line is iterated.

As we iterate forward, we'll need the bottom-right corner to store the max square value. This value can be computed by taking the minimum value of its neighbours and adding itself to the sum.

If this value is bigger than what we have stored as the max square lenght, we update the value.

Before moving to the next interation, we copy the second helper array into the first one.
The second array ($store[1]) will then have its data overwritten by newer computations.

 

Memory usage: array store vs generate

CPU: Intel Core i3-8100B @ 3,6 GHz

 

Usage

• Clone repository

• Open a new terminal window and run the following command:

$ /path/to/your/php index.php DATA_TYPE ROWS COLS

DATA_TYPE: array, generate, file

ROWS: number of array items

COLS: number of characters in each array

• Or open it in a browser (no options available):

$ /path/to/your/php -S localhost:8000

FAQ

• I have a question...

Please contact me at [email protected] for more details.

Authors

• Ciprian Cimpan - Ciprian.pro