130. Surrounded Regions

Difficulty: Medium

Frequency: N/A

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    void solve(vector<vector<char>>& board) {
        int width = board.size();
        if (!width) return;
        int length = board[0].size();
        if (!length) return;
        for (int i = 0; i < width; i++) {
            if (board[i][0] == 'O') flip(board, i, 0);
            if (board[i][length - 1] == 'O') flip(board, i, length - 1);
        }
        for (int j = 1; j < length - 1; j++) {
            if (board[0][j] == 'O') flip(board, 0, j);
            if (board[width - 1][j] == 'O') flip(board, width - 1, j);
        }
        for (int i = 0; i < width; i++) {
            for (int j = 0; j < length; j++) {
                if (board[i][j] == 'T') board[i][j] = 'O';
                else if (board[i][j] == 'O') board[i][j] = 'X';
            }
        }
    }
    void flip(vector<vector<char>>& board, int i, int j) {
        int width = board.size();
        int length = board[0].size();
        queue<pair<int, int>> myQ;
        myQ.push(make_pair(i, j));
        board[i][j] = 'T';
        while (!myQ.empty()) {
            pair<int, int> cur = myQ.front();
            myQ.pop();
            int p = cur.first, q = cur.second;
            if (p > 0 && board[p - 1][q] == 'O') {
                myQ.push(make_pair(p - 1, q));
                board[p - 1][q] = 'T';
            }
            if (p < width - 1 && board[p + 1][q] == 'O') {
                myQ.push(make_pair(p + 1, q));
                board[p + 1][q] = 'T';
            }
            if (q > 0 && board[p][q - 1] == 'O') {
                myQ.push(make_pair(p, q - 1));
                board[p][q - 1] = 'T';
            }
            if (q < length - 1 && board[p][q + 1] == 'O') {
                myQ.push(make_pair(p, q + 1));
                board[p][q + 1] = 'T';
            }
        }
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

200. Number of Islands

Difficulty: Medium

Frequency: N/A

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3


 

My solution:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.size() == 0 || grid[0].size() == 0) return 0;
        int result = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    result++;
                    DFS(grid, i, j);
                }
            }
        }
        return result;
    }
    void DFS(vector<vector<char>>& grid, int i, int j) {
        grid[i][j] = '0';
        if (i > 0 && grid[i - 1][j] == '1') DFS(grid, i - 1, j);
        if (i < grid.size() - 1 && grid[i + 1][j] == '1') DFS(grid, i + 1, j);
        if (j > 0 && grid[i][j - 1] == '1') DFS(grid, i, j - 1);
        if (j < grid[0].size() - 1 && grid[i][j + 1] == '1') DFS(grid, i, j+ 1);
    }
};

Things to learn:

199. Binary Tree Right Side View

Difficulty: Medium

Frequency: N/A

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> results;
        if (!root) return results;
        queue<TreeNode*> myQ;
        myQ.push(root);
        while (!myQ.empty()) {
            int q_size = myQ.size();
            while (q_size) {
                TreeNode *cur = myQ.front();
                if (q_size == 1) results.push_back(cur->val);
                myQ.pop();
                if (cur->left) myQ.push(cur->left);
                if (cur->right) myQ.push(cur->right);
                q_size--;
            }
        }
        return results;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn: