Posts tagged as “hard”

花花酱 LeetCode 1178. Number of Valid Words for Each Puzzle

By zxi on September 1, 2019

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”; while invalid words are “beefed” (doesn’t include “a”) and “based” (includes “s” which isn’t in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].

Example :

Input: 
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
Output: [1,1,3,2,4,0]
Explanation:
1 valid word for "aboveyz" : "aaaa" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn’t contain repeated characters.

Solution: Subsets

Preprocessing:
Compress each word to a bit map, and compute the frequency of each bit map.
Since there are at most |words| bitmaps while its value ranging from 0 to 2^26, thus it’s better to use a hashtable instead of an array.

Query:
Use the same way to compress a puzzle into a bit map.
Try all subsets (at most 128) of the puzzle (the bit of the first character is be must), and check how many words match each subset.

words = [“aaaa”,”asas”,”able”,”ability”,”actt”,”actor”,”access”],
puzzle = “abslute”
bitmap(“aaaa”) = {0}
bitmap(“asas”) = {0, 18}
bitmap(“able”) = {0,1,4,11}
bitmap(“actt”) = {0, 2, 19}
bitmap(“actor”) = {0, 2, 14, 17, 19}
bitmap(“access”) = {0, 2, 4, 18}

bitmap(“abslute”) = {0, 1, 4, 11, 18, 19, 20}

Time complexity: O(sum(len(w_i)) + |puzzles|)
Space complexity: O(|words|)

C++

// Author: Huahua, 136 ms, 29.7 MB

class Solution {

public:

vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {

vector<int> ans;

unordered_map<int, int> freq;

for (const string& word : words) {

int mask = 0;

for (char c : word)

mask |= 1 << (c - 'a');

++freq[mask];

}

for (const string& p : puzzles) {

int mask = 0;

for (char c : p)

mask |= 1 << (c - 'a');

int first = p[0] - 'a';

int curr = mask;

int total = 0;

while (curr) {

if ((curr >> first) & 1) {

auto it = freq.find(curr);

if (it != freq.end()) total += it->second;

}

curr = (curr - 1) & mask;

}

ans.push_back(total);

}

return ans;

}

};

花花酱 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 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 1163. Last Substring in Lexicographical Order

By zxi on August 18, 2019

Given a string s, return the last substring of s in lexicographical order.

Example 1:

Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:

Input: "leetcode"
Output: "tcode"

Note:

1 <= s.length <= 10^5
s contains only lowercase English letters.

Key observation: The last substring must be a suffix of the original string, can’t a substring in the middle since we can always extend it.
e.g. leetcode -> tcode, can’t be “t”, “tc”, “tco”, “tcod”

Solution 1: Brute Force

Try all possible suffixes.
Time complexity: O(n^2)
Space complexity: O(1)

C++

// Author: Huahua, 452 ms, 12.8 MB

class Solution {

public:

string lastSubstring(string_view s) {

string_view ans;

for (int i = 0; i < s.length(); ++i)

if (s.substr(i) > ans) ans = s.substr(i);

return string(ans);

}

};

Solution 2: Keep max and compare with candidates

Find the first largest letter as a starting point, whenever there is a same letter, keep it as a candidate and compare with the current best. If the later is larger, take over the current best.

e.g. “acbacbc”

“c” > “a”, the first “c” becomes the best.
“c” = “c”, the second “c” becomes a candidate
starting compare best and candidate.
“cb” = “cb”
“cba” < “cbc”, cand_i is the new best.

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

C++

// Author: Huahua

class Solution {

public:

string lastSubstring(string s) {

int max_i = 0;

char max_c = 0;

int cand_i = 0;

int l = 0;

for (int i = 0; i < s.length(); ++i) {

if (s[i] > max_c) {

// Find a better starting point.

max_c = s[i];

max_i = i;

cand_i = -1;

l = 1;

} else if (cand_i != -1) {

// Has a candidate.

if (s[i] > s[max_i + l]) {

// The candidate is larger.

max_i = cand_i;

cand_i = -1;

} else if (s[i] == s[max_i + l]) {

// The candidate is the same as current best.

++l;

} else {

// The candidate is smaller, no longer needed.

cand_i = -1;

}

} else if (s[i] == max_c) {

// Find a new candidate, starting with length 1.

cand_i = i;

l = 1;

}

return s.substr(max_i);

}

};

花花酱 LeetCode 1157. Online Majority Element In Subarray

By zxi on August 10, 2019

Implementing the class MajorityChecker, which has the following API:

MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
int query(int left, int right, int threshold) has arguments such that:
- 0 <= left <= right < arr.length representing a subarray of arr;
- 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(...) returns the element in arr[left], arr[left+1], ..., arr[right]that occurs at least threshold times, or -1 if no such element exists.

Example:

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

Constraints:

1 <= arr.length <= 20000
1 <= arr[i] <= 20000
For each query, 0 <= left <= right < len(arr)
For each query, 2 * threshold > right - left + 1
The number of queries is at most 10000

Solution 0: Brute Force TLE

For each range, find the majority element in O(n) time / O(n) or O(1) space.

Solution 1: Cache the range result

Cache the result for each range: mode and frequency

Time complexity:
init: O(1)
query: O(|right – left|)
total queries: O(sum(right_i – left_i)), right_i, left_i are bounds of unique ranges.
Space complexity:
init: O(1)
query: O(20000)

C++

// Author: Huahua, 568ms, 39.6 MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {}

int query(int left, int right, int threshold) {

int key = left * 20000 + right;

if (!seen.count(key)) {

int c[20001] = {0};

int best = (right - left) / 2;

int best_num = -1;

for (int i = left; i <= right; ++i) {

if (++c[nums[i]] > best) {

best = c[nums[i]];

best_num = nums[i];

}

seen[key] = {best_num, best};

}

return seen[key].second >= threshold ? seen[key].first : -1;

}

private:

unordered_map<int, pair<int, int>> seen;

const vector<int>& nums;

};

Solution 2: HashTable + binary search

Preprocessing: use a hashtable to store the indices of each element. And sort by frequency of the element in descending order.
Query: iterator over (total_freq, num) pair, if freq >= threshold do a binary search to find the frequency of the given range for num in O(logn).

Time complexity:
Init: O(nlogn)
Query: worst case: O(nlogn), best case: O(logn)

C++

// Author: Huahua, 156 ms, 44.7MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {

const int max_n = *max_element(begin(nums), end(nums));

m = vector<vector<int>>(max_n + 1);

for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);

for (int n = 1; n <= max_n; ++n) {

if (m[n].size()) f.emplace_back(m[n].size(), n);

}

sort(rbegin(f), rend(f));

}

int query(int left, int right, int threshold) {

for (const auto& p : f) {

if (p.first < threshold) return -1;

int n = p.second;

const auto& idx = m[n];

int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);

if (count >= threshold) return n;

}

return -1;

}

private:

const vector<int>& nums;

vector<vector<int>> m; // num -> {indices}

vector<pair<int, int>> f; // {freq, num}

};

Solution 2+: Randomization

Randomly pick a num in range [left, right] and check its freq, try k (e.g. 30) times. If a majority element exists, you should find it with error rate 1/2^k.

Time complexity:
Init: O(n)
Query: O(30 * logn)
Space complexity: O(n)

C++

// Author: Huahua, 240ms, 45.6MB

class MajorityChecker {

public:

MajorityChecker(vector<int>& arr):nums(arr) {

for (int i = 0; i < nums.size(); ++i) m[nums[i]].push_back(i);

}

int query(int left, int right, int threshold) {

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

int n = nums[rand() % (right - left + 1) + left];

const auto& idx = m[n];

int count = upper_bound(begin(idx), end(idx), right) - lower_bound(begin(idx), end(idx), left);

if (count >= threshold) return n;

}

return -1;

}

private:

unordered_map<int, vector<int>> m; // num -> {indices}

const vector<int>& nums;

};