Largest Square of Ones in a Grid
Updated
Problem statement
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[][]) → intExamples
Example 1
matrix = [["0","1","1","0"],["1","1","1","1"],["1","1","1","1"],["0","1","1","0"],["1","0","0","0"]]return = 4Rows 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 = 1No 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 = 0The grid has no ones at all, so the answer is 0.
Constraints
m == matrix.lengthandn == matrix[i].lengthfor 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)