Number of Distinct Islands
Updated
Problem statement
A binary grid contains land (1) and water (0). An island is a maximal group of land cells connected horizontally or vertically. Diagonal contact does not connect cells.
Two islands have the same shape if translating one makes its land cells equal to the other. Rotations and reflections do not count as the same shape.
Return the number of distinct island shapes.
Function
numDistinctIslands(grid: int[][]) → intExamples
Example 1
grid = [[1,1,0,0,1,1],[1,0,0,0,1,0],[0,0,0,0,0,0]]return = 1Both L-shaped islands are translations of each other, so there is one shape.
Example 2
grid = [[1,0,1],[0,1,0],[1,0,1]]return = 1All five islands are single cells, so they share one shape.
Constraints
- 1 <= grid.length <= 200
- 1 <= grid[0].length <= 200
- All rows have the same length.
- Each grid entry is 0 or 1.
More Citadel Phone Screen questions
- Portfolio Tickers with Constant-Time Random PickPHONE SCREEN · Seen Nov 2026
- Square Root FunctionPHONE SCREEN · Seen Oct 2026
- Reachable Transfer PositionsPHONE SCREEN · Seen Oct 2026
- Spreadsheet Formula DependenciesPHONE SCREEN · Seen Oct 2026
- Merge Price-Delta FeedsPHONE SCREEN · Seen Sep 2026
- Reconcile Unmatched Trades with Timestamp TolerancePHONE SCREEN · Seen Sep 2026
- Top Ten Trades by Notional ValuePHONE SCREEN · Seen Sep 2026
- Exchange BBO and Market-Wide NBBOPHONE SCREEN · Seen Sep 2026
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Word Chain Jumps in a GridGoogle · PHONE SCREENGoogle interview questions
- Minimize CommuteDatabricks · OA · PHONE SCREENDatabricks interview questions
- Count Connected IslandsUber · PHONE SCREENUber interview questions
- Number of IslandsSpaceX · PHONE SCREENSpaceX interview questions
- Count Islands in a Binary GridApple · PHONE SCREENApple interview questions
- Find and Reconstruct a Binary-Matrix PathMeta · PHONE SCREEN · ONSITE INTERVIEWMeta interview questions
- Pacific Atlantic Water FlowAnduril · PHONE SCREENAnduril interview questions
- Xiangqi Horse ReachabilityeBay · PHONE SCREENeBay interview questions
- Grid Pathfinding with Obstacles (DFS)Roblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions