C++ Coding Test Course, Depth First Search

1. Problem Description

The given problem is as follows:

Implement an algorithm to find the size of the largest group of consecutive 1s in a two-dimensional array (N x M) composed of integers. A group is defined as a subset of 1s that are connected vertically or horizontally. Additionally, non-consecutive 1s are treated as different groups.

The size of the array (N, M) is between 1 and 100.

2. Problem Analysis

This problem is about using graph search algorithms like DFS (Depth-First Search) or BFS (Breadth-First Search) to find connected components. It can be solved by counting the number of connected 1s and keeping track of the maximum size of the group.

The input array can be represented in the following form:

    1 0 0 1 1
    1 1 0 0 0
    0 0 1 1 1
    0 1 0 0 0
    1 1 1 0 0

In this case, the size of the largest group will be 5.

3. Approach

We need to use depth-first search to find and count connected 1s. DFS is stack-based and can be implemented either recursively or explicitly with a stack. The following are the steps to solve the problem:

  1. Iterate through the two-dimensional array and execute DFS when a 1 is found.
  2. In DFS, explore connected 1s by moving vertically and horizontally and increase the count.
  3. After exploring, compare and update the maximum group size.
  4. Once the exploration is complete, return the final maximum group size.

4. Code Implementation

Below is the C++ code implementing the above approach:


#include 
#include 
#include 

using namespace std;

class Solution {
public:
    int N, M; // Size of the array
    vector> directions{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // Directions for up, down, left, right

    // Implementation of DFS
    int dfs(int x, int y, vector>& grid) {
        if (x < 0 || x >= N || y < 0 || y >= M || grid[x][y] == 0) {
            return 0; // Out of bounds or 0 case
        }

        grid[x][y] = 0; // Mark as visited
        int count = 1; // Count current 1

        // Recursive calls in four directions
        for (const auto& dir : directions) {
            count += dfs(x + dir[0], y + dir[1], grid);
        }

        return count;
    }

    int largestGroupSize(vector>& grid) {
        N = grid.size();
        M = grid[0].size();
        int maxSize = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1) { // When 1 is found
                    int groupSize = dfs(i, j, grid); // Call DFS
                    maxSize = max(maxSize, groupSize); // Update maximum group size
                }
            }
        }

        return maxSize;
    }
};

int main() {
    Solution sol;
    vector> grid = {
        {1, 0, 0, 1, 1},
        {1, 1, 0, 0, 0},
        {0, 0, 1, 1, 1},
        {0, 1, 0, 0, 0},
        {1, 1, 1, 0, 0}
    };

    int result = sol.largestGroupSize(grid);
    cout << "Size of the largest group: " << result << endl;
    return 0;
}

5. Code Explanation

The above C++ code is structured as follows:

  1. Variable declaration: N and M store the size of the array, and directions defines movement directions for up, down, left, and right.
  2. DFS function: The dfs function recursively counts the number of connected 1s starting from the current position. It checks for boundary conditions and visit status.
  3. Main function: The largestGroupSize function iterates through the entire array, calling DFS every time a 1 is found to calculate the group size. It updates the maximum size and returns the final result.

6. Testing and Results

The above code can be tested with various cases. For example, we can change the size of groups or add new group structures to observe different results.

A successful result would be:

Size of the largest group: 5

7. Time Complexity Analysis

This algorithm has a time complexity of O(N * M) because each cell is visited once. The memory complexity is also O(N * M) due to the array and the recursive call stack.

8. Conclusion

In this lecture, we solved the problem of finding the maximum group size of connected 1s using depth-first search. DFS is a very useful algorithm for pathfinding problems and connected component identification, and it can be utilized in many algorithmic problems.

Next, we will discuss BFS and tackle various application problems. Thank you!