# 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.`