FastPrepLargest Square Sub-Grid Within a Sum Limit
Problems/Largest Square Sub-Grid Within a Sum Limit

Largest Square Sub-Grid Within a Sum Limit

C3.ai logoC3.ai● MediumNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: This was one of two questions in a 2023 C3.ai new grad online assessment. The author posted screenshots of the questions, and only their worked examples could be read. For a 3 x 3 grid, they show how the answer moves from 1 to 2 to 3 as the limit grows, and that the answer is the largest size where every square of that size stays within the limit.

The statement here is rebuilt from those worked examples. The part that could not be read leaves out the limits and the answer when even one cell is too big. Here the grid is always square, the answer is 0 when no size works, and the limits are our choice. The examples are new, and the report's worked example is one of the hidden tests.

Our version is about 90% the same as the reported question.

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 maxSum is 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, return 0.

Function

largestSubgrid(grid: int[][], maxSum: int) → int

Examples

Example 1

grid = [[1,2,3],[4,5,6],[7,8,9]]maxSum = 27return = 1
grid
012012314562789

Every 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 = 2
grid
012012314562789

Now 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 = 0
grid
01051111

The 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 <= 50
  • grid[i].length == grid.length
  • 1 <= grid[i][j] <= 105
  • 1 <= 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

Interview reports that mention this question

  • C3.ai New Grad Interviews: 25 Experiences (Part 1 of 2)

C3.ai interview experiences

  • C3.ai FDE and Other New Grad Roles: 5 Experiences (Part 2 of 2)
  • C3.ai New Grad Forward Deployed Engineer Interview: 1 Experience
All C3.ai interview questionsSee C3.ai hiring insights
Saved
class Solution {
    public int largestSubgrid(int[][] grid, int maxSum) {
        // Write your code here.
    }
}
Checking account…