Number Of Islands

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.graphs;

import java.util.*;

/* * ============================================================================================ * PROBLEM: Number of Islands * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a 2D grid map of '1's (land) and '0's (water). * Count the number of islands. * An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. * * --------------------- * 2. Logical Breakdown * --------------------- * This is a Connected Components problem on an implicit graph (the grid). * * Algorithm: * 1. Iterate through every cell (i, j) in the grid. * 2. If grid[i][j] == '1' (Land) AND not visited: * - We found a NEW island. Increment Count. * - Start a Traversal (DFS or BFS) from (i, j) to find the entire extent of this island. * - Mark all reachable '1's as visited (or turn them to '0' to save space). * * Traversal Logic (DFS): * - From (r, c), recursively visit (r+1, c), (r-1, c), (r, c+1), (r, c-1). * - Boundary checks: r, c must be within grid limits and grid[r][c] must be '1'. * * --------------------- * 3. Complexity * --------------------- * Time Complexity: O(N * M) * - We visit every cell at most twice (once in loop, once in DFS). * Space Complexity: O(N * M) * - Recursion stack in worst case (all '1's) or Queue for BFS. * * ============================================================================================ / public class NumberOfIslands { public int solve(int A) { // TODO: Implement solution return 0; }

public int numIslands(char[][] grid1) {
    return 1;
}

}