Posts tagged as “medium”

花花酱 LeetCode 1376. Time Needed to Inform All Employees

By zxi on March 8, 2020

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company has is the one with headID.

Each employee has one direct manager given in the manager array where manager[i] is the direct manager of the i-th employee, manager[headID] = -1. Also it’s guaranteed that the subordination relationships have a tree structure.

The head of the company wants to inform all the employees of the company of an urgent piece of news. He will inform his direct subordinates and they will inform their subordinates and so on until all employees know about the urgent news.

The i-th employee needs informTime[i] minutes to inform all of his direct subordinates (i.e After informTime[i] minutes, all his direct subordinates can start spreading the news).

Return the number of minutes needed to inform all the employees about the urgent news.

Example 1:

Input: n = 1, headID = 0, manager = [-1], informTime = [0]
Output: 0
Explanation: The head of the company is the only employee in the company.

Example 2:

Input: n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0]
Output: 1
Explanation: The head of the company with id = 2 is the direct manager of all the employees in the company and needs 1 minute to inform them all.
The tree structure of the employees in the company is shown.

Example 3:

Input: n = 7, headID = 6, manager = [1,2,3,4,5,6,-1], informTime = [0,6,5,4,3,2,1]
Output: 21
Explanation: The head has id = 6. He will inform employee with id = 5 in 1 minute.
The employee with id = 5 will inform the employee with id = 4 in 2 minutes.
The employee with id = 4 will inform the employee with id = 3 in 3 minutes.
The employee with id = 3 will inform the employee with id = 2 in 4 minutes.
The employee with id = 2 will inform the employee with id = 1 in 5 minutes.
The employee with id = 1 will inform the employee with id = 0 in 6 minutes.
Needed time = 1 + 2 + 3 + 4 + 5 + 6 = 21.

Example 4:

Input: n = 15, headID = 0, manager = [-1,0,0,1,1,2,2,3,3,4,4,5,5,6,6], informTime = [1,1,1,1,1,1,1,0,0,0,0,0,0,0,0]
Output: 3
Explanation: The first minute the head will inform employees 1 and 2.
The second minute they will inform employees 3, 4, 5 and 6.
The third minute they will inform the rest of employees.

Example 5:

Input: n = 4, headID = 2, manager = [3,3,-1,2], informTime = [0,0,162,914]
Output: 1076

Constraints:

1 <= n <= 10^5
0 <= headID < n
manager.length == n
0 <= manager[i] < n
manager[headID] == -1
informTime.length == n
0 <= informTime[i] <= 1000
informTime[i] == 0 if employee i has no subordinates.
It is guaranteed that all the employees can be informed.

Solution 1: Build the graph + DFS

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

C++

// Author: Huahua

class Solution {

public:

int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {

vector<vector<int>> es(n);

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

if (i != headID) es[manager[i]].push_back(i);

function<int(int)> dfs = [&](int cur) {

int t = 0;

for (int e : es[cur])

t = max(t, dfs(e));

return t + informTime[cur];

};

return dfs(headID);

}

};

Solution 2: Recursion with memoization

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

C++

// Author: Huahua

class Solution {

public:

int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {

vector<int> cache(n, -1);

function<int(int)> dfs = [&](int cur) {

if (cur == -1) return 0;

if (cache[cur] == -1)

cache[cur] = dfs(manager[cur]) + informTime[cur];

return cache[cur];

};

int ans = 0;

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

ans = max(ans, dfs(i));

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:

cache = [-1] * n

def dfs(cur):

if cur == -1: return 0

if cache[cur] == -1:

cache[cur] = dfs(manager[cur]) + informTime[cur]

return cache[cur]

return max([dfs(i) for i in range(n)])

花花酱 LeetCode 1372. Longest ZigZag Path in a Binary Tree

By zxi on March 8, 2020

Given a binary tree root, a ZigZag path for a binary tree is defined as follow:

Choose any node in the binary tree and a direction (right or left).
If the current direction is right then move to the right child of the current node otherwise move to the left child.
Change the direction from right to left or right to left.
Repeat the second and third step until you can’t move in the tree.

Zigzag length is defined as the number of nodes visited – 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

Example 1:

Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
Output: 3
Explanation: Longest ZigZag path in blue nodes (right -> left -> right).

Example 2:

Input: root = [1,1,1,null,1,null,null,1,1,null,1]
Output: 4
Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).

Example 3:

Input: root = [1]
Output: 0

Constraints:

Each tree has at most 50000 nodes..
Each node’s value is between [1, 100].

Solution: Recursion

For each node return
1. max ZigZag length if go left
2. max ZigZag length if go right
3. maz ZigZag length within the subtree

ZigZag(root):
ll, lr, lm = ZigZag(root.left)
rl, rr, rm = ZigZag(root.right)
return (lr+1, rl + 1, max(lr+1, rl+1, lm, rm))

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

C++

// Author: Huahua

class Solution {

public:

int longestZigZag(TreeNode* root) {

return get<2>(ZigZag(root));

}

// Returns {left, right, max}

tuple<int, int, int> ZigZag(TreeNode* root) {

if (!root) return {-1, -1, -1};

auto [ll, lr, lm] = ZigZag(root->left);

auto [rl, rr, rm] = ZigZag(root->right);

int l = lr + 1;

int r = rl + 1;

return {l, r, max({l, r, lm, rm})};

}

};

Python3

# Author: Huahua

class Solution:

def longestZigZag(self, root: TreeNode) -> int:

def ZigZag(node):

if not node: return (-1, -1, -1)

ll, lr, lm = ZigZag(node.left)

rl, rr, rm = ZigZag(node.right)

return (lr + 1, rl + 1, max(lr + 1, rl + 1, lm, rm))

return ZigZag(root)[2]

花花酱 LeetCode 1371. Find the Longest Substring Containing Vowels in Even Counts

By zxi on March 8, 2020

Given the string s, return the size of the longest substring containing each vowel an even number of times. That is, ‘a’, ‘e’, ‘i’, ‘o’, and ‘u’ must appear an even number of times.

Example 1:

Input: s = "eleetminicoworoep"
Output: 13
Explanation: The longest substring is "leetminicowor" which contains two each of the vowels: e, i and o and zero of the vowels: a and u.

Example 2:

Input: s = "leetcodeisgreat"
Output: 5
Explanation: The longest substring is "leetc" which contains two e's.

Example 3:

Input: s = "bcbcbc"
Output: 6
Explanation: In this case, the given string "bcbcbc" is the longest because all vowels: a, e, i, o and u appear zero times.

Constraints:

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

Solution: HashTable

Record the first index when a state occurs. index – last_index is the length of the all-even-vowel substring.

State: {a: odd|even, e: odd|even, …, u:odd|even}.

There are total 2^5 = 32 states that can be represented as a binary string.

whenever a vowel occurs, we flip the bit, e.g. odd->even, even->odd using XOR.

Time complexity: O(5*n)
Space complexity: O(32)

C++

// Author: Huahua

class Solution {

public:

int findTheLongestSubstring(string s) {

const char vowels[] = "aeiou";

vector<int> idx(1 << 5, INT_MAX); // state -> first_index

idx[0] = -1;

int state = 0;

int ans = 0;

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

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

if (s[i] == vowels[j]) state ^= 1 << j;

if (idx[state] == INT_MAX) idx[state] = i;

ans = max(ans, i - idx[state]);

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def findTheLongestSubstring(self, s: str) -> int:

idx = {0 : -1}

vowels = "aeiou"

state = 0

ans = 0

for i in range(len(s)):

j = vowels.find(s[i])

if j >= 0: state ^= 1 << j

if state not in idx:

idx[state] = i

ans = max(ans, i - idx[state])

return ans

花花酱 LeetCode 1366. Rank Teams by Votes

By zxi on March 2, 2020

In a special ranking system, each voter gives a rank from highest to lowest to all teams participated in the competition.

The ordering of teams is decided by who received the most position-one votes. If two or more teams tie in the first position, we consider the second position to resolve the conflict, if they tie again, we continue this process until the ties are resolved. If two or more teams are still tied after considering all positions, we rank them alphabetically based on their team letter.

Given an array of strings votes which is the votes of all voters in the ranking systems. Sort all teams according to the ranking system described above.

Return a string of all teams sorted by the ranking system.

Example 1:

Input: votes = ["ABC","ACB","ABC","ACB","ACB"]
Output: "ACB"
Explanation: Team A was ranked first place by 5 voters. No other team was voted as first place so team A is the first team.
Team B was ranked second by 2 voters and was ranked third by 3 voters.
Team C was ranked second by 3 voters and was ranked third by 2 voters.
As most of the voters ranked C second, team C is the second team and team B is the third.

Example 2:

Input: votes = ["WXYZ","XYZW"]
Output: "XWYZ"
Explanation: X is the winner due to tie-breaking rule. X has same votes as W for the first position but X has one vote as second position while W doesn't have any votes as second position.

Example 3:

Input: votes = ["ZMNAGUEDSJYLBOPHRQICWFXTVK"]
Output: "ZMNAGUEDSJYLBOPHRQICWFXTVK"
Explanation: Only one voter so his votes are used for the ranking.

Example 4:

Input: votes = ["BCA","CAB","CBA","ABC","ACB","BAC"]
Output: "ABC"
Explanation: 
Team A was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team B was ranked first by 2 voters, second by 2 voters and third by 2 voters.
Team C was ranked first by 2 voters, second by 2 voters and third by 2 voters.
There is a tie and we rank teams ascending by their IDs.

Example 5:

Input: votes = ["M","M","M","M"]
Output: "M"
Explanation: Only team M in the competition so it has the first rank.

Constraints:

1 <= votes.length <= 1000
1 <= votes[i].length <= 26
votes[i].length == votes[j].length for 0 <= i, j < votes.length.
votes[i][j] is an English upper-case letter.
All characters of votes[i] are unique.
All the characters that occur in votes[0] also occur in votes[j] where 1 <= j < votes.length.

Solution: Sort by rank

Time complexity: O(v*n + n^2*logn)
Space complexity: O(n*n)

C++

// Author: Huahua

class Solution {

public:

string rankTeams(vector<string>& votes) {

const int n = votes[0].length();

string ans(votes[0]);

vector<vector<int>> rank(26, vector<int>(n));

for (const auto& vote : votes)

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

++rank[vote[i] - 'A'][i];

sort(begin(ans), end(ans), [&](const char i, const char j) {

if (rank[i - 'A'] != rank[j - 'A']) return rank[i - 'A'] > rank[j - 'A'];

return i < j;

});

return ans;

}

};

花花酱 LeetCode 1367. Linked List in Binary Tree

By zxi on March 1, 2020

Given a binary tree root and a linked list with head as the first node.

Return True if all the elements in the linked list starting from the head correspond to some downward path connected in the binary tree otherwise return False.

In this context downward path means a path that starts at some node and goes downwards.

Example 1:

Input: head = [4,2,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true
Explanation: Nodes in blue form a subpath in the binary Tree.

Example 2:

Input: head = [1,4,2,6], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: true

Example 3:

Input: head = [1,4,2,6,8], root = [1,4,4,null,2,2,null,1,null,6,8,null,null,null,null,1,3]
Output: false
Explanation: There is no path in the binary tree that contains all the elements of the linked list from head.

Constraints:

1 <= node.val <= 100 for each node in the linked list and binary tree.
The given linked list will contain between 1 and 100 nodes.
The given binary tree will contain between 1 and 2500 nodes.

Solution: Recursion

We need two recursion functions: isSubPath / isPath, the later one does a strict match.

Time complexity: O(|L| * |T|)
Space complexity: O(|T|)

C++

class Solution {

public:

bool isSubPath(ListNode* head, TreeNode* root) {

if (!root) return false;

return isPath(head, root) || isSubPath(head, root->left) || isSubPath(head, root->right);

}

private:

bool isPath(ListNode* head, TreeNode* root) {

if (!head) return true;

if (!root) return false;

if (root->val != head->val) return false;

return isPath(head->next, root->left) || isPath(head->next, root->right);

}

};