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.