# 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

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 11 1 14     →   maxSum = 4`

`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 23 3 3 34 4 4 439      →   maxSum = 39`

`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 = 22   4 5   →   grid = [[4,5], [6,7]] 6 72     →   maxSum = 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 = [ * (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 = [*(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.

--

--

I write about Technical stuff, interview questions, and finance Deep Learning, LLM, Startup, Influencer, Executive, Data Science Manager