Q: Square submatrix with sum equal to k Given a 2D matrix of numbers and a number K, find if there exists a square submatrix with sum equal to K.
I have tried the DP approach with TC O(n^3) and optimised it using binary search to get TC O (n log n).
https://www.geeksforgeeks.org/maximum-size-square-sub-matrix-with-sum-less-than-or-equals-to-k/
Is there a way to do this is O(n*n) ?

A: I saw a similar question on the coding challenges site CSES (If ill find the question link I will attach it here).
I won't give you the answer but a general direction, try to research about prefixes sum array.
here is a link to an explanation and use.
You can use this concept to solve this problem in O(n^2) time and O(n^2) space complexity.
