Module Week 6

Island Perimeter

LeetCode 463

Easy ▼

Source

LeetCode 463 - Island Perimeter

Problem

You are given a rows x cols grid where grid[i][j] is either 0 (water) or 1 (land). The grid contains exactly one island (one or more connected land cells). The island doesn't have any "lakes" (water inside that isn't connected to the water around the island). Cells are connected horizontally/vertically (not diagonally). Determine the perimeter of the island.

Function Signature

islandPerimeter(grid: int[][]) -> int

Examples

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16

Input: grid = [[1]]
Output: 4

Input: grid = [[1,0]]
Output: 4

Each land cell contributes 4 edges. But when two land cells are adjacent, the shared edge is interior and doesn't count toward the perimeter.

So the perimeter = total edges from land cells minus the shared interior edges.

Use BFS starting from any land cell. Add the cell to a queue. While the queue is not empty, pop a cell and check all 4 neighbours. Each neighbour that is water or out of bounds adds 1 to the perimeter. Enqueue unvisited land neighbours.

⚙ Knowledge Hub: Using Graphs

Find any land cell (1) in the grid
Start a BFS from that cell: add it to a queue and mark it as visited (e.g. set to -1)
While the queue is not empty, dequeue a cell and check all 4 directions: if the neighbour is water or out of bounds, add 1 to the perimeter; if it's unvisited land, mark it visited and enqueue it
When the queue is empty, return the accumulated perimeter

Since there is exactly one island, one BFS from any land cell will visit every land cell and compute the full perimeter.

from collections import deque

def islandPerimeter(grid):
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                perimeter = 0
                q = deque([(r, c)])
                grid[r][c] = -1  # visited
                while q:
                    cr, cc = q.popleft()
                    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nr, nc = cr+dr, cc+dc
                        if nr<0 or nr>=rows or nc<0 or nc>=cols or grid[nr][nc]==0:
                            perimeter += 1
                        elif grid[nr][nc] == 1:
                            grid[nr][nc] = -1
                            q.append((nr, nc))
                return perimeter
    return 0

int islandPerimeter(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    int dirs[] = {-1,0,1,0,-1};
    for (int r = 0; r < m; r++)
      for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) {
            int peri = 0;
            queue<pair<int,int>> q;
            q.push({r,c}); grid[r][c] = -1;
            while (!q.empty()) {
                auto [cr,cc] = q.front(); q.pop();
                for (int d=0;d<4;d++) {
                    int nr=cr+dirs[d], nc=cc+dirs[d+1];
                    if (nr<0||nr>=m||nc<0||nc>=n||grid[nr][nc]==0)
                        peri++;
                    else if (grid[nr][nc]==1) {
                        grid[nr][nc]=-1; q.push({nr,nc});
                    }
                }
            }
            return peri;
        }
    return 0;
}

public int IslandPerimeter(int[][] grid) {
    int m = grid.Length, n = grid[0].Length;
    int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
    for (int r = 0; r < m; r++)
      for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) {
            int peri = 0;
            var q = new Queue<(int,int)>();
            q.Enqueue((r,c)); grid[r][c] = -1;
            while (q.Count > 0) {
                var (cr,cc) = q.Dequeue();
                for (int d = 0; d < 4; d++) {
                    int nr=cr+dr[d], nc=cc+dc[d];
                    if (nr<0||nr>=m||nc<0||nc>=n||grid[nr][nc]==0)
                        peri++;
                    else if (grid[nr][nc]==1) {
                        grid[nr][nc]=-1; q.Enqueue((nr,nc));
                    }
                }
            }
            return peri;
        }
    return 0;
}

public int islandPerimeter(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int r = 0; r < m; r++)
      for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) {
            int peri = 0;
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{r,c}); grid[r][c] = -1;
            while (!q.isEmpty()) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int nr=cur[0]+d[0], nc=cur[1]+d[1];
                    if (nr<0||nr>=m||nc<0||nc>=n||grid[nr][nc]==0)
                        peri++;
                    else if (grid[nr][nc]==1) {
                        grid[nr][nc]=-1;
                        q.add(new int[]{nr,nc});
                    }
                }
            }
            return peri;
        }
    return 0;
}

Find Centre of Star Graph

LeetCode 1791

Easy ▼

Source

LeetCode 1791 - Find Centre of Star Graph

Problem

There is an undirected star graph consisting of n nodes labelled from 1 to n. A star graph is a graph where there is one centre node and exactly n - 1 edges that connect the centre node with every other node. You are given a 2D integer array edges where each edges[i] = [u, v] indicates that there is an edge between nodes u and v. Return the centre of the given star graph.

Function Signature

findCentre(edges: int[][]) -> int

Examples

Input: edges = [[1,2],[2,3],[4,2]]
Output: 2
Explanation: Node 2 is connected to every other node, so 2 is the centre.

Input: edges = [[1,2],[5,1],[1,3],[1,4]]
Output: 1

A star graph has one centre connected to all other nodes. The centre appears in every edge. Every other node appears in exactly one edge.

In graph terminology, the centre has degree n-1 (the highest degree).

Build an adjacency list from the edge list (a fundamental graph operation). Then run a BFS from any node using a queue. The centre node is the one whose adjacency list length equals the number of edges (i.e. it connects to every other node).

⚙ Knowledge Hub: Using Graphs

Build an adjacency list: for each edge [u, v], add v to adj[u] and u to adj[v]
Pick any starting node and run BFS (using a queue). The first node you encounter whose neighbour count equals n - 1 (i.e. len(edges)) is the centre
Alternatively, since the centre must appear in every edge, it must appear in both edges[0] and edges[1]. Find the common node

In a star graph BFS from the centre visits every node in one level. From any leaf, BFS reaches the centre in one step and then fans out.

from collections import defaultdict, deque

def findCentre(edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    n = len(edges) + 1  # star graph has n-1 edges
    # BFS from node in first edge
    start = edges[0][0]
    visited = set([start])
    q = deque([start])
    while q:
        node = q.popleft()
        if len(adj[node]) == n - 1:
            return node  # centre found
        for nb in adj[node]:
            if nb not in visited:
                visited.add(nb)
                q.append(nb)
    return -1

int findCentre(vector<vector<int>>& edges) {
    int n = edges.size() + 1;
    unordered_map<int, vector<int>> adj;
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    unordered_set<int> vis;
    queue<int> q;
    q.push(edges[0][0]);
    vis.insert(edges[0][0]);
    while (!q.empty()) {
        int node = q.front(); q.pop();
        if ((int)adj[node].size() == n - 1) return node;
        for (int nb : adj[node])
            if (!vis.count(nb)) { vis.insert(nb); q.push(nb); }
    }
    return -1;
}

public int FindCentre(int[][] edges) {
    int n = edges.Length + 1;
    var adj = new Dictionary<int, List<int>>();
    foreach (var e in edges) {
        if (!adj.ContainsKey(e[0])) adj[e[0]] = new List<int>();
        if (!adj.ContainsKey(e[1])) adj[e[1]] = new List<int>();
        adj[e[0]].Add(e[1]);
        adj[e[1]].Add(e[0]);
    }
    var vis = new HashSet<int>();
    var q = new Queue<int>();
    q.Enqueue(edges[0][0]);
    vis.Add(edges[0][0]);
    while (q.Count > 0) {
        int node = q.Dequeue();
        if (adj[node].Count == n - 1) return node;
        foreach (int nb in adj[node])
            if (vis.Add(nb)) q.Enqueue(nb);
    }
    return -1;
}

public int findCentre(int[][] edges) {
    int n = edges.length + 1;
    Map<Integer, List<Integer>> adj = new HashMap<>();
    for (int[] e : edges) {
        adj.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
        adj.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);
    }
    Set<Integer> vis = new HashSet<>();
    Queue<Integer> q = new LinkedList<>();
    q.add(edges[0][0]);
    vis.add(edges[0][0]);
    while (!q.isEmpty()) {
        int node = q.poll();
        if (adj.get(node).size() == n - 1) return node;
        for (int nb : adj.get(node))
            if (vis.add(nb)) q.add(nb);
    }
    return -1;
}

Colouring A Border

LeetCode 1034

Medium ▼

Source

LeetCode 1034 - Colouring A Border

Problem

You are given an m x n integer matrix grid, and three integers row, col, and color. Each value in the grid represents the colour of the grid square at that location. Two squares are adjacent if they are next to each other in any of the 4 directions. Two squares belong to the same connected component if they have the same colour and they are adjacent. The border of a connected component is all squares in the component that are either adjacent to a square not in the component, or on the boundary of the grid. Colour the border of the connected component that contains grid[row][col] with color. Return the final grid.

Function Signature

colourBorder(grid: int[][], row: int, col: int, colour: int) -> int[][]

Examples

Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]

Input: grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
Output: [[1,3,3],[2,3,3]]

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
Output: [[2,2,2],[2,1,2],[2,2,2]]

You need to find the connected component that includes grid[row][col]. Then identify which cells in that component are on the border.

A cell is a border cell if it's on the edge of the grid OR at least one of its 4 neighbours has a different colour (i.e. isn't part of the same component).

Only re-colour the border cells; leave interior cells unchanged.

Use BFS starting from (row, col) to find all cells in the connected component. Add the starting cell to a queue and process neighbours level by level. As you visit each cell, check if it's a border cell.

⚙ Knowledge Hub: Using Graphs

Don't re-color cells during traversal or you'll break the adjacency check. Collect border cells first, then re-color them at the end.

Save the original colour at (row, col)
BFS from (row, col) using a queue. Only enqueue cells with the original colour. Mark visited cells
For each visited cell, check if it's a border: is it on row 0, last row, col 0, last col, OR does any of its 4 neighbours have a different colour?
Collect all border cells in a list
After traversal, loop through the border list and set each cell to the new color

from collections import deque

def colourBorder(grid, row, col, colour):
    m, n = len(grid), len(grid[0])
    orig = grid[row][col]
    visited = set([(row, col)])
    border = []
    q = deque([(row, col)])
    while q:
        r, c = q.popleft()
        is_border = False
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r + dr, c + dc
            if nr < 0 or nr >= m or nc < 0 or nc >= n:
                is_border = True
            elif grid[nr][nc] != orig:
                is_border = True
            elif (nr, nc) not in visited:
                visited.add((nr, nc))
                q.append((nr, nc))
        if is_border:
            border.append((r, c))
    for r, c in border:
        grid[r][c] = colour
    return grid

vector<vector<int>> colourBorder(
        vector<vector<int>>& grid,
        int row, int col, int colour) {
    int m = grid.size(), n = grid[0].size();
    int orig = grid[row][col];
    vector<vector<bool>> vis(m, vector<bool>(n, false));
    vector<pair<int,int>> border;
    int dirs[] = {-1,0,1,0,-1};
    queue<pair<int,int>> q;
    q.push({row, col}); vis[row][col] = true;
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        bool isBorder = false;
        for (int d = 0; d < 4; d++) {
            int nr = r+dirs[d], nc = c+dirs[d+1];
            if (nr<0||nr>=m||nc<0||nc>=n) isBorder = true;
            else if (grid[nr][nc] != orig) isBorder = true;
            else if (!vis[nr][nc]) {
                vis[nr][nc] = true; q.push({nr, nc});
            }
        }
        if (isBorder) border.push_back({r, c});
    }
    for (auto& [r, c] : border) grid[r][c] = colour;
    return grid;
}

public int[][] ColourBorder(int[][] grid,
        int row, int col, int colour) {
    int m = grid.Length, n = grid[0].Length;
    int orig = grid[row][col];
    var vis = new bool[m, n];
    var border = new List<(int, int)>();
    int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
    var q = new Queue<(int, int)>();
    q.Enqueue((row, col)); vis[row, col] = true;
    while (q.Count > 0) {
        var (r, c) = q.Dequeue();
        bool isBorder = false;
        for (int d = 0; d < 4; d++) {
            int nr = r+dr[d], nc = c+dc[d];
            if (nr<0||nr>=m||nc<0||nc>=n) isBorder = true;
            else if (grid[nr][nc] != orig) isBorder = true;
            else if (!vis[nr, nc]) {
                vis[nr, nc] = true; q.Enqueue((nr, nc));
            }
        }
        if (isBorder) border.Add((r, c));
    }
    foreach (var (r, c) in border) grid[r][c] = colour;
    return grid;
}

public int[][] colourBorder(int[][] grid,
        int row, int col, int colour) {
    int m = grid.length, n = grid[0].length;
    int orig = grid[row][col];
    boolean[][] vis = new boolean[m][n];
    List<int[]> border = new ArrayList<>();
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{row, col}); vis[row][col] = true;
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1];
        boolean isBorder = false;
        for (int[] d : dirs) {
            int nr = r+d[0], nc = c+d[1];
            if (nr<0||nr>=m||nc<0||nc>=n) isBorder = true;
            else if (grid[nr][nc] != orig) isBorder = true;
            else if (!vis[nr][nc]) {
                vis[nr][nc] = true;
                q.add(new int[]{nr, nc});
            }
        }
        if (isBorder) border.add(new int[]{r, c});
    }
    for (int[] b : border) grid[b[0]][b[1]] = colour;
    return grid;
}

Max Area of Island

LeetCode 695

Medium ▼

Source

LeetCode 695 - Max Area of Island

Problem

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical). You may assume all four edges of the grid are surrounded by water. The area of an island is the number of cells with a value of 1 in the island. Return the maximum area of an island in grid. If there is no island, return 0.

Function Signature

maxAreaOfIsland(grid: int[][]) -> int

Examples

Input: grid = [
  [0,0,1,0,0,0,0,1,0,0,0,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0,0,0,0,1,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

The grid can have multiple islands. You need to find the area (number of land cells) of the largest one. If no land exists, return 0.

Connections are only horizontal/vertical, not diagonal.

Use BFS to explore each island. When you find an unvisited land cell, add it to a queue and process neighbours level by level. Count every cell you visit. That count is the island's area.

⚙ Knowledge Hub: Using Graphs

Track the maximum area seen across all islands. Mark cells as visited (e.g. set them to 0) so you don't count them twice.

Initialise maxArea = 0
Loop through every cell in the grid
When you find a 1, launch BFS from that cell using a queue
In the BFS, mark each visited cell as 0 (or use a visited set) and count the cells
After the traversal finishes, update maxArea if this island's area is larger
Return maxArea

Sinking the island (setting visited cells to 0) avoids needing an extra visited array and is a common BFS trick on grid problems.

from collections import deque

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])
    max_area = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                area = 0
                q = deque([(r, c)])
                grid[r][c] = 0  # sink
                while q:
                    cr, cc = q.popleft()
                    area += 1
                    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                        nr, nc = cr+dr, cc+dc
                        if 0<=nr<rows and 0<=nc<cols and grid[nr][nc]==1:
                            grid[nr][nc] = 0
                            q.append((nr, nc))
                max_area = max(max_area, area)
    return max_area

int maxAreaOfIsland(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size(), ans = 0;
    int dirs[] = {-1,0,1,0,-1};
    for (int r = 0; r < m; r++)
      for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) {
            int area = 0;
            queue<pair<int,int>> q;
            q.push({r,c}); grid[r][c] = 0;
            while (!q.empty()) {
                auto [cr,cc] = q.front(); q.pop();
                area++;
                for (int d=0;d<4;d++) {
                    int nr=cr+dirs[d], nc=cc+dirs[d+1];
                    if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==1) {
                        grid[nr][nc]=0; q.push({nr,nc});
                    }
                }
            }
            ans = max(ans, area);
        }
    return ans;
}

public int MaxAreaOfIsland(int[][] grid) {
    int m = grid.Length, n = grid[0].Length, ans = 0;
    int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
    for (int r = 0; r < m; r++)
      for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) {
            int area = 0;
            var q = new Queue<(int,int)>();
            q.Enqueue((r,c)); grid[r][c] = 0;
            while (q.Count > 0) {
                var (cr,cc) = q.Dequeue();
                area++;
                for (int d = 0; d < 4; d++) {
                    int nr=cr+dr[d], nc=cc+dc[d];
                    if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==1) {
                        grid[nr][nc]=0; q.Enqueue((nr,nc));
                    }
                }
            }
            ans = Math.Max(ans, area);
        }
    return ans;
}

public int maxAreaOfIsland(int[][] grid) {
    int m = grid.length, n = grid[0].length, ans = 0;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    for (int r = 0; r < m; r++)
      for (int c = 0; c < n; c++)
        if (grid[r][c] == 1) {
            int area = 0;
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{r,c}); grid[r][c] = 0;
            while (!q.isEmpty()) {
                int[] cur = q.poll();
                area++;
                for (int[] d : dirs) {
                    int nr=cur[0]+d[0], nc=cur[1]+d[1];
                    if (nr>=0&&nr<m&&nc>=0&&nc<n&&grid[nr][nc]==1) {
                        grid[nr][nc]=0;
                        q.add(new int[]{nr,nc});
                    }
                }
            }
            ans = Math.max(ans, area);
        }
    return ans;
}

MODULE WEEK 6