Huahua’s Tech Road

花花酱 LeetCode 1609. Even Odd Tree

By zxi on October 4, 2020

A binary tree is named Even-Odd if it meets the following conditions:

The root of the binary tree is at level index 0, its children are at level index 1, their children are at level index 2, etc.
For every even-indexed level, all nodes at the level have odd integer values in strictly increasing order (from left to right).
For every odd-indexed level, all nodes at the level have even integer values in strictly decreasing order (from left to right).

Given the root of a binary tree, return true if the binary tree is Even-Odd, otherwise return false.

Example 1:

Input: root = [1,10,4,3,null,7,9,12,8,6,null,null,2]
Output: true
Explanation: The node values on each level are:
Level 0: [1]
Level 1: [10,4]
Level 2: [3,7,9]
Level 3: [12,8,6,2]
Since levels 0 and 2 are all odd and increasing, and levels 1 and 3 are all even and decreasing, the tree is Even-Odd.

Example 2:

Input: root = [5,4,2,3,3,7]
Output: false
Explanation: The node values on each level are:
Level 0: [5]
Level 1: [4,2]
Level 2: [3,3,7]
Node values in the level 2 must be in strictly increasing order, so the tree is not Even-Odd.

Example 3:

Input: root = [5,9,1,3,5,7]
Output: false
Explanation: Node values in the level 1 should be even integers.

Example 4:

Input: root = [1]
Output: true

Example 5:

Input: root = [11,8,6,1,3,9,11,30,20,18,16,12,10,4,2,17]
Output: true

Constraints:

The number of nodes in the tree is in the range [1, 10⁵].
1 <= Node.val <= 10⁶

Solution 1: DFS

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

C++

class Solution {

public:

bool isEvenOddTree(TreeNode* root) {

vector<int> vals;

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

if (!root) return true;

if (vals.size() <= d)

vals.push_back(d % 2 == 0 ? -1 : INT_MAX);

int& val = vals[d];

if (d % 2 == 0)

if (root->val % 2 == 0 || root->val <= val) return false;

if (d % 2 == 1)

if (root->val % 2 == 1 || root->val >= val) return false;

val = root->val;

return dfs(root->left, d + 1) && dfs(root->right, d + 1);

};

return dfs(root, 0);

}

};

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

vals = {}

def dfs(root: TreeNode, d: int) -> bool:

if not root: return True

if d not in vals: vals[d] = 0 if d % 2 == 0 else 10**7

comp = int.__ge__ if d % 2 else int.__le__

if root.val % 2 == d % 2 or comp(root.val, vals[d]): return False

vals[d] = root.val

return dfs(root.left, d + 1) and dfs(root.right, d + 1)

return dfs(root, 0)

Solution 2: BFS

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

Python3

# Author: Huahua

class Solution:

def isEvenOddTree(self, root: TreeNode) -> bool:

q = collections.deque([root])

odd = 1

while q:

prev = 0 if odd else 10**7

for _ in range(len(q)):

root = q.popleft()

if not root: continue

comp = int.__le__ if odd else int.__ge__

if root.val % 2 != odd or comp(root.val, prev): return False

prev = root.val

q += (root.left, root.right)

odd = 1 - odd

return True

花花酱 LeetCode 1608. Special Array With X Elements Greater Than or Equal X

By zxi on October 4, 2020

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 1000

Solution 1: Brute Force

Try all possible x from 0 to n.

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

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

for (int x = 0; x <= nums.size(); ++x)

if (x == count_if(begin(nums), end(nums), [x](int num) {

return num >= x; }))

return x;

return -1;

}

};

Python3

# Author: Huahua

class Solution:

def specialArray(self, nums: List[int]) -> int:

for x in range(len(nums) + 1):

if x == sum([n >= x for n in nums]): return x

return -1

Solution 2: Counting Sort

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

f[i] := sum(nums >= i)

C++

// Author: Huahua

class Solution {

public:

int specialArray(vector<int>& nums) {

const int n = nums.size();

vector<int> f(n + 2);

for (int v : nums) ++f[min(v, n)];

for (int i = n; i >= 0; --i)

if ((f[i] += f[i + 1]) == i) return i;

return -1;

}

};

花花酱 LeetCode 1606. Find Servers That Handled Most Number of Requests

By zxi on October 3, 2020

You have k servers numbered from 0 to k-1 that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

The i^th (0-indexed) request arrives.
If all servers are busy, the request is dropped (not handled at all).
If the (i % k)^th server is available, assign the request to that server.
Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary). For example, if the i^th server is busy, try to assign the request to the (i+1)^th server, then the (i+2)^th server, and so on.

You are given a strictly increasing array arrival of positive integers, where arrival[i] represents the arrival time of the i^th request, and another array load, where load[i] represents the load of the i^th request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

Example 1:

Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3] 
Output: [1] 
Explanation:
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.

Example 2:

Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation:
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.

Example 3:

Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles a single request, so they are all considered the busiest.

Example 4:

Input: k = 3, arrival = [1,2,3,4,8,9,10], load = [5,2,10,3,1,2,2]
Output: [1]

Example 5:

Input: k = 1, arrival = [1], load = [1]
Output: [0]

Constraints:

1 <= k <= 10⁵
1 <= arrival.length, load.length <= 10⁵
arrival.length == load.length
1 <= arrival[i], load[i] <= 10⁹
arrival is strictly increasing.

Solution: Heap + TreeSet

Use a min heap to store the release time -> server.
Use a treeset to track the current available servers.
For reach request, check whether servers can be released at that time.

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {

priority_queue<pair<int, int>, vector<pair<int,int>>, greater<>> q; // {release_time, server}

set<int> servers;

vector<int> requests(k);

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

servers.insert(i);

for (int i = 0; i < arrival.size(); ++i) {

const int t = arrival[i];

const int l = load[i];

// Release servers. O(logk) per pop()

while (!q.empty() && q.top().first <= t) {

servers.insert(q.top().second);

q.pop();

}

// Drop the request.

if (servers.empty()) continue;

// Find first avaiable one O(logk)

auto it = servers.lower_bound(i % k);

if (it == servers.end()) it = begin(servers);

const int idx = *it;

++requests[idx];

servers.erase(it);

q.emplace(t + l, idx);

}

const int max_req = *max_element(begin(requests), end(requests));

vector<int> ans;

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

if (requests[i] == max_req) ans.push_back(i);

return ans;

}

};

花花酱 LeetCode 1605. Find Valid Matrix Given Row and Column Sums

By zxi on October 3, 2020

You are given two arrays rowSum and colSum of non-negative integers where rowSum[i] is the sum of the elements in the i^th row and colSum[j] is the sum of the elements of the j^th column of a 2D matrix. In other words, you do not know the elements of the matrix, but you do know the sums of each row and column.

Find any matrix of non-negative integers of size rowSum.length x colSum.length that satisfies the rowSum and colSum requirements.

Return a 2D array representing any matrix that fulfills the requirements. It’s guaranteed that at least one matrix that fulfills the requirements exists.

Example 1:

Input: rowSum = [3,8], colSum = [4,7]
Output: [[3,0],
         [1,7]]
Explanation:
0th row: 3 + 0 = 0 == rowSum[0]
1st row: 1 + 7 = 8 == rowSum[1]
0th column: 3 + 1 = 4 == colSum[0]
1st column: 0 + 7 = 7 == colSum[1]
The row and column sums match, and all matrix elements are non-negative.
Another possible matrix is: [[1,2],
                             [3,5]]

Example 2:

Input: rowSum = [5,7,10], colSum = [8,6,8]
Output: [[0,5,0],
         [6,1,0],
         [2,0,8]]

Example 3:

Input: rowSum = [14,9], colSum = [6,9,8]
Output: [[0,9,5],
         [6,0,3]]

Example 4:

Input: rowSum = [1,0], colSum = [1]
Output: [[1],
         [0]]

Example 5:

Input: rowSum = [0], colSum = [0]
Output: [[0]]

Constraints:

1 <= rowSum.length, colSum.length <= 500
0 <= rowSum[i], colSum[i] <= 10⁸
sum(rows) == sum(columns)

Solution: Greedy

Let a = min(row[i], col[j]), m[i][j] = a, row[i] -= a, col[j] -=a

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> restoreMatrix(vector<int>& rowSum, vector<int>& colSum) {

const int m = rowSum.size();

const int n = colSum.size();

vector<vector<int>> ans(m, vector<int>(n));

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

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

ans[i][j] = min(rowSum[i], colSum[j]);

rowSum[i] -= ans[i][j];

colSum[j] -= ans[i][j];

}

return ans;

}

};

花花酱 LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period

By zxi on October 3, 2020

Leetcode company workers use key-cards to unlock office doors. Each time a worker uses their key-card, the security system saves the worker’s name and the time when it was used. The system emits an alert if any worker uses the key-card three or more times in a one-hour period.

You are given a list of strings keyName and keyTime where [keyName[i], keyTime[i]] corresponds to a person’s name and the time when their key-card was used in a single day.

Access times are given in the 24-hour time format “HH:MM”, such as "23:51" and "09:49".

Return a list of unique worker names who received an alert for frequent keycard use. Sort the names in ascending order alphabetically.

Notice that "10:00" – "11:00" is considered to be within a one-hour period, while "23:51" – "00:10" is not considered to be within a one-hour period.

Example 1:

Input: keyName = ["daniel","daniel","daniel","luis","luis","luis","luis"], keyTime = ["10:00","10:40","11:00","09:00","11:00","13:00","15:00"]
Output: ["daniel"]
Explanation: "daniel" used the keycard 3 times in a one-hour period ("10:00","10:40", "11:00").

Example 2:

Input: keyName = ["alice","alice","alice","bob","bob","bob","bob"], keyTime = ["12:01","12:00","18:00","21:00","21:20","21:30","23:00"]
Output: ["bob"]
Explanation: "bob" used the keycard 3 times in a one-hour period ("21:00","21:20", "21:30").

Example 3:

Input: keyName = ["john","john","john"], keyTime = ["23:58","23:59","00:01"]
Output: []

Example 4:

Input: keyName = ["leslie","leslie","leslie","clare","clare","clare","clare"], keyTime = ["13:00","13:20","14:00","18:00","18:51","19:30","19:49"]
Output: ["clare","leslie"]

Constraints:

1 <= keyName.length, keyTime.length <= 10⁵
keyName.length == keyTime.length
keyTime are in the format “HH:MM”.
[keyName[i], keyTime[i]] is unique.
1 <= keyName[i].length <= 10
keyName[i] contains only lowercase English letters.

Solution: Hashtable + sorting

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

C++

class Solution {

public:

vector<string> alertNames(vector<string>& keyName, vector<string>& keyTime) {

unordered_map<string, vector<int>> t; // {name -> time}

for (size_t i = 0; i < keyName.size(); ++i) {

const int h = stoi(keyTime[i].substr(0, 2));

const int m = stoi(keyTime[i].substr(3));

t[keyName[i]].push_back(h * 60 + m);

}

vector<string> ans;

for (auto& [name, times] : t) {

sort(begin(times), end(times));

for (size_t i = 2; i < times.size(); ++i)

if (times[i] - times[i - 2] <= 60) {

ans.push_back(name);

break;

}

sort(begin(ans), end(ans));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1609. Even Odd Tree

Solution 1: DFS

C++

Python3

Solution 2: BFS

Python3

花花酱 LeetCode 1608. Special Array With X Elements Greater Than or Equal X

Solution 1: Brute Force

C++

Python3

Solution 2: Counting Sort

C++

花花酱 LeetCode 1606. Find Servers That Handled Most Number of Requests

Solution: Heap + TreeSet

C++

花花酱 LeetCode 1605. Find Valid Matrix Given Row and Column Sums

Solution: Greedy

C++

花花酱 LeetCode 1604. Alert Using Same Key-Card Three or More Times in a One Hour Period

Solution: Hashtable + sorting

C++