Katkat
Back

Count islands on a torus grid

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates skills in graph and grid algorithms, topology-aware adjacency (torus wrap-around), and maintaining dynamic connectivity under incremental updates.

You are given an m x n binary grid representing water ( 0) and land (

  1. laid out on a torus: the top edge is adjacent to the bottom edge and the left edge is adjacent to the right edge. Two land cells are connected if they share a side (4-directional), considering wrap-around adjacency. Return the number of connected land components (islands). Follow-ups: (
  2. Provide two distinct approaches (e.g., graph search and disjoint-set). (
  3. Analyze the time and space complexities. (
  4. Extend the solution to support a stream of single-cell flips between 0 and 1 and report the island count after each update.