3619. Count Islands With Total Value Divisible by K

MediumView on LeetCode

Array Depth-First Search Breadth-First Search Union Find Matrix

Time: O(m * n)

Space: O(m * n)

Problem Overview

An island is a 4-connected group of cells whose values are positive.

Intuition

An island is a 4-connected group of cells whose values are positive. Cells that hold 0 are water and never join an island. The question only asks whether the island sum is divisible by k, so the flood keeps a running residue. Each newly reached cell adds its own value modulo k, and the residue drops by k once it reaches k. The cell is then set to 0, so a later scan will not start the same island again. Cells that still need expanding wait on an explicit stack, which keeps a long snake of land on the heap.

Algorithm

1Allocate one stack large enough to hold every cell.
2Scan the grid and skip cells that are already 0.
3From each positive cell, flood the island. Add the cell value modulo k into the residue, mark the cell 0, and push its four neighbors.
4Count the island when the residue that comes back is 0.

Example Walkthrough

Input: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5

1.The cells 2, 1, and 5 form one island. Their sum is 8, and 8 modulo 5 is 3, so this island does not count.
2.The lone 5 on the second row has residue 0, so it counts.
3.The cells 1, 1, 4, 7, and 2 sum to 15, which is divisible by 5, so that island counts.
4.The lone 8 leaves residue 3.

Output: 2

Common Pitfalls

•Land starts out positive. Setting a visited land cell to 0 is safe, because a real water cell was already 0.
•Add the cell value modulo k. A single subtraction of k is then enough, since both the old residue and the added piece are smaller than k.
•Keep expanding all four neighbors after the residue hits 0. Stopping early leaves unmarked land that a later start would count as a second island.
•A recursive flood on a snake of 100000 land cells can overflow the call stack. The explicit stack stays on the heap.

3619.cs

// Approach: An island is a 4-connected group of positive cells. Only the sum
// modulo k matters, so each cell adds its value modulo k into a running
// residue and is then set to 0. An explicit stack expands the four
// neighbors, so a snake of land stays on the heap.
// Time: O(m * n) Space: O(m * n)

public class Solution
{
    public int CountIslands(int[][] grid, int k)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int ans = 0;
        int[] stack = new int[m * n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] > 0 && Flood(grid, stack, i, j, k) == 0)
                    ans++;
        return ans;
    }

    private static int Flood(int[][] grid, int[] stack, int si, int sj, int k)
    {
        int m = grid.Length;
        int n = grid[0].Length;
        int top = 0;
        int residue = Push(grid, stack, ref top, si, sj, m, n, k, 0);
        while (top > 0)
        {
            int id = stack[--top];
            int r = id / n;
            int c = id - r * n;
            residue = Push(grid, stack, ref top, r - 1, c, m, n, k, residue);
            residue = Push(grid, stack, ref top, r + 1, c, m, n, k, residue);
            residue = Push(grid, stack, ref top, r, c - 1, m, n, k, residue);
            residue = Push(grid, stack, ref top, r, c + 1, m, n, k, residue);
        }
        return residue;
    }

    private static int Push(int[][] grid, int[] stack, ref int top, int r, int c, int m, int n, int k, int residue)
    {
        if (r < 0 || c < 0 || r == m || c == n || grid[r][c] == 0)
            return residue;
        residue += grid[r][c] % k;
        if (residue >= k)
            residue -= k;
        grid[r][c] = 0;
        stack[top++] = r * n + c;
        return residue;
    }
}

Was this solution helpful?