Markus - 6 months ago 37

Python Question

I have some 2D array of different values for example:

`array = [[1, 1, 2, 5, 6, 1],`

[5, 1, 1, 1, 6, 7],

[10, 12, 1, 1, 11, 11],

[8, 10, 1, 1, 1, 9],

6, 5, 10, 1, 15]]

and, I would like to find coordinates (upper left corner and bottom right corner) of the biggest rectangular array of same values and print them.

In this array are coordinates:

`x=1, y=2`

x=3, y=3

Any ideas?

Answer

You can use this algorithm:

- Start at each x/y coordinate of the array.
- Walk right and to the bottom as long as the value does not change.
- Check at each step whether a new largest field with equal values has been found.

Here is the script. Note that I have added a 1 at the end of the last line of the array so that all entries have the same length. The variables `x`

and `y`

refer to the first and second array index, respectively, which correspond to line and column, respectively (not column and line!).

```
array =[[ 1, 1, 2, 5, 6, 1],
[ 5, 1, 1, 1, 6, 7],
[10, 12, 1, 1, 11, 11],
[ 8, 10, 1, 1, 1, 9],
[ 6, 5, 10, 1, 15, 1]]
xMax = len(array)
yMax = len(array[1])
maxSize = 0
for xUL in range(xMax):
for yUL in range(yMax):
valueRef = array[xUL][yUL]
yBRMax = yMax
for x in range(xUL, xMax):
if (array[x][yUL] != valueRef):
break
for y in range(yUL, yBRMax):
size = (y-yUL+1)*(x-xUL+1)
if (array[x][y] != valueRef):
yBRMax = y
break
else:
size = (y-yUL+1)*(x-xUL+1)
if (size > maxSize):
print("New max size: xUL: %d yUL: %d x: %d y %d size: %d" %(xUL, yUL, x, y, size))
maxSize = size
xMaxUL = xUL
yMaxUL = yUL
xMaxBR = x
yMaxBR = y
```

The following output is produced by running `python3 max.py`

:

```
New max size: xUL: 0 yUL: 0 x: 0 y 0 size: 1
New max size: xUL: 0 yUL: 0 x: 0 y 1 size: 2
New max size: xUL: 1 yUL: 1 x: 1 y 3 size: 3
New max size: xUL: 1 yUL: 2 x: 2 y 3 size: 4
New max size: xUL: 1 yUL: 2 x: 3 y 3 size: 6
```