695. Max Area of Island

📝 Problem Details

• Title: 695. Max Area of Island
• Link: https://leetcode.com/problems/max-area-of-island/
• Difficulty: Medium
• Tags/Categories: Graphs BFS

input m x n binary matrix (0 or 1) grid island: a group of 1s directionally connected (horizontal and vertical) assume all four edges of the grid are surrounded by water (?) area of an island: number of cells with the value 1 in the island return max area of an island in grid

💡 Explanation of Solution

same intution and approach as problem 200. Number of Islands, except instaed of counting the number of islands, we track a maxSize variable and count the size of the current island inside the BFS traversal

⌛ Complexity Analysis

Time Complexity: O(n*m)
Space Complexity: O(maxIslandSize) for use of queue for BFS

💻 Implementation of Solution

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if (grid.empty()) return 0;
 
        int rows = grid.size();
        int cols = grid[0].size();
        int maxArea = 0;
 
        vector<pair<int, int>> directions = {
            {0, 1},   // right
            {0, -1},  // left
            {1, 0},   // down
            {-1, 0}   // up
        };
 
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 1) {
                    int count = 0;  // Initialize island size
 
                    queue<pair<int, int>> q;
                    q.push({r, c});
                    grid[r][c] = 0; // Mark as visited
 
                    while (!q.empty()) {
                        auto [row, col] = q.front();
                        q.pop();
                        count++;  // Increment island size
 
                        for (auto [directionRow, directionCol] : directions) {
                            int newRow = row + directionRow;
                            int newCol = col + directionCol;
                            if (newRow >= 0 && newRow < rows  // In bounds?
                             && newCol >= 0 && newCol < cols  // In bounds?
                             && grid[newRow][newCol] == 1) {  // Land?
                                q.push({newRow, newCol});
                                grid[newRow][newCol] = 0;  // Mark visited
                            }
                        }
                    }
                    maxArea = max(maxArea, count);
                }
            }
        }
        return maxArea;
    }
};