Huahua’s Tech Road

花花酱 LeetCode 1172. Dinner Plate Stacks

By zxi on August 24, 2019

You have an infinite number of stacks arranged in a row and numbered (left to right) from 0, each of the stacks has the same maximum capacity.

Implement the DinnerPlates class:

DinnerPlates(int capacity) Initializes the object with the maximum capacity of the stacks.
void push(int val) pushes the given positive integer val into the leftmost stack with size less than capacity.
int pop() returns the value at the top of the rightmost non-empty stack and removes it from that stack, and returns -1 if all stacks are empty.
int popAtStack(int index) returns the value at the top of the stack with the given index and removes it from that stack, and returns -1 if the stack with that given index is empty.

Example:

Input: 
["DinnerPlates","push","push","push","push","push","popAtStack","push","push","popAtStack","popAtStack","pop","pop","pop","pop","pop"]
[[2],[1],[2],[3],[4],[5],[0],[20],[21],[0],[2],[],[],[],[],[]]
Output:

[null,null,null,null,null,null,2,null,null,20,21,5,4,3,1,-1]

Explanation: 
DinnerPlates D = DinnerPlates(2);  // Initialize with capacity = 2
D.push(1);
D.push(2);
D.push(3);
D.push(4);
D.push(5);         // The stacks are now:  2  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 2.  The stacks are now:     4
                                                       1  3  5
                                                       ﹈ ﹈ ﹈
D.push(20);        // The stacks are now: 20  4
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.push(21);        // The stacks are now: 20  4 21
                                           1  3  5
                                           ﹈ ﹈ ﹈
D.popAtStack(0);   // Returns 20.  The stacks are now:     4 21
                                                        1  3  5
                                                        ﹈ ﹈ ﹈
D.popAtStack(2);   // Returns 21.  The stacks are now:     4
                                                        1  3  5
                                                        ﹈ ﹈ ﹈ 
D.pop()            // Returns 5.  The stacks are now:      4
                                                        1  3 
                                                        ﹈ ﹈  
D.pop()            // Returns 4.  The stacks are now:   1  3 
                                                        ﹈ ﹈   
D.pop()            // Returns 3.  The stacks are now:   1 
                                                        ﹈   
D.pop()            // Returns 1.  There are no stacks.
D.pop()            // Returns -1.  There are still no stacks.

Constraints:

1 <= capacity <= 20000
1 <= val <= 20000
0 <= index <= 100000
At most 200000 calls will be made to push, pop, and popAtStack.

Solution: Array of stacks + TreeSet

Store all the stacks in an array, and store the indices of all free stacks in a tree set.
1. push(): find the first free stack and push onto it, if it becomes full, remove it from free set.
2. pop(): pop element from the last stack by calling popAtIndex(stacks.size()-1).
3. popAtIndex(): pop element from given index
3.1 add it to free set if it was full
3.2 remove it from free set if it becomes empty
3.2.1 remove it from stack array if it is the last stack

Time complexity:
Push: O(logn)
Pop: O(logn)
PopAtIndex: O(logn)

Space complexity: O(n)

C++

// Author: Huahua

class DinnerPlates {

public:

DinnerPlates(int capacity): cap_(capacity) {}

void push(int val) {

int index = aval_.empty() ? stacks_.size() : *begin(aval_);

if (index == stacks_.size()) stacks_.emplace_back();

stack<int>& s = stacks_[index];

s.push(val);

if (s.size() == cap_)

aval_.erase(index);

else if (s.size() == 1) // only insert for the first element

aval_.insert(index);

}

int pop() { return popAtStack(stacks_.size() - 1); }

int popAtStack(int index) {

if (index < 0 || index >= stacks_.size() || stacks_[index].empty()) return -1;

stack<int>& s = stacks_[index];

int val = s.top(); s.pop();

if (s.size() == cap_ - 1) aval_.insert(index);

// Amortized O(1)

auto it = prev(end(aval_));

while (stacks_.size() && stacks_.back().empty()) {

stacks_.pop_back();

aval_.erase(it--);

}

return val;

}

private:

int cap_;

set<int> aval_;

vector<stack<int>> stacks_;

};

花花酱 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;

}

};

Huahua's Tech Road

花花酱 LeetCode 1172. Dinner Plate Stacks

Solution: Array of stacks + TreeSet

C++

花花酱 LeetCode 92. Reverse Linked List II

C++

Python3

花花酱 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++