Breadth and Depth First Search

When given a string, return the length of the longest distinct list of characters in the string. Example: abcdeba -> returns 5 for 'abcde'.

This can be solved 2 different ways.

Breadth First Search

  Is an algorithm where you check the neighbors of a given index to see whether they are something or not and track those that have been visited along the way. You keep track of the ones, you've visited, the ones you include in the resultset and a queue for managing the next index to review.

  As you traverse through each index you're getting all of the indexes next to the current one and checking to see if they've been visited or not and then adding them to the queue if you haven't visited them yet. You continue this until you've reached the end.

  The big difference between BFS and DFS is that in breadth first, you go are looping through all the shallow connections of the index before moving a step deeper. In DFS you inmmediately go into the deepest parts of the relational graph from the start.

In the islands question you are going to loop through the 2D array looking for if an index has a 'L' for land and update the result set with +1 if it does and hasn't been visited yet. When you first find one, then you use BFS to check each of it's neighbors to see if one of them is also an 'L' and hasn't been visited, if true you add them to the queue as well. This breadth loop loops until all 'L's are found. Then the you iterate again at the top making sure each next index hasn't been visited or isn't a 'L' until you've exhausted the 2D array.

Steps to complete:

1. Loop through the provided 2D array.
2. If the value of the current cell is 'L' AND you haven't visited that index before, THEN increase the island counter and start the breadth first search.
3. Capture all possible directions around the current cell.
4. Create a queue and add the current cell to it as the first item.
5. Mark the cell as visited.
6. While loop through the queue until it's empty.
7. Pop the top cell out of the queue and get it's row and column for reference.
8. Now loop through all the possible directions of neighbor cells around the current cell.
9. Check if they are valid options that can exist and if any contain values of 'L' AND haven't been visited yet.
10. If that neighbor is kosher, then mark it as visited and add it back to the queue so it may be processed later.
11. If none of the current cell's neighbors are possible 'L's then it goes to the next cell or back up the stack until it finds a cell that hasn't been visited yet or reaches the end of the 2D array.

import java.util.*;

public class Main {

    // Check if the cell (r, c) is valid for BFS traversal
    // It must lie within grid bounds, contain land ('L'), and not be visited yet
    static boolean isSafe(char[][] grid, int r, int c, boolean[][] visited) {
        int n = grid.length;
        int m = grid[0].length;
        return (r >= 0 && r < n && c >= 0 && c < m && grid[r][c] == 'L' && !visited[r][c]);
    }

    // Perform BFS to traverse all connected land cells (forming one island)
    static void bfs(char[][] grid, boolean[][] visited, int startR, int startC) {
        // Possible 8 directions (vertical, horizontal, and diagonal)
        int[] dRow = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] dCol = {-1, 0, 1, -1, 1, -1, 0, 1};

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{startR, startC});
        visited[startR][startC] = true;

        // Explore all reachable land cells for this island
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int r = cell[0];
            int c = cell[1];

            // Check all 8 neighbors of the current cell
            for (int k = 0; k < 8; k++) {
                int newR = r + dRow[k];
                int newC = c + dCol[k];
                if (isSafe(grid, newR, newC, visited)) {
                    visited[newR][newC] = true;
                    q.add(new int[]{newR, newC});
                }
            }
        }
    }

    // Count the total number of islands in the grid
    static int countIslands(char[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        boolean[][] visited = new boolean[n][m];
        int islandCount = 0;

        // Traverse every cell in the grid
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {

                // If an unvisited land cell is found, start BFS for that island
                if (grid[r][c] == 'L' && !visited[r][c]) {
                    bfs(grid, visited, r, c);
                    islandCount++;
                }
            }
        }

        return islandCount;
    }

    public static void main(String[] args) {
        char[][] grid = {
            {'L', 'L', 'W', 'W', 'W'},
            {'W', 'L', 'W', 'W', 'L'},
            {'L', 'W', 'W', 'L', 'L'},
            {'W', 'W', 'W', 'W', 'W'},
            {'L', 'W', 'L', 'L', 'W'}
        };

        System.out.println(countIslands(grid));
    }
}