Number of Islands II

HardGraphsunion find

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have an m x n map that starts as all water. You are given a list positions, where positions[i] = [r, c] turns cell (r, c) into land on step i. After each step, count the islands. An island is a maximal group of land cells connected horizontally or vertically. Return an array whose i-th value is the island count right after step i. A position may repeat. Adding land where land already exists changes nothing, but it still produces an entry in the output. Aim for close to O(k) total time for k positions.

Examples

Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output: [1, 1, 2, 3]
(0,1) joins (0,0). (1,2) only touches it diagonally, so it starts a second island. (2,1) makes a third.
Input: m = 1, n = 1, positions = [[0,0]]
Output: [1]
The only cell becomes one island.

Constraints

  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • 1 <= positions.length <= 10^4
  • 0 <= r < m, 0 <= c < n

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More union find problems