# HackerRank Coding Interview Largest Sub-Grid

--

**Time to complete **— 50minutes

**Question Type =** Medium

**Asked in = Microsoft, Uber, Netflix, Bloomberg, Morgan Stanley, Apple, AMAZON, Google, Target, Walmart, Coupang,**

**Skills:** algorithms, Binary Search, Cumulative Sums, Greedy Algorithms

**Insights — **It should be read very carefully read and you must ask questions in between.

**Question —**

Given a square grid of integers and an integer value, *maxSum*, determine the maximum size of the square sub-grid where for all such sub-grids, the sum of all its elements’ values is less than or equal to the value *maxSum*.

## Example:

*grid =[[2, 2, 2], [3, 3, 3], [4, 4, 4]]*

*maxSum: different scenarios shown below*

*maxSum:* The maximum sum of all square sub-grids of a size must be less than or equal to this integer value

`1. The maximum 1x1 grid has a sum of 4. If maxSum < 4 there is no size square sub-grid that satisfies the condition. The answer is 0`

`2. The maximum 2x2 grid has a sum of 14. If 4 ≤ maxSum < 14, the maximum size of the square sub-grid is 1.`

`3. The maximum 3x3 grid has a sum of 27. If 14 ≤ maxSum < 27, the maximum size of the square sub-grid is 2.`

`4. If maxSum ≥ 27, the entire grid satisfies the condition so the answer is 3.`

# Function Description

Complete the function *largestSubgrid* in the editor below.

largestSubgrid has the following parameter(s):

*int grid[n][n]:*an*n × n*array where*grid[i][j]*is the value of the cell in the*ith*row and*jth*column*int maxSum:*an integer, the maximum acceptable sum of any sub-grid

## Returns:

*int: *an integer that denotes the largest integer k such that there is no *k × k* sub-grid with a total value greater than *maxSum*. If all square sub-grids have value greater than *maxSum*, the function should return 0.

**Constraints**

*1 ≤ n ≤ 1550**1 ≤ maxSum ≤ 10^9**1 ≤ grid[i][j] ≤ 10^7*- the sum of any entire grid is ≤ 10^9

# Input Format for Custom Testing

Input from stdin will be processed as follows and passed to the function*.*

In the first line, there is a single integer *n* representing the number of rows in *grid*.

In the second line, the integer *n* is repeated and represents the number of columns in *grid*.

Each of the next *n* lines contains a row, *grid[i]*, containing *n* space-separated integers, each representing a value of *grid[i][j]*.

In the last line, there is a single integer *maxSum*.

# Sample Case 0

## Sample Input 0

`STDIN Function `

----- --------

3 → grid[n][n] n = 3

3

1 1 1 → grid = [[1,1,1], [1,1,1], [1,1,1]]

1 1 1

1 1 1

4 → maxSum = 4

## Sample Output 0

`2`

## Explanation 0

*n* = 3

*grid = [[1,1,1], [1,1,1], [1,1,1]]*

*maxSum = 4*.

- Square grid of 3 rows and 3 columns :
- Each square sub-grid of size 1 has a sum of values = 1
- Each square sub-grid of size 2 has a sum of values = 4
- The square sub-grid of size 3 has a sum of values = 9

The maximum size of the appropriate sub-grid ( 4 <= 4).

# Sample Case 1

## Sample Input 1

`STDIN Function`

----- --------

4 → grid[n][n] n = 4

4

1 1 1 1 → grid = [[1,1,1,1], [2,2,2,2], [3,3,3,3], [4,4,4,4]]

2 2 2 2

3 3 3 3

4 4 4 4

39 → maxSum = 39

## Sample Output 1

`3`

## Explanation 1

*n = 4*

*grid = [[1,1,1,1], [2,2,2,2], [3,3,3,3], [4,4,4,4]]*

*maxSum = 39*.

- Square grid of 4 rows and 4 columns :
- A square sub-grid of size 1 has a maximum sum of values = 4
- A square sub-grid of size 2 has a maximum sum of values = 14
- A square sub-grid of size 3 has a maximum sum of values = 27
- A square sub-grid of size 4 has a maximum sum of values = 40

The maximum size of appropriate sub-grid is 3, (27 < 39).

# Sample Case 2

## Sample Input 2

`STDIN Function`

----- --------

2 → grid[n][n] n = 2

2

4 5 → grid = [[4,5], [6,7]]

6 7

2 → maxSum = 2

## Sample Output 2

`0`

## Explanation 2

*n = 2*

*grid = [[4,5],[6,7]]*

*maxSum = 2*

- Square grid of 2 rows and 2 columns :
- A square sub-grid of size 1 has a maximum sum of 7.
- A square sub-grid of size 2 has a maximum sum of 22.

Any size sub-grid has a maximum sum > 2.

Hint 1

How would you efficiently find the sum of the elements present in sub-grid? Think about using cumulative sums in two dimensions.

Hint 2

Trying squares of every size is not possible here and would lead to TLE. Can you find the answer greedily?

# Solution

Concepts covered: Binary Search, Cumulative Sums, Greedy Algorithms

# Optimal Solution:

First we will explain how to find the sum of elements inside any sub-grid in constant time and then will use it to find the answer. The idea is to use cumulative sums in 2 dimensions. Let’s suppose cum[i][j] denotes the sum of the grid from (1,1) to (i,j). The sum of the elements of any sub-grid from (i1,j1) to (i2,j2) is cum[i2][j2] — cum[i2][j1] — cum[i1][j2] + cum[i1][j1]. We can start by first assuming that the current largest sub-grid size (size) is n. Now, iterate over each index and find whether the current size of the sub-grid has sum ≤ maxSum. If not, decrease it until it becomes ≤ maxSum. Do this for every index. The final size left is suitable with every index.

`def largestSubgrid(grid, maxSum): `

def get_area(top_i, left_j, size):

return pre_sum[top_i + size][left_j + size] - pre_sum[top_i + size][left_j] - pre_sum[top_i][left_j + size] + pre_sum[top_i][left_j] n = len(grid)

pre_sum = [[0] * (n + 1) for i in range(n + 1)]

for i in range(n):

for j in range(n):

pre_sum[i + 1][j + 1] = grid[i][j] + pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j]

size = n

for i in range(n):

for j in range(n):

if i + size > n or j + size > n:

continue

while size > 0 and get_area(i, j, size) > maxSum:

size -= 1

return size

## Sub-Optimal Solution:

Passes 12 of 14 test cases

We can observe that there is a threshold length of the square sub-grid beyond which there would be at least one sub-grid which has sum > maxSum or it would be a contradiction. Any square sub-grid with length less than this threshold length would definitely have sum ≤ maxSum. Hence we could use a binary search to find the optimal grid size.

`def largestSubgrid(grid, maxSum):`

n = len(grid)

cum = [[0]*(n+1) for _ in range(n+1)]

for i in range(n):

for j in range(n):

cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + grid[i][j]

low, high = 0, n

while low <= high:

mid = (low + high) // 2

maximum_sum = 0

for i in range(mid, n+1):

for j in range(mid, n+1):

maximum_sum = max(maximum_sum, cum[i][j] - cum[i-mid][j] - cum[i][j-mid] + cum[i-mid][j-mid])

if maximum_sum > maxSum:

high = mid - 1

break

if maximum_sum > maxSum:

break

if maximum_sum <= maxSum:

low = mid + 1

return low - 1

Brute Force Approach: Passes 4 of 14 test cases

`def largestSubgrid(grid, maxSum):`

n = len(grid)

low, high = 0, n

for l in range(1, n+1):

maximum_sum = 0

for i in range(0, n-l+1):

for j in range(0, n-l+1):

sum = 0

for ii in range(i,i+l):

for jj in range(j,j+l):

sum += grid[ii][jj]

maximum_sum = max(maximum_sum, sum)

if maximum_sum > maxSum:

return l - 1

return n

# Error Handling:

There are a few test cases where there’s an element greater than maxSum, so the answer may be 0.

# Complexity Analysis

Time Complexity — O(n2).

The preprocessing part, fill the cumulative sum array, takes O(n2) time. Next, for finding the answer we are iterating over each index exactly once for a total of O(n2 indices). Since the value of size can decrease at most n times, the overall time complexity is O(n2).

Space Complexity — O(n2).

The cumulative sum array takes O(n2) space.