2023-10-17
1361. Validate Binary Tree Nodes

Topic: Tree, Depth-First Search, Breadth-First Search, Union Find, Graph, Binary Tree
Difficulty: Medium

Problem:
You have n binary tree nodes numbered from 0 to n - 1 where node i has two children leftChild[i] and rightChild[i], return true if and only if all the given nodes form exactly one valid binary tree.

If node i has no left child then leftChild[i] will equal -1, similarly for the right child.

Note that the nodes have no values and that we only use the node numbers in this problem.

Example 1:

Image: https://assets.leetcode.com/uploads/2019/08/23/1503_ex1.png

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

Example 2:

Image: https://assets.leetcode.com/uploads/2019/08/23/1503_ex2.png

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
Output: false

Example 3:

Image: https://assets.leetcode.com/uploads/2019/08/23/1503_ex3.png

Input: n = 2, leftChild = [1,0], rightChild = [-1,-1]
Output: false

Constraints:

• n == leftChild.length == rightChild.length
• 1 <= n <= 10^4
• -1 <= leftChild[i], rightChild[i] <= n - 1

2023-10-18
2050. Parallel Courses III

Topic: Array, Dynamic Programming, Graph, Topological Sort
Difficulty: Hard

Problem:
You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given a 2D integer array relations where relations[j] = [prevCourse_j, nextCourse_j] denotes that course prevCourse_j has to be completed before course nextCourse_j (prerequisite relationship). Furthermore, you are given a 0-indexed integer array time where time[i] denotes how many months it takes to complete the (i+1)^th course.

You must find the minimum number of months needed to complete all the courses following these rules:

• You may start taking a course at any time if the prerequisites are met.
• Any number of courses can be taken at the same time.

Return the minimum number of months needed to complete all the courses.

Note: The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

Example 1:

Image: https://assets.leetcode.com/uploads/2021/10/07/ex1.png

Input: n = 3, relations = [[1,3],[2,3]], time = [3,2,5]
Output: 8
Explanation: The figure above represents the given graph and the time required to complete each course. 
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

Example 2:

Image: https://assets.leetcode.com/uploads/2021/10/07/ex2.png

Input: n = 5, relations = [[1,5],[2,5],[3,5],[3,4],[4,5]], time = [1,2,3,4,5]
Output: 12
Explanation: The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

Constraints:

• 1 <= n <= 5 * 10^4
• 0 <= relations.length <= min(n * (n - 1) / 2, 5 * 10^4)
• relations[j].length == 2
• 1 <= prevCourse_j, nextCourse_j <= n
• prevCourse_j != nextCourse_j
• All the pairs [prevCourse_j, nextCourse_j] are unique.
• time.length == n
• 1 <= time[i] <= 10^4
• The given graph is a directed acyclic graph.

2023-10-19
844. Backspace String Compare

Topic: Two Pointers, String, Stack, Simulation
Difficulty: Easy

Problem:
Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

2023-10-20
341. Flatten Nested List Iterator

Topic: Stack, Tree, Depth-First Search, Design, Queue, Iterator
Difficulty: Medium

Problem:
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints:

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [-10^6, 10^6].

2023-10-21
1425. Constrained Subsequence Sum

Topic: Array, Dynamic Programming, Queue, Sliding Window, Heap (Priority Queue), Monotonic Queue
Difficulty: Hard

Problem:
Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.

A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.

Example 1:

Input: nums = [10,2,-10,5,20], k = 2
Output: 37
Explanation: The subsequence is [10, 2, 5, 20].

Example 2:

Input: nums = [-1,-2,-3], k = 1
Output: -1
Explanation: The subsequence must be non-empty, so we choose the largest number.

Example 3:

Input: nums = [10,-2,-10,-5,20], k = 2
Output: 23
Explanation: The subsequence is [10, -2, -5, 20].

Constraints:

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

2023-10-22
1793. Maximum Score of a Good Subarray

Topic: Array, Two Pointers, Binary Search, Stack, Monotonic Stack
Difficulty: Hard

Problem:
You are given an array of integers nums (0-indexed) and an integer k.

The score of a subarray (i, j) is defined as min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1). A good subarray is a subarray where i <= k <= j.

Return the maximum possible score of a good subarray.

Example 1:

Input: nums = [1,4,3,7,4,5], k = 3
Output: 15
Explanation: The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15.

Example 2:

Input: nums = [5,5,4,5,4,1,1,1], k = 0
Output: 20
Explanation: The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 2 * 10^4
• 0 <= k < nums.length

2023-10-23
342. Power of Four

Topic: Math, Bit Manipulation, Recursion
Difficulty: Easy

Problem:
Given an integer n, return true if it is a power of four. Otherwise, return false.

An integer n is a power of four, if there exists an integer x such that n == 4^x.

Example 1:

Input: n = 16
Output: true

Example 2:

Input: n = 5
Output: false

Example 3:

Input: n = 1
Output: true

Constraints:

• -2^31 <= n <= 2^31 - 1

Follow up: Could you solve it without loops/recursion?

2023-10-24
515. Find Largest Value in Each Tree Row

Topic: Tree, Depth-First Search, Breadth-First Search, Binary Tree
Difficulty: Medium

Problem:
Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed).

Example 1:

Image: https://assets.leetcode.com/uploads/2020/08/21/largest_e1.jpg

Input: root = [1,3,2,5,3,null,9]
Output: [1,3,9]

Example 2:

Input: root = [1,2,3]
Output: [1,3]

Constraints:

• The number of nodes in the tree will be in the range [0, 10^4].
• -2^31 <= Node.val <= 2^31 - 1

2023-10-25
779. K-th Symbol in Grammar

Topic: Math, Bit Manipulation, Recursion
Difficulty: Medium

Problem:
We build a table of n rows (1-indexed). We start by writing 0 in the 1^st row. Now in every subsequent row, we look at the previous row and replace each occurrence of 0 with 01, and each occurrence of 1 with 10.

• For example, for n = 3, the 1^st row is 0, the 2^nd row is 01, and the 3^rd row is 0110.

Given two integer n and k, return the k^th (1-indexed) symbol in the n^th row of a table of n rows.

Example 1:

Input: n = 1, k = 1
Output: 0
Explanation: row 1: 0

Example 2:

Input: n = 2, k = 1
Output: 0
Explanation: 
row 1: 0
row 2: 01

Example 3:

Input: n = 2, k = 2
Output: 1
Explanation: 
row 1: 0
row 2: 01

Constraints:

• 1 <= n <= 30
• 1 <= k <= 2^n - 1

2023-10-26
823. Binary Trees With Factors

Topic: Array, Hash Table, Dynamic Programming, Sorting
Difficulty: Medium

Problem:
Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node's value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [2,4]
Output: 3
Explanation: We can make these trees: [2], [4], [4, 2, 2]

Example 2:

Input: arr = [2,4,5,10]
Output: 7
Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2].

Constraints:

• 1 <= arr.length <= 1000
• 2 <= arr[i] <= 10^9
• All the values of arr are unique.

2023-10-27
5. Longest Palindromic Substring

Topic: String, Dynamic Programming
Difficulty: Medium

Problem:
Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

2023-10-28
1220. Count Vowels Permutation

Topic: Dynamic Programming
Difficulty: Hard

Problem:
Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

• Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
• Each vowel 'a' may only be followed by an 'e'.
• Each vowel 'e' may only be followed by an 'a' or an 'i'.
• Each vowel 'i' may not be followed by another 'i'.
• Each vowel 'o' may only be followed by an 'i' or a 'u'.
• Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".

Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".

Example 3: 

Input: n = 5
Output: 68

Constraints:

• 1 <= n <= 2 * 10^4

End of Maintenance Notice

Dear subscribers,

I regret to inform you that I have made the decision to discontinue the maintenance of this bot. This means that I will no longer provide updates on LeetCode's "Question of Today".

The decision is primarily based on the following reasons:

1. Recent updates to LeetCode's security measures have made it increasingly challenging to bypass CloudFlare challenges.

2. The costs associated with server infrastructure and maintenance have become unsustainable given my current resources and budget.

3. Due to limited resources, I am no longer able to allocate the necessary time and attention required for the maintenance and support of this bot.

I understand that this may cause inconvenience, and I apologize for any disruption it may cause. The existing bot will remain available for use "as is," but I cannot guarantee its functionality.

I would like to express my gratitude for your support throughout its lifespan.

Thank you for your understanding.

Best regards,
LeetCode Question of Today Bot

2023-10-30
1356. Sort Integers by The Number of 1 Bits

Topic: Array, Bit Manipulation, Sorting, Counting
Difficulty: Easy

Problem:
You are given an integer array arr. Sort the integers in the array in ascending order by the number of 1's in their binary representation and in case of two or more integers have the same number of 1's you have to sort them in ascending order.

Return the array after sorting it.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Constraints:

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

2023-10-31
2433. Find The Original Array of Prefix Xor

Topic: Array, Bit Manipulation
Difficulty: Medium

Problem:
You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

• pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i].

Note that ^ denotes the bitwise-xor operation.

It can be proven that the answer is unique.

Example 1:

Input: pref = [5,2,0,3,1]
Output: [5,7,2,3,2]
Explanation: From the array [5,7,2,3,2] we have the following:
- pref[0] = 5.
- pref[1] = 5 ^ 7 = 2.
- pref[2] = 5 ^ 7 ^ 2 = 0.
- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3.
- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

Constraints:

• 1 <= pref.length <= 10^5
• 0 <= pref[i] <= 10^6

2023-11-01
501. Find Mode in Binary Search Tree

Topic: Tree, Depth-First Search, Binary Search Tree, Binary Tree
Difficulty: Easy

Problem:
Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Image: https://assets.leetcode.com/uploads/2021/03/11/mode-tree.jpg

Input: root = [1,null,2,2]
Output: [2]

Example 2:

Input: root = [0]
Output: [0]

Constraints:

• The number of nodes in the tree is in the range [1, 10^4].
• -10^5 <= Node.val <= 10^5

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

2023-11-02
2265. Count Nodes Equal to Average of Subtree

Topic: Tree, Depth-First Search, Binary Tree
Difficulty: Medium

Problem:
Given the root of a binary tree, return the number of nodes where the value of the node is equal to the average of the values in its subtree.

Note:

• The average of n elements is the sum of the n elements divided by n and rounded down to the nearest integer.
• A subtree of root is a tree consisting of root and all of its descendants.

Example 1:

Image: https://assets.leetcode.com/uploads/2022/03/15/image-20220315203925-1.png

Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation: 
For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4.
For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5.
For the node with value 0: The average of its subtree is 0 / 1 = 0.
For the node with value 1: The average of its subtree is 1 / 1 = 1.
For the node with value 6: The average of its subtree is 6 / 1 = 6.

Example 2:

Image: https://assets.leetcode.com/uploads/2022/03/26/image-20220326133920-1.png

Input: root = [1]
Output: 1
Explanation: For the node with value 1: The average of its subtree is 1 / 1 = 1.

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• 0 <= Node.val <= 1000

2023-11-03
1441. Build an Array With Stack Operations

Topic: Array, Stack, Simulation
Difficulty: Medium

Problem:
You are given an integer array target and an integer n.

You have an empty stack with the two following operations:

• "Push": pushes an integer to the top of the stack.
• "Pop": removes the integer on the top of the stack.

You also have a stream of the integers in the range [1, n].

Use the two stack operations to make the numbers in the stack (from the bottom to the top) equal to target. You should follow the following rules:

• If the stream of the integers is not empty, pick the next integer from the stream and push it to the top of the stack.
• If the stack is not empty, pop the integer at the top of the stack.
• If, at any moment, the elements in the stack (from the bottom to the top) are equal to target, do not read new integers from the stream and do not do more operations on the stack.

Return the stack operations needed to build target following the mentioned rules. If there are multiple valid answers, return any of them.

Example 1:

Input: target = [1,3], n = 3
Output: ["Push","Push","Pop","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Pop the integer on the top of the stack. s = [1].
Read 3 from the stream and push it to the stack. s = [1,3].

Example 2:

Input: target = [1,2,3], n = 3
Output: ["Push","Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Read 3 from the stream and push it to the stack. s = [1,2,3].

Example 3:

Input: target = [1,2], n = 4
Output: ["Push","Push"]
Explanation: Initially the stack s is empty. The last element is the top of the stack.
Read 1 from the stream and push it to the stack. s = [1].
Read 2 from the stream and push it to the stack. s = [1,2].
Since the stack (from the bottom to the top) is equal to target, we stop the stack operations.
The answers that read integer 3 from the stream are not accepted.

Constraints:

• 1 <= target.length <= 100
• 1 <= n <= 100
• 1 <= target[i] <= n
• target is strictly increasing.

2023-11-04
1503. Last Moment Before All Ants Fall Out of a Plank

Topic: Array, Brainteaser, Simulation
Difficulty: Medium

Problem:
We have a wooden plank of the length n units. Some ants are walking on the plank, each ant moves with a speed of 1 unit per second. Some of the ants move to the left, the other move to the right.

When two ants moving in two different directions meet at some point, they change their directions and continue moving again. Assume changing directions does not take any additional time.

When an ant reaches one end of the plank at a time t, it falls out of the plank immediately.

Given an integer n and two integer arrays left and right, the positions of the ants moving to the left and the right, return the moment when the last ant(s) fall out of the plank.

Example 1:

Image: https://assets.leetcode.com/uploads/2020/06/17/ants.jpg

Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).

Example 2:

Image: https://assets.leetcode.com/uploads/2020/06/17/ants2.jpg

Input: n = 7, left = [], right = [0,1,2,3,4,5,6,7]
Output: 7
Explanation: All ants are going to the right, the ant at index 0 needs 7 seconds to fall.

Example 3:

Image: https://assets.leetcode.com/uploads/2020/06/17/ants3.jpg

Input: n = 7, left = [0,1,2,3,4,5,6,7], right = []
Output: 7
Explanation: All ants are going to the left, the ant at index 7 needs 7 seconds to fall.

Constraints:

• 1 <= n <= 10^4
• 0 <= left.length <= n + 1
• 0 <= left[i] <= n
• 0 <= right.length <= n + 1
• 0 <= right[i] <= n
• 1 <= left.length + right.length <= n + 1
• All values of left and right are unique, and each value can appear only in one of the two arrays.

2023-11-05
1535. Find the Winner of an Array Game

Topic: Array, Simulation
Difficulty: Medium

Problem:
Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0, and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
  1   | [2,1,3,5,4,6,7] | 2      | 1
  2   | [2,3,5,4,6,7,1] | 3      | 1
  3   | [3,5,4,6,7,1,2] | 5      | 1
  4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.

Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.

Constraints:

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr contains distinct integers.
• 1 <= k <= 10^9