286. (Locked)Walls and Gates

Difficulty: Medium

Frequency: N/A

You are given a m x n 2D grid initialized with these three possible values.

  1. -1 – A wall or an obstacle.
  2. 0 – A gate.
  3. INF – Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:

INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

  3  -1   0   1
  2   2   1  -1
  1  -1   2  -1
  0  -1   3   4

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
private:
    struct Grid {
        int p, q, d;
        Grid(int p_, int q_, int d_) : p(p_), q(q_), d(d_) {}
    };
public:
    void wallsAndGates(vector<vector<int>>& rooms) {
        if (rooms.empty()) return;
        int m = rooms.size(), n = rooms[0].size();
        queue<Grid> myQ;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!rooms[i][j]) {
                    myQ.push(Grid(i - 1, j, 1));
                    myQ.push(Grid(i + 1, j, 1));
                    myQ.push(Grid(i, j - 1, 1));
                    myQ.push(Grid(i, j + 1, 1));
                    while (!myQ.empty()) {
                        Grid cur = myQ.front();
                        myQ.pop();
                        if (cur.p < 0 || cur.p >= m || cur.q < 0 || cur.q > n || rooms[cur.p][cur.q] < d) continue;
                        rooms[cur.p][cur.q] = d;
                        myQ.push(Grid(cur.p - 1, cur.q, d + 1));
                        myQ.push(Grid(cur.p + 1, cur.q, d + 1));
                        myQ.push(Grid(cur.p, cur.q - 1, d + 1));
                        myQ.push(Grid(cur.p, cur.q + 1, d + 1));                    
                    }
                }
            }
        }
    }
};

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

Things to learn:

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:

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:

107. Binary Tree Level Order Traversal II

Difficulty: Easy

Frequency: N/A

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

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<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> results;
        if (!root) return results;
        queue<TreeNode*> myQ;
        myQ.push(root);
        while (!myQ.empty()) {
            int q_size = myQ.size();
            vector<int> tmp;
            while (q_size) {
                TreeNode *cur = myQ.front();
                tmp.push_back(cur->val);
                myQ.pop();
                if (cur->left) myQ.push(cur->left);
                if (cur->right) myQ.push(cur->right);
                q_size--;
            }
            results.push_back(tmp);
        }
        return vector<vector<int>> (results.rbegin(), results.rend());
    }
};

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

Things to learn:

102. Binary Tree Level Order Traversal

Difficulty: Easy

Frequency: N/A

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> results;
        if (!root) return results;
        queue<TreeNode*> myQ;
        myQ.push(root);
        while (!myQ.empty()) {
            vector<int> tmp;
            int q_size = myQ.size();
            while (q_size) {
                TreeNode *cur = myQ.front();
                tmp.push_back(cur->val);
                myQ.pop();
                if (cur->left) myQ.push(cur->left);
                if (cur->right) myQ.push(cur->right);
                q_size--;
            }
            results.push_back(tmp);
        }
        return results;
    }
};

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

Things to learn: