Huahua’s Tech Road

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

};

花花酱 LeetCode 1110. Delete Nodes And Return Forest

By zxi on August 8, 2019

Given the root of a binary tree, each node in the tree has a distinct value.

After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).

Return the roots of the trees in the remaining forest. You may return the result in any order.

Example 1:

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

Constraints:

The number of nodes in the given tree is at most 1000.
Each node has a distinct value between 1 and 1000.
to_delete.length <= 1000
to_delete contains distinct values between 1 and 1000.

Solution: Recursion / Post-order traversal

Recursively delete nodes on left subtree and right subtree and return the trimmed tree.
if the current node needs to be deleted, then its non-null children will be added to output array.

Time complexity: O(n)
Space complexity: O(|d| + h)

C++

// Author: Huahua

class Solution {

public:

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {

vector<TreeNode*> ans;

unordered_set<int> s{begin(to_delete), end(to_delete)};

function<TreeNode*(TreeNode*)> del = [&](TreeNode* n) -> TreeNode* {

if (!n) return nullptr;

if (n->left) n->left = del(n->left);

if (n->right) n->right = del(n->right);

if (!s.count(n->val)) return n;

if (n->left) ans.push_back(n->left);

if (n->right) ans.push_back(n->right);

return nullptr;

};

TreeNode* r = del(root);

if (r) ans.push_back(r);

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:

ans = []

ds = set(to_delete)

def process(n):

if not n: return None

n.left, n.right = process(n.left), process(n.right)

if n.val not in ds: return n

if n.left: ans.append(n.left)

if n.right: ans.append(n.right)

return None

root = process(root)

if root: ans.append(root)

return ans

花花酱 LeetCode 1147. Longest Chunked Palindrome Decomposition

By zxi on August 4, 2019

Return the largest possible k such that there exists a_1, a_2, ..., a_k such that:

Each a_i is a non-empty string;
Their concatenation a_1 + a_2 + ... + a_k is equal to text;
For all 1 <= i <= k, a_i = a_{k+1 - i}.

Example 1:

Input: text = "ghiabcdefhelloadamhelloabcdefghi"
Output: 7
Explanation: We can split the string on "(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)".

Example 2:

Input: text = "merchant"
Output: 1
Explanation: We can split the string on "(merchant)".

Example 3:

Input: text = "antaprezatepzapreanta"
Output: 11
Explanation: We can split the string on "(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)".

Example 4:

Input: text = "aaa"
Output: 3
Explanation: We can split the string on "(a)(a)(a)".

Solution: Greedy

Break the string when the shortest palindrome is found.
prefer to use string_view

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

C++

// Author: Huahua, 0 ms, 8.7 ms

class Solution {

public:

int longestDecomposition(string_view text) {

const int n = text.length();

if (n == 0) return 0;

for (int l = 1; l <= n / 2; ++l) {

if (text.substr(0, l) == text.substr(n - l))

return 2 + longestDecomposition(text.substr(l, n - 2 * l));

}

return 1;

}

};

花花酱 LeetCode 1146. Snapshot Array

By zxi on August 4, 2019

Implement a SnapshotArray that supports the following interface:

SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
void set(index, val) sets the element at the given index to be equal to val.
int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id

Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

Constraints:

1 <= length <= 50000
At most 50000 calls will be made to set, snap, and get.
0 <= index < length
0 <= snap_id < (the total number of times we call snap())
0 <= val <= 10^9

Solution: map + upper_bound

Use a vector to store maps, one map per element.
The map stores {snap_id -> val}, use upper_bound to find the first version > snap_id and use previous version’s value.

Time complexity:
Set: O(log|snap_id|)
Get: O(log|snap_id|)
Snap: O(1)
Space complexity: O(length + set_calls)

C++

// Author: Huahua

class SnapshotArray {

public:

SnapshotArray(int length): id_(0), vals_(length) {}

void set(int index, int val) {

vals_[index][id_] = val;

}

int snap() { return id_++; }

int get(int index, int snap_id) const {

auto it = vals_[index].upper_bound(snap_id);

if (it == begin(vals_[index])) return 0;

return prev(it)->second;

}

private:

int id_;

vector<map<int, int>> vals_;

};

花花酱 LeetCode 1145. Binary Tree Coloring Game

By zxi on August 4, 2019

Two players play a turn based game on a binary tree. We are given the root of this binary tree, and the number of nodes n in the tree. n is odd, and each node has a distinct value from 1 to n.

Initially, the first player names a value x with 1 <= x <= n, and the second player names a value y with 1 <= y <= n and y != x. The first player colors the node with value x red, and the second player colors the node with value yblue.

Then, the players take turns starting with the first player. In each turn, that player chooses a node of their color (red if player 1, blue if player 2) and colors an uncolored neighbor of the chosen node (either the left child, right child, or parent of the chosen node.)

If (and only if) a player cannot choose such a node in this way, they must pass their turn. If both players pass their turn, the game ends, and the winner is the player that colored more nodes.

You are the second player. If it is possible to choose such a y to ensure you win the game, return true. If it is not possible, return false.

Example 1:

Input: root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
Output: true
Explanation: The second player can choose the node with value 2.

Constraints:

root is the root of a binary tree with n nodes and distinct node values from 1 to n.
n is odd.
1 <= x <= n <= 100

Solution: Count size of red’s subtrees

There are two situations that blue can win.
1. one of the red’s subtree has more than n>>1 nodes. Blue colorize the root of the larger subtree.
2. red and its children has size less or equal to n>>1. Blue colorize red’s parent.

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

C++

// Author: Huahua

class Solution {

public:

bool btreeGameWinningMove(TreeNode* root, int n, int x) {

int red_left;

int red_right;

function<int(TreeNode*)> count = [&](TreeNode* node){

if (!node) return 0;

int l = count(node->left);

int r = count(node->right);

if (root->val == x) {

red_left = l;

red_right = r;

}

return 1 + l + r;

};

count(root);

// Color red's parent.

if (1 + red_left + red_right <= n / 2) return true;

// Color the child that has the larger subtree.

return max(red_left, red_right) > n / 2;

}

};

Huahua's Tech Road

花花酱 LeetCode 1157. Online Majority Element In Subarray

Solution 0: Brute Force TLE

Solution 1: Cache the range result

C++

Solution 2: HashTable + binary search

C++

Solution 2+: Randomization

C++

花花酱 LeetCode 1110. Delete Nodes And Return Forest

Solution: Recursion / Post-order traversal

C++

Python3

花花酱 LeetCode 1147. Longest Chunked Palindrome Decomposition

Solution: Greedy

C++

花花酱 LeetCode 1146. Snapshot Array

Solution: map + upper_bound

C++

花花酱 LeetCode 1145. Binary Tree Coloring Game

C++