Number of Distinct Islands
Reported by candidates from Bloomberg's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
The detail that decides this Bloomberg OA from January 2021 is one line: shapes match only under translation, no rotation, no mirror. That single rule is the whole problem. It's Number of Distinct Islands, a grid flood fill where you count unique island shapes, not islands. If you've got an invite and 48 hours, this is a DFS or BFS you can write cold once you know how to fingerprint a shape. StealthCoder sits invisibly on your screen as a safety net if you blank mid-assessment, but the idea below is short enough to memorize tonight.
The problem
In an ocean, there are islands marked by 1. Water is represented by 0. Determine how many unique shapes (no rotation or mirror) among these islands. Islands are connected 4-directionally. Function numDistinctIslands(grid: int[][]) → int Complete the function numDistinctIslands in the editor. numDistinctIslands has the following parameter: int[][] grid: a 2D array of integers representing the ocean Returns int: the number of unique island shapes Examples Example 1 grid = [[1, 1, 1, 1, 0, 0], [1, 1, 0, 0, 0, 1], [0, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0], [0, 0, 1, 1, 1, 1], [1, 0, 1, 1, 0, 0]] return = 4 There are 4 unique island shapes: the 2 6-sized islands, the 2 2-sized islands, the 1 2-sized island, the 1 1-sized island. Standard BFS/DFS problem with a translation of the starting point to the origin of each island. The solution is done correctly and optimally with O(n) complexity. Constraints 1 ≤ grid.length, grid[i].length ≤ 500 grid[i][j] is 0 or 1. Cells are connected only in the four cardinal directions. Shapes are equal only under translation; rotations and reflections are distinct.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is normalizing each island so identical shapes produce identical keys. Run DFS or BFS from the first cell you hit in each island, and record every cell as an offset from that starting cell (row - r0, col - c0). Store the offsets in a list, then put a tuple or string of that list in a set. The set size is your answer. Traversal order has to be consistent, so use a fixed direction order every time. The common pitfall is hashing absolute coordinates, which makes every island look unique. Another is skipping the backtrack marker in a path-string approach, so different shapes collide. Mark cells visited as you go, either in place or with a separate array. On a 500 by 500 grid, recursive DFS can overflow the stack, so consider an iterative version. StealthCoder is your hedge in the live OA if the offset idea slips your mind under pressure.
StealthCoder is the hedge for the one pattern you didn't drill. It runs invisibly during the screen share.
You can drill Number of Distinct Islands cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. If you're reading this with an OA window open, you're who this was built for.
Get StealthCoderRelated leaked OAs
This OA pattern shows up on LeetCode as number of distinct islands. If you have time before the OA, drill that.
You've seen the question.
Make sure you actually pass Bloomberg's OA.
Bloomberg reuses patterns across OAs. If you're reading this with an OA window open, you're who this was built for. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Number of Distinct Islands FAQ
What's the trick to Number of Distinct Islands?+
Normalize each island by recording cell positions relative to its starting cell, the first one found scanning top-left to bottom-right. Two islands with the same offset set are the same shape under translation. Put each normalized signature in a set and return its size.
Do rotations and reflections count as the same shape here?+
No. The constraints say shapes are equal only under translation. A rotated or mirrored island counts as distinct. That makes the problem easier, since you only need offsets from the start cell, with no canonical-form logic for rotations.
Should I use DFS or BFS?+
Either works. Both visit every cell once. DFS is shorter to write recursively, but on a grid up to 500 by 500 the recursion depth can get large. If you're worried, use an iterative stack or BFS with a queue and a fixed direction order.
How do I avoid false matches between different shapes?+
Use the list of relative offsets in a consistent traversal order as the key, or a path string that also records backtracking steps. Without a consistent order or backtrack markers, two different shapes can serialize to the same string. Offsets from a fixed start cell are the safest option.
How do I prepare for this in 48 hours?+
Write the solution from scratch twice. First do plain Number of Islands with DFS, then add the offset signature and a set. Test it on the example that returns 4. Then check edge cases like an all-water grid, an all-land grid, and single-cell islands.