Huahua's Tech Road

花花酱 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 212. Word Search II

By zxi on August 20, 2019

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example:

Input: 
board = [
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

Note:

All inputs are consist of lowercase letters a-z.
The values of words are distinct.

Solution 1: DFS

Time complexity: O(sum(m*n*4^l))
Space complexity: O(l)

C++

// Author: Huahua, 708 ms, 15.3 MB

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

unordered_set<string> unique_words(words.begin(), words.end());

vector<string> ans;

for (const string& word : unique_words)

if (exist(board, word))

ans.push_back(word);

return ans;

}

private:

int w;

int h;

bool exist(vector<vector<char>> &board, string word) {

if (board.size() == 0) return false;

h = board.size();

w = board[0].size();

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

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

if (search(board, word, 0, i, j)) return true;

return false;

}

bool search(vector<vector<char>> &board,

const string& word, int d, int x, int y) {

if (x < 0 || x == w || y < 0 || y == h || word[d] != board[y][x])

return false;

// Found the last char of the word

if (d == word.length() - 1)

return true;

char cur = board[y][x];

board[y][x] = '#';

bool found = search(board, word, d + 1, x + 1, y)

|| search(board, word, d + 1, x - 1, y)

|| search(board, word, d + 1, x, y + 1)

|| search(board, word, d + 1, x, y - 1);

board[y][x] = cur;

return found;

}

};

Solution 2: Trie

Store all the words into a trie, search the board using DFS, paths must be in the trie otherwise there is no need to explore.

Time complexity: O(sum(l) + 4^max(l))
space complexity: O(sum(l) + l)

C++

// Author: Huahua, 64 ms, 35.6 MB

class TrieNode {

public:

vector<TrieNode*> nodes;

const string* word;

TrieNode(): nodes(26), word(nullptr) {}

~TrieNode() {

for (auto node : nodes) delete node;

}

};

class Solution {

public:

vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {

TrieNode root;

// Add all the words into Trie.

for (const string& word : words) {

TrieNode* cur = &root;

for (char c : word) {

auto& next = cur->nodes[c - 'a'];

if (!next) next = new TrieNode();

cur = next;

}

cur->word = &word;

}

const int n = board.size();

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

vector<string> ans;

function<void(int, int, TrieNode*)> walk = [&](int x, int y, TrieNode* node) {

if (x < 0 || x == m || y < 0 || y == n || board[y][x] == '#')

return;

const char cur = board[y][x];

TrieNode* next_node = node->nodes[cur - 'a'];

// Pruning, only expend paths that are in the trie.

if (!next_node) return;

if (next_node->word) {

ans.push_back(*next_node->word);

next_node->word = nullptr;

}

board[y][x] = '#';

walk(x + 1, y, next_node);

walk(x - 1, y, next_node);

walk(x, y + 1, next_node);

walk(x, y - 1, next_node);

board[y][x] = cur;

};

// Try all possible pathes.

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

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

walk(j, i, &root);

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 34. Find First and Last Position of Element in Sorted Array

By zxi on August 20, 2019

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Solution: Binary Search

Basically this problem asks you to implement lower_bound and upper_bound using binary search.

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

C++

// Author: Huahua

class Solution {

public:

vector<int> searchRange(vector<int>& nums, int target) {

return {firstPos(nums, target), lastPos(nums, target)};

}

private:

int firstPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] >= target) {

r = m;

} else {

l = m + 1;

}

if (l == nums.size() || nums[l] != target) return -1;

return l;

}

int lastPos(const vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

int m = l + (r - l) / 2;

if (nums[m] > target) {

r = m;

} else {

l = m + 1;

}

// l points to the first element this is greater than target.

--l;

if (l < 0 || nums[l] != target) return -1;

return l;

}

};

Huahua's Tech Road

花花酱 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 212. Word Search II

Solution 1: DFS

C++

Solution 2: Trie

C++

花花酱 LeetCode 36. Valid Sudoku

Solution: HashTable

C++

Follow up:

花花酱 LeetCode 34. Find First and Last Position of Element in Sorted Array

Solution: Binary Search

C++