FastPrepLargest Square of Ones in a Grid
Problems/Largest Square of Ones in a Grid

Largest Square of Ones in a Grid

Expedia logoExpedia● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: A post published on September 8, 2018, by a student at a college visited by Expedia for intern hiring, lists this task among the questions of its second technical interview.

The post gives only the title of the task, with no statement, limits or examples, so it does not settle whether the answer is a side length or an area. Here, the grid holds the characters 0 and 1 with at most 100 rows and 100 columns. The answer is the area of the largest all-ones square.

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

You are given a grid matrix of the characters '0' and '1'. Look for a square block of cells, with its sides along the rows and columns of the grid, in which every cell is '1'.

Return the area of the largest such square, that is, the number of cells it contains. If the grid has no '1', return 0.

Function

maximalSquare(matrix: char[][]) → int

Examples

Example 1

matrix = [["0","1","1","0"],["1","1","1","1"],["1","1","1","1"],["0","1","1","0"],["1","0","0","0"]]return = 4
matrix
01230011011111211113011041000

Rows 2 and 3 (counting from 1) and columns 2 and 3 form a 2 by 2 square of ones, so its area is 4. No 3 by 3 block is all ones: each of the six 3 by 3 blocks contains a zero from row 1, row 4 or row 5. The answer is 4.

Example 2

matrix = [["1","0","1","1"],["0","1","0","1"]]return = 1
matrix
01230101110101

No two ones touch to form a 2 by 2 block, so the best square is a single cell with area 1.

Example 3

matrix = [["0","0","0"],["0","0","0"]]return = 0
matrix
01200001000

The grid has no ones at all, so the answer is 0.

Constraints

  • m == matrix.length and n == matrix[i].length for every row, so all rows have the same length.
  • 1 <= m, n <= 100
  • Each matrix[i][j] is the character '0' or '1'.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Maximum All-Ones Square Side LengthOmnissa · ONSITE INTERVIEWOmnissa interview questions
  • Minimum Path SumAmazon · ONSITE INTERVIEW
  • Minimum Path SumMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Minimum Path SumBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
  • Bomb Enemy Best CoordinatesSambaNova Systems · ONSITE INTERVIEWSambaNova Systems interview questions
  • Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
  • Longest Increasing Path in a MatrixVisa · ONSITE INTERVIEWVisa interview questions
  • Maximal Rectangle in a Binary MatrixGoogle · ONSITE INTERVIEWGoogle interview questions
  • Find Robots by Blocker DistancesUber · PHONE SCREENUber interview questions
  • Largest Square of OnesOpenAI · OAOpenAI interview questions

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int maximalSquare(char[][] matrix) {
        // Write your code here.
    }
}
Checking account…