suppose there is an n by n array and where n is taken as the input. The numbers in the array are also given in the input as n rows with each having n elements. Also, n can be between 1 and 450 inclusive and each number in the array (let’s define each as f(i,j) can be between 1 and 200 inclusive. Now we want to find how many rectangular sub grids are there such that the minimum value of f is EXACTLY 88. So the program should find how many of these sub grids are there. The sub-grids could be just one element or the entire array as well.
To start, we know that there are \frac{(n^2(n + 1)^2)}{4} https://i.stack.imgur.com/ZiijV.png4 sub grids in any given array. Figure out a way to write this program using an efficient algorithm. The time complexity should be below 10^7 and the space complexity should be below 10^{10}. So as you can see it has to be an efficient algorithm. (using java)
Some example input for a 3 * 3 array is where n (in this case 3) is the first line and the next n lines constitute n numbers each that make up the array: \begin{array}{ccc} 2 & 36 & 56 \ 5 & 88 & 90 \ 100 & 150 & 200 \end{array} Array image here: https://i.stack.imgur.com/MjiYO.png1
Then the output would be: 4