# The biggest square

This question is similar to Biggest Square in a grid.

Challenge

Given a matrix of 1 and 0 in a string format "xxxx,xxxxx,xxxx,xx.." or array format ["xxxx","xxxx","xxxx",...], You will create a function that determines the area of the largest square submatrix that contains all 1.

A square submatrix is one of equal width and height, and your function should return the area of the largest submatrix that contains only 1.

For Example:

Given "10100,10111,11111,10010", this looks like the following matrix:

1 0 1 0 0

1 0 1 1 1

1 1 1 1 1

1 0 0 1 0

You can see the bolded 1 create the largest square submatrix of size 2x2, so your program should return the area which is 4.

Rules

• Submatrix must be one of equal width and height
• Submatrix must contains only values 1
• Your function must return the area of the largest submatrix
• In case no submatrix is found, return 1
• You can calculate the area of the submatrix by counting the number of 1 in the submatrix

Test cases

Input: "10100,10111,11111,10010" Output: 4

Input: "0111,1111,1111,1111" Output: 9

Input "0111,1101,0111" Output: 1

This is , so the shortest answer in bytes win.

• Why string format? Apr 25, 2018 at 18:23
• Can we take the input as a binary (numeric) matrix? Apr 25, 2018 at 18:28
• For [0] still required to output 1?
– l4m2
Apr 25, 2018 at 20:37
• Hang about, why return 1 when no all-1 sub-matrix is found, wouldn't 0 make much more sense? (Otherwise it is simply a special case to handle) Apr 25, 2018 at 21:01
• As it stands I think both answerers would not mind if you changed the specs and I strongly recommend doing so because there's no point for returning 1 and it doesn't make the submissions more interesting. Apr 25, 2018 at 23:15

# Haskell, 113 121 118 117 bytes

x!s=[0..length x-s]
t#d=take t.drop d
f x=last$1:[s*s|s<-min(x!0)$x!!0!0,i<-x!!0!s,j<-x!s,all(>'0')$s#i=<<(s#j)x,s>0]  Try it online! -3 bytes thanks to Laikoni! -1 byte thanks to Lynn! +8 bytes for the ridiculous requirement of returning 1 for no all-1s sub-matrix.. ### Explanation/Ungolfed The following helper function just creates offsets for x allowing to decrement them by s: x!s=[0..length x-s]  x#y will drop y elements from a list and then take x: t#d=take t.drop d  The function f loops over all possible sizes for sub-matrices in order, generates each sub-matrix of the corresponding size, tests whether it contains only '1's and stores the size. Thus the solution will be the last entry in the list: -- v prepend a 1 for no all-1s submatrices f x= last$ 1 : [ s*s
-- all possible sizes are given by the minimum side-length
| s <- min(x!0)$x!!0!0 -- the horizontal offsets are [0..length(x!!0) - s] , i <- x!!0!s -- the vertical offsets are [0..length x - s] , j <- x!s -- test whether all are '1's , all(>'0')$
-- from each row: drop first i elements and take s (concatenates them to a single string)
s#i =<<
-- drop the first j rows and take s from the remaining
(s#j) x
-- exclude size 0...........................................
, s>0
]


# APL (Dyalog Unicode), 3534 32 bytes

{⌈/{×⍨⍵×1∊{∧/∊⍵}⌺⍵ ⍵⊢X}¨⍳⌊/⍴X←⍵}


Try it online!

Adám's SBCS has all of the characters in the code

Explanation coming eventually!

• You had me at 'explanation', lol. Sep 11, 2020 at 13:41

b s@((_:_):_)=maximum$sum[length s^2|s==('1'<$s<$s)]:map b[init s,tail s,init<$>s,tail<$>s] b _=1  Checks if input is a square matrix of just ones with s==('1'<$s<$s), if it is, answer is length^2, else 0. Then recursively chops first/last column/row and takes the maximum value it finds anywhere. Try it online! # K (ngn/k), 33 28 bytes {*/2#+/|/',/'{0&':'0&':x}\x}  Try it online! • I never knew you had a K version! Apr 26, 2018 at 14:31 # J, 33 27 bytes -6 bytes thanks to FrownyFrog! [:>./@,,~@#$$#**/)@,;._3"]  Try it online! ## Explanation: I'll use the first test case in my explanation:  ] a =. 3 51 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1  I generate all the possible square submatrices with size from 1 to the number of rows of the input. ,~@#\ creates a list of pairs for the sizes of the submatrices by stitching ,. togehter the length of the successive prefixes #\ of the input:  ,~@#\ a 1 1 2 2 3 3  Then I use them to cut x u ;. _3 y the input into submatrices. I already have x (the list of sizes); y is the right argument ] (the input).  ((,~@#$$<;._3"$]) a
┌─────┬─────┬─────┬───┬─┐
│1    │0    │1    │0  │0│
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │0    │1    │1  │1│
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │1    │1    │1  │1│
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0  │0 1  │1 0  │0 0│ │
│1 0  │0 1  │1 1  │1 1│ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1 0  │0 1  │1 1  │1 1│ │
│1 1  │1 1  │1 1  │1 1│ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0 1│0 1 0│1 0 0│   │ │
│1 0 1│0 1 1│1 1 1│   │ │
│1 1 1│1 1 1│1 1 1│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘


For each submatrix I check if it consist entirely of 1s: (#**/)@, - flatten the matrix, and mutiply the number of items by their product. If all items are 1s, the result will be their sum, otherwise - 0:

   (#**/)@, 3 3$1 0 0 1 1 1 1 1 1 0 (#**/)@, 2 2$1 1 1 1
4

((,~@#\)(+/**/)@,;._3"$]) a 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 4 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0  Finally I flatten the list of results for each submatrix and find the maximum: >./@,  ([:>./@,,~@#\(+/**/)@,;._3"$]) a
4

• ,~@#\ and "1 2 -> "$ Apr 26, 2018 at 11:56 • @FrownyFrog Thank you! I didn't know about "$ Apr 26, 2018 at 12:02
• # is shorter than adding up the 1s. Apr 26, 2018 at 13:15
• @ FrownyFrog Hmm, it really is. Cool, thanks! Apr 26, 2018 at 13:19

# Ruby-n, 63 bytes

p (1..l=$_=~/,|$/).map{|i|/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max


Try it online!

Ruby version of my Python answer. Golfier as a full program. Alternatively, an anonymous lambda:

->s{(1..l=s=~/,|$/).map{|i|s=~/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max}  Try it online! # Jelly, 18 bytes +2 to handle no-all-1 sublist present output ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1


Try it online! Or see the test-suite

### How?

ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1 - Link: list of lists of 1s and 0s Ẇ - all slices (lists of "rows") call these S = [s1,s2,...]$           - last two links as a monad:
L€            -   length of each (number of rows in each slice) call these X = [x1, x2, ...]
"              -   zip with (i.e. [f(s1,x1),f(s2,x2),...]):
Z                 -       transpose (get the columns of the current slice)
ṡ                -       all slices of length xi (i.e. squares of he slice)
Ẏ          - tighten (to get a list of the square sub-matrices)
Ðf       - filter keep if:
Ȧ         -   any & all (all non-zero when flattened?)
L€     - length of €ach (the side length)
Ṁ    - maximum
²   - square (the maximal area)
»1 - maximum of that and 1 (to coerce a 0 found area to 1)

• Awesome. Can you add some explanation? Apr 25, 2018 at 20:32
• I will, I'm trying to think of shorter first... Apr 25, 2018 at 20:33
• @Mr.Xcoder I have updated to handle the requirement for now Apr 25, 2018 at 21:10

# Retina, 143 bytes

%$,;# +%((\d\d.+;#)#*$1¶$&¶$&#
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2
)r((11)|\d\d)(\d*,;?#*)\G
$#2$3
1,
#
Lv$(#+).*;\1$.($.1*$1
N
-1G
^$1  Try it online! Link includes test cases. Takes input as comma-separated strings. Explanation: %$
,;#


Add a , to terminate the last string, a ; to separate the strings from the #s and a # as a counter.

+%(
)


Repeat the block until no more subsitutions happen (because each string is now only one digit long).

(\d\d.+;#)#*
$1¶$&¶$&#  Triplicate the line, setting the counter to 1 on the first line and incrementing it on the last line. \G\d(\d+,)|\G((;#+¶|,)\d)\d+$1$2  On the first line, delete the first digit of each string, while on the second line, delete all the digits but the first. r((11)|\d\d)(\d*,;?#*)\G$#2$3  On the third line, bitwise and the first two digits together. 1, #  At this point, each line consists of two values, a) a horizontal width counter and b) the bitwise and of that many bits taken from each string. Convert any remaining 1s to #s so that they can be compared against the counter. Lv$(#+).*;\1
$.($.1*$1  Find any runs of bits (vertically) that match the counter (horizontally), corresponding to squares of 1s in the original input, and square the length. N  Sort numerically. -1G  Take the largest. ^$
1


Special-case the zero matrix.

# JavaScript, 92 bytes

a=>(g=w=>a.match(Array(w).fill(1{${w}}).join(..{${W-w}}))?w*w:g(w-1))(W=a.indexOf,)||1


f=
a=>(g=w=>a.match(Array(w).fill(1{${w}}).join(..{${W-w}}))?w*w:g(w-1))(W=a.indexOf,)||1
console.log(f('0111,1111,1111,1111'));
console.log(f('10100,10111,11111,10010'));
console.log(f('0111,1101,0111'));

# APL (Dyalog Classic), 21 20 bytes

×⍨{1∊⍵:1+∇2×/2×⌿⍵⋄0}


Try it online!

• Recursion! Nice! Apr 26, 2018 at 10:51
• @Zacharý Thanks. Actually, instead of recursion I'd prefer something like k's f\x for a monadic f, which is (x; f x; f f x; ...) until convergence, but there's no equivalent in APL (yet). Doing it with ⍣≡ takes too many bytes.
– ngn
Apr 26, 2018 at 12:40

# Python 2, 117 109 bytes

Credit to @etene for pointing out an inefficiency that cost me an additional byte.

lambda s:max(i*i for i in range(len(s))if re.search(("."*(s.find(',')-i+1)).join(["1"*i]*i),s))or 1
import re


Try it online!

Takes input as a comma-separated string. This is a regex-based approach that tries matching the input string against patterns of the form 111.....111.....111 for all possible sizes of the square.

In my calculations, doing this with an anonymous lambda is just a tad shorter than defined function or a full program. The or 1 part in the end is only necessary to handle the strange edge case, where we must output 1 if there are no ones in the input.

# Python 2, 116115117 109 bytes

Credits to @Kirill for helping me golf it even more and for his clever & early solution

Edit: Golfed 1 byte by using a lambda, I didn't know assigning it to a variable didn't count towards the byte count.

Edit 2: Kirill pointed out my solution didn't work for cases where the input only contains 1s, I had to fix it and lost two precious bytes...

Edit 3: more golfing thanks to Kirill

Takes a comma separated string, returns an integer.

lambda g:max(i*i for i in range(len(g))if re.search(("."*(g.find(",")+1-i)).join(["1"*i]*i),g))or 1
import re


Try it online!

I independently found an answer that is close to Kiril's one, i.e regex based, except that I use re.search and a def.

It uses a regex built during each loop to match an incrementally larger square and returns the largest one, or 1.

• Nice, I somehow automatically discarded the if approach as "too long for sure", but then had to make up some other way to make a bool value out of the match. Unfortunately, your solution misses one point - you cannot have just range(l) - it will miss the case when there are no zeroes at all. E.g., take 2nd test case and make it all 1s - it should become 16, not 9. Apr 26, 2018 at 13:44
• Damn, I thought about testing with all zeroes but not with all ones (never mentioned in the challenge...). I'll try to make something up. Apr 26, 2018 at 13:48
• @KirillL. by the way, you're fast ! I was still working on my answer when you posted yours and was a bit bummed (and proud!) when I saw our approaches were similar... the level around here is impressive. Apr 26, 2018 at 13:52
• Golfed a few more bytes by getting rid of duplicated find. Now that our codes are not identical anymore, I suggest we at least fix the obvious mistakes from each other - in your case the extra byte comes from using tuple ("1"*i,) instead of list. Apr 26, 2018 at 14:53
• Thank you, yeah the useless tuple is pretty stupid on my part. And the extra find too, that was clever of you. Apr 26, 2018 at 14:59

# Perl 6, 6160 58 bytes

{(^$_ X.. ^$_).max({[~&](.[|$^r||*])~~/$(1 x$r)/&&+$r})²}


Try it online!

# Python 2, 138 128 bytes

def f(m):j=''.join;L=j(m);k=map(j,zip(*m));return len(L)and max(len(L)*(len(m)**2*'1'==L),f(k[1:]),f(k[:-1]),f(m[1:]),f(m[:-1]))


Try it online!

Saved

• -10 bytes thanks to ovs

## Clojure, 193 bytes

#(apply max(for [f[(fn[a b](take-while seq(iterate a b)))]R(f next %)R(f butlast R)n[(count R)]c(for[i(range(-(count(first R))n -1)):when(apply = 1(for[r R c(subvec r i(+ i n))]c))](* n n))]c))


Wow, things escalated :o

Less golfed:

(def f #(for [rows (->> %    (iterate next)    (take-while seq)) ; row-postfixes
rows (->> rows (iterate butlast) (take-while seq)) ; row-suffixes
n    [(count rows)]
c    (for[i(range(-(count(first rows))n -1)):when(every? pos?(for [row rows col(subvec row i(+ i n))]col))](* n n))] ; rectangular subsections
c))