Leetcode.com problem 695: "Maximum Area of Island"

James S. Plank

Fri Jul 15 01:19:55 PM EDT 2022

Problem Statement.
Success Rate (as of July, 2022): 71.3%
This is a medium problem.
The first example
tests.sh: A testing script
answers.txt: Correct output to the testing script
The Problems directory has example input files that you can use for testing.
A skeleton with my main() that you can use to test your answer.
My recursive solution
My non-recursive solution

This is a standard, simple graph problem from CS302: Of all the connected components in the graph, return the size of the largest. You can determine connected components with DFS, so go ahead and define a recursive DFS method, and implement it.

The DFS is so simple, that to challenge yourself, you can try to implement it without recursion. You can do that by maintaining a stack, and where you would normally make a recursive call, you push the node onto the stack. Your main loop maintains a current row, a current column, and the stack. Inside the main loop, you do the following:

If the stack is not empty, pop the node off the top and process it.
Otherwise, check g[row][column]. If it equals 1, push the node (row/colums) onto the stack. If it equals 0, do nothing. Regardless, move onto the next row/column before returning to the top of the loop.
When you process a node off the stack, check to see if it equals 1. If it does, add one to the component size, set it to 0, and push neighboring elements onto the stack. It it doesn't equal 1, ignore it. Regardless, when you pop the last node off the stack, that marks the end of a component, so you can now keep track of the maximum component size.

I have my commented non-recursive code below. Instead of a single stack that holds a "node", I have two stacks -- one for the row number of the node and one for the column number.

/*
Runtime: 26 ms, faster than 68.48% of C++ online submissions for Max Area of Island.
Memory Usage: 23.2 MB, less than 67.07% of C++ online submissions for Max Area of Island.
*/

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int> >& grid);
};

int Solution::maxAreaOfIsland(vector<vector<int> >& g)
{
  int i, j, cs;
  vector <int> row_stack, col_stack;
  int r, c;
  int csize;
  int max;

  csize = 0;
  max = 0;
  i = 0;      /* i is the current row number that we're looking at. */
  j = 0;      /* And j is the current_column number */

  /* Iterate until the stacks are empty and i has exceeded the number of rows. */
  while (i < g.size() || !row_stack.empty()) {

    /* If the stack is empty, check to see if g[i][j] is one.
       If so, push i and j onto the stacks.  Regardless, update j
       (and maybe i) to look at the next element of g. */

    if (row_stack.empty()) {
      if (g[i][j] == 1) {
        row_stack.push_back(i);
        col_stack.push_back(j);
      } 
      j++;
      if (j == g[0].size()) { j = 0; i++; }

    /* If the stack isn't empty, then pop the top node's row and column
       numbers into r and c. */

    } else {
      r = row_stack.back();
      c = col_stack.back();
      row_stack.pop_back();
      col_stack.pop_back();

      /* If g[r][c] is 1, then increment the component size, set
         g[r][c] to zero, and then check the neighboring elements.
         If a neighbors entry in g is one, then push it onto the stack. */

      if (g[r][c] == 1) {
        csize++;
        g[r][c] = 0;
        if (r > 0 && g[r-1][c] == 1) {
          row_stack.push_back(r-1);
          col_stack.push_back(c);
        }
        if (r+1 < g.size() && g[r+1][c] == 1) {
          row_stack.push_back(r+1);
          col_stack.push_back(c);
        }
        if (c > 0 && g[r][c-1] == 1) {
          row_stack.push_back(r);
          col_stack.push_back(c-1);
        }
        if (c+1 < g[0].size() && g[r][c+1] == 1) {
          row_stack.push_back(r);
          col_stack.push_back(c+1);
        }
      }

      /* Finally, if the pops have made the stacks empty, then
         you are done with that component.  Maintain the max
         component size, and clear csize back to zero. */

      if (row_stack.size() == 0) {
        if (csize > max) max = csize;
        csize = 0;
      }
    }
  }
  return max;
}

int main()
{
  int r, c, n;
  int i, j;
  vector < vector < int > > g;
  Solution s;

  cin >> r >> c;

  g.resize(r);
  for (i = 0; i < r; i++) {
    for (j = 0; j < c; j++) {
      cin >> n;
      g[i].push_back(n);
    }
  }

  n = s.maxAreaOfIsland(g);
  cout << n << endl;
  return 0;
}