Posts tagged as “medium”

花花酱 LeetCode 116. Populating Next Right Pointers in Each Node

By zxi on August 22, 2019

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example:

Input: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

Output: {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

Note:

You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.

Solution: Recursion

Do a preorder traversal:
1. return if self is empty or leaf
2. self.left->next = self.right
3. if self.next: self.right.next = self.next.left

Time complexity: O(n)
Space complexity: O(log(n)) since it’s a perfect tree

C++

// Author: Huahua

class Solution {

public:

Node* connect(Node* root) {

if (!root || !root->left) return root;

root->left->next = root->right;

if (root->next)

root->right->next = root->next->left;

connect(root->left);

connect(root->right);

return root;

}

};

花花酱 LeetCode 103. Binary Tree Zigzag Level Order Traversal

By zxi on August 20, 2019

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its zigzag level order traversal as:

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

Solution 1: DFS

in order traversal using DFS and reverse the result of even levels.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, 0ms, 15.1 MB

class Solution {

public:

vector<vector<int> > zigzagLevelOrder(TreeNode *root) {

vector<vector<int>> ans;

function<void(TreeNode*, int)> dfs = [&](TreeNode* r, int d) {

if (!r) return;

while (ans.size() <= d) ans.push_back({});

ans[d].push_back(r->val);

dfs(r->right, d + 1);

dfs(r->left, d + 1);

};

dfs(root, 0);

for (int i = 0; i < ans.size(); i += 2)

reverse(begin(ans[i]), end(ans[i]));

return ans;

}

};

Solution 2: BFS

Expend/append in order for even levels and doing that in reverse order for odd levels.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

if (!root) return {};

vector<vector<int>> ans;

deque<TreeNode*> q;

q.push_back(root);

int d = 0;

while (q.size()) {

ans.push_back({});

auto cur = &ans.back();

deque<TreeNode*> next;

while (q.size()) {

if (d % 2) {

TreeNode* node = q.back();

q.pop_back();

cur->push_back(node->val);

if (node->right) next.push_front(node->right);

if (node->left) next.push_front(node->left);

} else {

TreeNode* node = q.front();

q.pop_front();

cur->push_back(node->val);

if (node->left) next.push_back(node->left);

if (node->right) next.push_back(node->right);

}

++d;

q.swap(next);

}

return ans;

}

};

花花酱 LeetCode 36. Valid Sudoku

By zxi on August 20, 2019

Determine if a 9×9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.

Solution: HashTable

Use hashtable to store the numbers of each row, column and each 3×3 box. If there number appears more than once then it’s an invalid Sudoku.

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isValidSudoku(vector<vector<char> > &board) {

for (int i = 0; i < 9;i++) {

set<char> r, c;

for (int j = 0; j < 9; j++) {

if (board[i][j] != '.' && !r.insert(board[i][j]).second)

return false;

if (board[j][i] != '.' && !c.insert(board[j][i]).second)

return false;

}

for (int p = 0; p < 3; p++)

for (int q = 0; q < 3; q++) {

set<char> b;

for (int i = 0; i < 3; i++)

for (int j = 0; j < 3; j++) {

int x = p * 3 + i;

int y = q * 3 + j;

if (board[y][x] != '.' && !b.insert(board[y][x]).second)

return false;

}

return true;

}

};

Follow up:

https://zxi.mytechroad.com/blog/searching/leetcode-37-sudoku-solver/

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

By zxi on August 17, 2019

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level X such that the sum of all the values of nodes at level X is maximal.

Example 1:

Input: [1,7,0,7,-8,null,null]
Output: 2
Explanation: 
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Note:

The number of nodes in the given tree is between 1 and 10^4.
-10^5 <= node.val <= 10^5

Solution: HashTable

Use a hash table / array to store the level sum.

Time complexity: O(n)
Space complexity: O(h)

C++

// Author: Huahua, 232 ms, 70.2 ms

class Solution {

public:

int maxLevelSum(TreeNode* root) {

vector<int> sums;

function<void(TreeNode*, int)> preorder = [&](TreeNode* n, int d) {

if (!n) return;

while (sums.size() <= d) sums.push_back(0);

sums[d] += n->val;

preorder(n->left, d + 1);

preorder(n->right, d + 1);

};

preorder(root, 1);

int max_sum = sums[1];

int ans = 1;

for (int i = 2; i < sums.size(); ++i)

if (sums[i] > max_sum) {

max_sum = sums[i];

ans = i;

}

return ans;

}

};

花花酱 LeetCode 1162. As Far from Land as Possible

By zxi on August 17, 2019

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1)is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

Note:

1 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1

Solution: BFS

Put all land cells into a queue as source nodes and BFS for water cells, the last expanded one will be the farthest.

Time compleixty: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua, 48 ms, 13.4 MB

class Solution {

public:

int maxDistance(vector<vector<int>>& grid) {

const int n = grid.size();

const int m = grid[0].size();

int ans = -1;

queue<int> q; // y*100 + x

for (int i = 0; i < n; ++i)

for (int j = 0; j < m; ++j)

if (grid[i][j] == 1) q.push(i * 100 + j);

vector<int> dirs{0, -1, 0, 1, 0};

int steps = 0;

while (q.size()) {

int size = q.size();

while (size--) {

auto p = q.front(); q.pop();

int x = p % 100;

int y = p / 100;

if (grid[y][x] == 2)

ans = max(ans, steps);

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || tx >= m || ty < 0 || ty >= n || grid[ty][tx] != 0) continue;

grid[ty][tx] = 2;

q.push(ty * 100 + tx);

}

++steps;

}

return ans;

}

};

Posts tagged as “medium”

花花酱 LeetCode 116. Populating Next Right Pointers in Each Node

Solution: Recursion

C++

花花酱 LeetCode 103. Binary Tree Zigzag Level Order Traversal

Solution 1: DFS

C++

Solution 2: BFS

C++

Related Problems

花花酱 LeetCode 36. Valid Sudoku

Solution: HashTable

C++

Follow up:

花花酱 LeetCode 1161. Maximum Level Sum of a Binary Tree

Solution: HashTable

C++

花花酱 LeetCode 1162. As Far from Land as Possible

Solution: BFS

C++