Largest Square Sub-Grid Within a Sum Limit
Updated
Problem statement
You are given an n x n grid of positive integers and an integer maxSum. A k x k square is any block of k consecutive rows and k consecutive columns of the grid.
Return the largest side length k such that every k x k square in the grid has a sum of at most maxSum.
- A square whose sum is exactly
maxSumis fine. - It is not enough for some squares of a size to fit. One square over the limit rules out that size.
- If even a single cell is greater than
maxSum, return0.
Function
largestSubgrid(grid: int[][], maxSum: int) → intExamples
Example 1
grid = [[1,2,3],[4,5,6],[7,8,9]]maxSum = 27return = 1Every single cell is at most 9, so size 1 works. The four 2 x 2 squares have sums 1 + 2 + 4 + 5 = 12, 2 + 3 + 5 + 6 = 16, 4 + 5 + 7 + 8 = 24 and 5 + 6 + 8 + 9 = 28. Three of them fit within 27, but the bottom-right one does not, so size 2 fails. The answer is 1.
Example 2
grid = [[1,2,3],[4,5,6],[7,8,9]]maxSum = 28return = 2Now all four 2 x 2 sums (12, 16, 24 and 28) are at most 28, so size 2 works. The only 3 x 3 square is the whole grid, with sum 45, which is more than 28. The answer is 2.
Example 3
grid = [[5,1],[1,1]]maxSum = 4return = 0The cell with value 5 is a 1 x 1 square whose sum is more than 4, so even size 1 fails. The answer is 0.
Constraints
1 <= grid.length <= 50grid[i].length == grid.length1 <= grid[i][j] <= 1051 <= maxSum <= 109
More C3.ai interview questions
- Drop Recent Duplicate MessagesOA · Seen Oct 2026
- Maximum K-Star SumOA · Seen Oct 2026
- Prefix Scores With the Running MaximumOA · Seen Jan 2023
- Tree Node With Maximum BeautyOA · Seen Nov 2022
- Count Vowel Strings With Follow RulesOA · Seen Apr 2022
- Photo Album Insert OrderOA · Seen Apr 2022
- Sort by Frequency, Then ValueOA · Seen Apr 2022
- Count Distinct Binary Search TreesOA · Seen Mar 2022
- Count Palindromic Subsequences of Length KOA · Seen Mar 2022
- Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024
Similar questions at other companies
- Shortest Path Around Rectangular ObstaclesDRW · OADRW interview questions
- Choose ContainersIMC Trading · OAIMC Trading interview questions
- Largest Sub-GridMathWorks · OAMathWorks interview questions
- Minimum Size Subarray SumMicrosoft · OAMicrosoft interview questions
- Grid Path With the Most ClearanceDocuSign · OADocuSign interview questions
- Calculate Total Distance TravelledAmazon · OA
- TikTok Metrics AnalysisTikTok · OATikTok interview questions
- Maximum Distinct Items Within a BudgetAdobe · OAAdobe interview questions
- Calculating QuantilesIndeed · OAIndeed interview questions
- Count Lamps Lighting Each PointCapital One · OACapital One interview questions