Thread 106320308

i can't even think of an approach???? its over
is this dynamic programming? i fucking hate dynamic programming
previous
>>106308762

>>106320308 (OP)
Are these tests made for people who need to prove how smart they are and sniff their own farts?

>>106320453
f off hater

>>106320308 (OP)
What’s the non brute force approach here? My thought is to slide squares of increasing size across the grid and check for any 0s for an early exit, but I’m sure that would be TLE. It would be O(m*n*min(n,m)) I think, probably much too slow.

>>106320630
Fucking nerd

>>106320723
for every 1 leetcode question i do, a googler does 10
i could never compete
i can NEVER be a real nerd
i just want to leave my shit enterprise java job bros..

When would I need this in the real world?

>>106320308 (OP)
Can’t we find all squares or rectangles of the matrix first and apply some derived math formula to get all side squares count and put them in Hashmap. To find a square and rectangles We can expand outward to group all neighbouring ones? I guess dfs. Maybe tle? Yeah maybe dp is the answer

>>106320680
>>106320746
Notice that for a square nxn matrix the total number of subsquares is the sum of the squares of 1 to n. The general case is even worse. So yeah the problem would need to be reduced somehow first. This problem is probably trivial if you've taken linear algebra recently but it was not recent for me. I have an itch in the back of my head that diagonalizing the matrix should give you information about this but I couldn't extract it.

probably start looking for submatrices of size 1x1 and record them then for every 1x1 check if it's the top-left corner of a 2x2 submatrix and record them. Then for every 2x2 check if it's the top-left corner of a 3x3 and so on until there are none.

>>106320888
this is probably the only solution that doesn't require a ton of extra memory or scales pathologically. it's not very cache friendly at scale but then nothing is with matrices

>>106320888
So what is this, O(n^2)? Who cares, it's plenty fast.
If you want to make it faster you could check for squares made from previously checked squares (doubling n each time) and find the largest size for each square without checking all the intermediates. So worse than O(n*log(n))

>>106321055
I think this is ok memory-wise, 1.333*n^2 bits. Annoying to implement though.

prefix sum matrix mumble mumble
the biggest optimization is when you recognize that the original matrix already contains the information, you just need to count the right way
key insight is that in the first row and column, every cell that contains "1" is already a maximum "so far"; from there you can construct a secondary matrix that references the known surrounding cells to compute whether your current cell is part of a bigger maximum square

in Rust this is just
pub fn count_squares(matrix: Vec>) -> i32 {
let mut table = vec![0; matrix[0].len() + 1];
let (mut prev, mut res) = (0, 0);

for i in 0..matrix.len() {
for j in 0..matrix[0].len() {
table[j + 1] = (matrix[i][j] == 1)
.then(|| replace(&mut prev, table[j + 1]).min(table[j].min(table[j + 1])) + 1)
.unwrap_or(0);

res += table[j + 1];
}
}

res
}

the constraints are so small you can just brute force it pretty easily, that is what i did. O^3 is good enough here. just check each point and count all possible squares where it is the top left corner. i could give pseudo code, but i feel like this is a pretty easy thing to implement.

>>106320308 (OP)
Probably you could do a prefix scan-like (? "prefix-sum"? Not sure proper name) operation. (1, 1, 0, 1, 1, 1, 0) -> (1, 2, 0, 1, 2, 3, 0). So if the question were for # of Nx1's, it'd just be the sum of that. But of course we want to consider columns. Maybe let's try a 3x3 of 1's?
1 2 3
1 2 3
1 2 3

we should get 14 somehow. Working backwards,
1x1:
1 1 1
1 1 1
1 1 1
2x2:
0 0 0
0 1 1
0 1 1
3x3:
0 0 0
0 0 0
0 0 1
merged:
1 1 1
1 2 2
1 2 3

... so maybe you'd do a scan going column-wise, and then min() w/ the prior row-wise scan? O(fucking awesome), if so. But I am a sleepy Chud and my Hitler wants me to go to bed.

>RNS0Y

>>106321674
you beat me to it, this is a variant of the 'largest square submatrix with all 1's problem'

https://www.geeksforgeeks.org/dsa/maximum-size-sub-matrix-with-all-1s-in-a-binary-matrix/

the linear programming solution in this article just needs a little tweaking to get the correct answer

>>106322645
yeah, this is called linear programming.
The best you can do is O(nm) complexity and O(n) space. If you sum up the values you obtained with your method you'll get the answer to this problem.

>page 10, post some shit to keep the thread alive for a while
>>106324489
O(nm) is the "best you can do"? Sorry but if you're coming into contact with all the input data... are you really even trying?

>>106326815
Anon, the input is n*m, so unless you find a way to count all possible squares in less operations than the input size then post it

>>106322645
I'd like to share my recollected thought process for up until I hit "prefix sum".
>0x0 is a square, NxM contains infinite 0x0, obviously the correct answer is infinity
>but how many 0x0's are there? There's only 1. So 1 should be added to all the answers.
>where would you even put a 0x0
>okay so 0x0 is a troll but what about 1x1's do we count those? So we could start by counting all the 1's.
>what's the brute-force answer? for n..., for m..., for n.min(m)... pretty awful...
>what if we worked top-down? Just check if the nxn is all 1's, and if you find a certain square you could "generate" the interior answers
>this seems horrifically complicated, it would be much easier with square input
>it reminds me of certain image processing problems I've done— you make a kernel, calculate the initial values, and then add the new data but then subtract the old
>isn't a prefix scan an important primitive in parallel programming? How's that work again?
Kinda popped out from nowhere.