HackerRank Coding Interview Largest Sub-Grid

Amber Ivanna Trujillo

6 min readMar 5

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

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

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

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.