Largest Universally Bounded Subgrid
Updated
Problem statement
Given a positive-integer square grid, return the greatest side length k such that every contiguous k × k subgrid has sum at most maxSum.
It is insufficient for only one square of that size to fit: no square of the chosen size may exceed the limit. Return 0 when no positive side length satisfies the rule. For this exercise, assume the input grid must remain unchanged.
Function
largestSubgrid(grid: int[][], maxSum: int) → intExamples
Example 1
grid = [[1,1,1],[1,1,1],[1,1,1]]maxSum = 4return = 2Every 2 by 2 square sums to 4; the full 3 by 3 square sums to 9.
Example 2
grid = [[1,1,1,1],[2,2,2,2],[3,3,3,3],[4,4,4,4]]maxSum = 39return = 3The greatest 3 by 3 sum is 27, while the full 4 by 4 sum is 40.
Example 3
grid = [[4,5],[6,7]]maxSum = 2return = 0Some 1 by 1 squares already exceed 2, so no positive size satisfies the universal rule.
Constraints
1 <= grid.length <= 1550, and every row has the same length as the number of rows.1 <= grid[r][c] <= 10000000.1 <= maxSum <= 1000000000.- The sum of the entire grid is at most
1000000000.
More Roblox Online Assessment questions
- Centered Block Placement QueriesOA · Seen Oct 2026
- Robot Navigation Around LasersOA · Seen Oct 2026
- Factory Batch Profit (Game Adaptation)OA · Seen Sep 2026
- Nested Recipe Blocks (Game Adaptation)OA · Seen Sep 2026
- Vehicle Builds for Required Terrain (Game Adaptation)OA · Seen Sep 2026
- Track Received Byte RangesOA · Seen Sep 2026
- Break a PalindromeOA · Seen Jun 2026
- Count Pairs Differing in One DigitOA · Seen Oct 2025
- Find Zero Cells in a 2×2 GridOA · Seen Oct 2025
- Cat Route Budget Planning (Game Adaptation)OA · Seen Aug 2025
Similar questions at other companies
- Find Minimum Time to Create Beautiful CanvasAmazon · OA
- Sub-matrix SumsIMC Trading · OAIMC Trading interview questions
- Largest Sub-GridMathWorks · OAMathWorks interview questions
- Largest Square Sub-Grid Within a Sum LimitC3.ai · OAC3.ai interview questions
- Maximum Non-Decreasing Array LengthVisa · OAVisa interview questions
- Minimum Cost to Make Array EqualWalmart · OAWalmart interview questions
- Largest Two Non-Overlapping Buildable SquaresAmerican Express · OAAmerican Express interview questions
- Longest Subarray with Sum at Most KGoogle · OAGoogle interview questions
- Maximum CellsMicrosoft · OAMicrosoft interview questions
- Find Maximum DistanceWells Fargo · OAWells Fargo interview questions