Problems
November 28, 2022
Design phone directory
We will use a set to keep track of the available numbers. We will also use a queue to keep track of the numbers that have been released.
Time complexity: O(1)
Space complexity:...
November 28, 2022
Count nodes equal to sum of descendants
We will use DFS in post order traversal to solve the problem. We will recursively call the function on the left and right child of the root. Then we will check if the sum of the left and right child...
ReadNovember 28, 2022
Design hashset
We will use a boolean array to store the values. We will use the value as the index of the array and set the value to true
if the value is added and false
if the value is...
November 28, 2022
Shortest word distance
We will keep track of both words' last seen index. Then we will iterate through the words
array and update the result if we find either of the words. Finally, we will return the result....
November 28, 2022
Count number of bad pairs
Rather counting the number of bad pair, we can count the number of good pair and substruct it from to total number of pairs to get the number of bad pairs. For an array of size n, there are exactly n...
ReadNovember 28, 2022
Count pairs in two arrays
nums1[i] + nums1[j] > nums2[i] + nums2[j]
, i < j can be converted to (nums1[i]-nums2[i]) + (nums1[j]-nums2[j]) > 0
, i < j.
At this point, we will realize that...
November 28, 2022
Find players with zero or one losses
We use 3 different hashset to store zero losses, one loss and more than one loss. Then we iterate through the results
array and update the hashsets accordingly. Finally, we iterate...
November 27, 2022
Binary tree upside down
We will use recursive DFS to solve the problem. We will recursively call the function on the left child of the root. Then we will set the left child of the root to the right child of the root. Then...
ReadNovember 27, 2022
Arithmetic slices II subsequence
We will use dynamic programming to solve the problem. We will use a hashmap to store the number of arithmetic slices that ends with the current number. We will iterate over the numbers, and for each...
ReadNovember 27, 2022
Arithmetic slices
We will take a top-down approach to solve the problem. Then we memoize each subproblem to avoid duplicate computation.
Time complexity: O(n)
, n is the length of nums
Space...