Amazon OA

Question 1

The variance of a string is defined as the largest difference between the number of occurrences of any 2 characters present in the string. Note the two characters may or may not be the same. Given a string s consisting of lowercase English letters only, return the largest variance possible among all substrings of s.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = “aababbb”

Output: 3

Explanation:All possible variances along with their respective substrings are listed below: - Variance 0 for substrings “a”, “aa”, “ab”, “abab”, “aababb”, “ba”, “b”, “bb”, and “bbb”. - Variance 1 for substrings “aab”, “aba”, “abb”, “aabab”, “ababb”, “aababbb”, and “bab”. - Variance 2 for substrings “aaba”, “ababbb”, “abbb”, and “babb”. - Variance 3 for substring “babbb”. Since the largest possible variance is 3, we return it.

Example 2:

Input: s = “abcde”Output: 0Explanation:No letter occurs more than once in s, so the variance of every substring is 0.

Constraints:

• 1 <= s.length <= 10⁴
• s consists of lowercase English letters.

Answer 1

Topic: Array + Dynamic Programming (Hard - Substring With Largest Variance)

Link to discuss: https://leetcode.com/problems/substring-with-largest-variance/discuss/2038556/Python3-or-Simple-or-Kadanes-algo-or-Faster-than-100

Approach: As maximum number of letters is 26, we may have in the worst case 26x25 combinations of different letters, which is not bad! We can pick any two letters and check the subarrays for the maximum length with Kadane’s algo! For letters x,y, I will check both cases when x-max occur, y-min occur and vice versa. As we need to have at least one occurrence of each letter, I used flags to make sure of it!

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 2

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the i^th wizard. For a contiguous group of wizards (i.e. the wizards’ strengths form a subarray of strength), the total strength is defined as the product of the following two values:

• The strength of the weakest wizard in the group.
• The total of all the individual strengths of the wizards in the group.

Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 10⁹ + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: strength = [1,3,1,2]

Output: 44

Explanation: The following are all the contiguous groups of wizards: - [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1 - [3] from [1,3,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9 - [1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1 - [2] from [1,3,1,2] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4 - [1,3] from [1,3,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4 - [3,1] from [1,3,1,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4 - [1,2] from [1,3,1,2] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3 - [1,3,1] from [1,3,1,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5 - [3,1,2] from [1,3,1,2] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6 - [1,3,1,2] from [1,3,1,2] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7 The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.

Example 2:

Input: strength = [5,4,6]

Output: 213

Explanation: The following are all the contiguous groups of wizards: - [5] from [5,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25 - [4] from [5,4,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16 - [6] from [5,4,6] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36 - [5,4] from [5,4,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36 - [4,6] from [5,4,6] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40 - [5,4,6] from [5,4,6] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60 The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.

Constraints:

• 1 <= strength.length <= 10⁵
• 1 <= strength[i] <= 10⁹

Answer 2

Topic: Stack / Prefix Sum (Hard - Sum of Total Strength of Wizards)

Link to discuss: https://leetcode.com/problems/sum-of-total-strength-of-wizards/discuss/2061985/JavaC%2B%2BPython-One-Pass-Solution

Approach: Intuition: Assume array[i] is the leftmost smallest element in a subarray, Calculate each array[i] contribution

Explanation:

1. Find next smallest on the right
2. Find next smallest or equal on the left.
3. For each array[i] as the minimum, find the possible subarray sums

Optimal TC: O(N) confirmed

Optimal SC: O(N) confirmed

Question 3

Let’s define a function countUniqueChars(s) that returns the number of unique characters on s.

• For example, calling countUniqueChars(s) if s = “LEETCODE” then “L”, “T”, “C”, “O”, “D” are the unique characters since they appear only once in s, therefore countUniqueChars(s) = 5.

Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.

Notice that some substrings can be repeated so in this case you have to count the repeated ones too.

Example 1:

Input: s = “ABC”

Output: 10

Explanation: All possible substrings are: “A”,”B”,”C”,”AB”,”BC” and “ABC”. Every substring is composed with only unique letters. Sum of lengths of all substring is 1 + 1 + 1 + 2 + 2 + 3 = 10

Example 2:

Input: s = “ABA”

Output: 8

Explanation: The same as example 1, except countUniqueChars(“ABA”) = 1.

Example 3:

Input: s = “LEETCODE”

Output: 92

Constraints:

• 1 <= s.length <= 10⁵
• s consists of uppercase English letters only.

Answer 3

Topic: Dynamic Programming (Hard - Count Unique Characters of All Substrings of a Given String)

Link Discuss: https://leetcode.com/problems/count-unique-characters-of-all-substrings-of-a-given-string/discuss/128952/JavaC%2B%2BPython-One-pass-O(N)

Approach: Intuition

Let’s think about how a character can be found as a unique character.

Think about string “XAXAXXAX” and focus on making the second “A” a unique character.
We can take “XA(XAXX)AX” and between “()” is our substring.
We can see here, to make the second “A” counted as a unique character, we need to:

1. insert “(“ somewhere between the first and second A
2. insert “)” somewhere between the second and third A

For step 1 we have “A(XA” and “AX(A”, 2 possibility.
For step 2 we have “A)XXA”, “AX)XA” and “AXX)A”, 3 possibilities.

So there are in total 2 * 3 = 6 ways to make the second A a unique character in a substring.
In other words, there are only 6 substring, in which this A contribute 1 point as unique string.

Instead of counting all unique characters and struggling with all possible substrings,
we can count for every char in S, how many ways to be found as a unique char.
We count and sum, and it will be out answer.

Explanation

1. index[26][2] record last two occurrence index for every upper characters.
2. Initialize all values in index to -1.
3. Loop on string S, for every character c, update its last two occurrence index to index[c].
4. Count when loop. For example, if “A” appears twice at index 3, 6, 9 separately, we need to count:
   
   • For the first “A”: (6-3) * (3-(-1))”
   • For the second “A”: (9-6) * (6-3)”
   • For the third “A”: (N-9) * (9-6)”

Optimal TC: O(N)

Optimal SC: O(1)

Question 4

You are given two string arrays username and website and an integer array timestamp. All the given arrays are of the same length and the tuple [username[i], website[i], timestamp[i]] indicates that the user username[i] visited the website website[i] at time timestamp[i].

A pattern is a list of three websites (not necessarily distinct).

• For example, [“home”, “away”, “love”], [“leetcode”, “love”, “leetcode”], and [“luffy”, “luffy”, “luffy”] are all patterns.

The score of a pattern is the number of users that visited all the websites in the pattern in the same order they appeared in the pattern.

• For example, if the pattern is [“home”, “away”, “love”], the score is the number of users x such that x visited “home” then visited “away” and visited “love” after that.
• Similarly, if the pattern is [“leetcode”, “love”, “leetcode”], the score is the number of users x such that x visited “leetcode” then visited “love” and visited “leetcode” one more time after that.
• Also, if the pattern is [“luffy”, “luffy”, “luffy”], the score is the number of users x such that x visited “luffy” three different times at different timestamps.

Return the pattern with the largest score. If there is more than one pattern with the same largest score, return the lexicographically smallest such pattern.

Example 1:

Input: username = [“joe”,”joe”,”joe”,”james”,”james”,”james”,”james”,”mary”,”mary”,”mary”], timestamp = [1,2,3,4,5,6,7,8,9,10], website = [“home”,”about”,”career”,”home”,”cart”,”maps”,”home”,”home”,”about”,”career”]

Output: [“home”,”about”,”career”]

Explanation: The tuples in this example are: [“joe”,”home”,1],[“joe”,”about”,2],[“joe”,”career”,3],[“james”,”home”,4],[“james”,”cart”,5],[“james”,”maps”,6],[“james”,”home”,7],[“mary”,”home”,8],[“mary”,”about”,9], and [“mary”,”career”,10]. The pattern (“home”, “about”, “career”) has score 2 (joe and mary). The pattern (“home”, “cart”, “maps”) has score 1 (james). The pattern (“home”, “cart”, “home”) has score 1 (james). The pattern (“home”, “maps”, “home”) has score 1 (james). The pattern (“cart”, “maps”, “home”) has score 1 (james). The pattern (“home”, “home”, “home”) has score 0 (no user visited home 3 times).

Example 2:

Input: username = [“ua”,”ua”,”ua”,”ub”,”ub”,”ub”], timestamp = [1,2,3,4,5,6], website = [“a”,”b”,”a”,”a”,”b”,”c”]

Output: [“a”,”b”,”a”]

Constraints:

• 3 <= username.length <= 50
• 1 <= username[i].length <= 10
• timestamp.length == username.length
• 1 <= timestamp[i] <= 10⁹
• website.length == username.length
• 1 <= website[i].length <= 10
• username[i] and website[i] consist of lowercase English letters.
• It is guaranteed that there is at least one user who visited at least three websites.
• All the tuples [username[i], timestamp[i], website[i]] are unique.

Answer 4

Topic: Sorting (Medium - Analyze User Website Visit Pattern)

Discuss Link: https://leetcode.com/problems/analyze-user-website-visit-pattern/discuss/899805/DETAILED-Easy-to-Follow-Python-Solution-%2B-Clearly-Explained

**Approach**: 
 # 1. first get all possible 3-sequences 
 # 2. then, count each one once
 # 3. finally, count the number of times we've seen the 3-sequence for every user
 # 4. get most frequent 3-sequence sorted lexicographically

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 5

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,2,3]

Output: 4

Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [2], range = 2 - 2 = 0 [3], range = 3 - 3 = 0 [1,2], range = 2 - 1 = 1 [2,3], range = 3 - 2 = 1 [1,2,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.

Example 2:

Input: nums = [1,3,3]

Output: 4

Explanation: The 6 subarrays of nums are the following: [1], range = largest - smallest = 1 - 1 = 0 [3], range = 3 - 3 = 0 [3], range = 3 - 3 = 0 [1,3], range = 3 - 1 = 2 [3,3], range = 3 - 3 = 0 [1,3,3], range = 3 - 1 = 2 So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.

Example 3:

Input: nums = [4,-2,-3,4,1]

Output: 59

Explanation: The sum of all subarray ranges of nums is 59.

Constraints:

• 1 <= nums.length <= 1000
• -10⁹ <= nums[i] <= 10⁹

Follow-up: Could you find a solution with O(n) time complexity?

Answer 5

Topic: Monotonic Stack (Medium - Sum of Subarray Ranges)

Discuss Link: https://leetcode.com/problems/sum-of-subarray-ranges/discuss/1624222/JavaC%2B%2BPython-O(n)-solution-detailed-explanation

Approach: Intuition

res = sum(A[i] \* f(i))
where f(i) is the number of subarrays,
in which A[i] is the minimum.

To get f(i), we need to find out:
left[i], the length of strict bigger numbers on the left of A[i],
right[i], the length of bigger numbers on the right of A[i].

Then,
left[i] + 1 equals to
the number of subarray ending with A[i],
and A[i] is single minimum.

right[i] + 1 equals to
the number of subarray starting with A[i],
and A[i] is the first minimum.

Finally f(i) = (left[i] + 1) * (right[i] + 1)

For [3,1,2,4] as example:
left + 1 = [1,2,1,1]
right + 1 = [1,3,2,1]
f = [1,6,2,1]
res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17

Explanation

To calculate left[i] and right[i],
we use two increasing stacks.

Optimal TC: O(N) confirmed

Optimal SC: O(N) confirmed

Question 6

You are given an array of logs. Each log is a space-delimited string of words, where the first word is the identifier.

There are two types of logs:

• Letter-logs: All words (except the identifier) consist of lowercase English letters.
• Digit-logs: All words (except the identifier) consist of digits.

Reorder these logs so that:

1. The letter-logs come before all digit-logs.
2. The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
3. The digit-logs maintain their relative ordering.

Return the final order of the logs.

Example 1:

Input: logs = [“dig1 8 1 5 1”,”let1 art can”,”dig2 3 6”,”let2 own kit dig”,”let3 art zero”]

Output: [“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]

Explanation:The letter-log contents are all different, so their ordering is “art can”, “art zero”, “own kit dig”. The digit-logs have a relative order of “dig1 8 1 5 1”, “dig2 3 6”.

Example 2:

Input: logs = [“a1 9 2 3 1”,”g1 act car”,”zo4 4 7”,”ab1 off key dog”,”a8 act zoo”]

Output: [“g1 act car”,”a8 act zoo”,”ab1 off key dog”,”a1 9 2 3 1”,”zo4 4 7”]

Constraints:

• 1 <= logs.length <= 100
• 3 <= logs[i].length <= 100
• All the tokens of logs[i] are separated by a single space.
• logs[i] is guaranteed to have an identifier and at least one word after the identifier.

Answer 6

Topic: Sorting (Medium - Reorder Data in Log Files)

Hint: https://leetcode.com/problems/reorder-data-in-log-files/discuss/352878/Python3-Sort-the-list-use-key

Approach:

• define a function to label the item in logs with 0 if the rest is alphabet, with 1 if the rest is number.
• sort the list according to the label.

By default, sort(key) means to sort the list by key in increasing order.
if b[0] is letter: key = (0,b,a)
If b[0] is not letter: key = (1,None,None)
effect of use (None,None) is when you sort letter-logs, the digit-logs remain in the same order.
(1,) is short for (1,None,None).
step 1: 0 < 1: so letter-logs come before any digit-log.
we get:
[“let1 art can”,”let2 own kit dig”,”let3 art zero”,”dig1 8 1 5 1”,”dig2 3 6”]
step 2: b and None The letter-logs are sorted lexicographically by contend(b), the digit-logs remain in the same order
We get:
[“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]
step3: a and None, The letter-logs are sorted lexicographically by identifier(a), the digit-logs remain in the same order.
We get:
[“let1 art can”,”let3 art zero”,”let2 own kit dig”,”dig1 8 1 5 1”,”dig2 3 6”]

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 7

Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.

A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.

Example 1:

Input: words = [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”]

Output: [“catsdogcats”,”dogcatsdog”,”ratcatdogcat”]

Explanation:“catsdogcats” can be concatenated by “cats”, “dog” and “cats”; “dogcatsdog” can be concatenated by “dog”, “cats” and “dog”; “ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.

Example 2:

Input: words = [“cat”,”dog”,”catdog”]

Output: [“catdog”]

Constraints:

• 1 <= words.length <= 10⁴
• 1 <= words[i].length <= 30
• words[i] consists of only lowercase English letters.
• All the strings of words are unique.
• 1 <= sum(words[i].length) <= 10⁵

Answer 7

Topic: DFS (Hard - Concatenated Words)

Discuss Link(Memoization solution is below main post): https://leetcode.com/problems/concatenated-words/discuss/159348/Python-DFS-readable-solution

Approach: Basic idea is to find if strings can be broken down to smaller strings. I believe this could be dealt with thru several appraching such as backtracking or a bottom-up dynamic programming approach, but I went with a Depth First Search approach here, while optimizing a bit with memoization .

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 8

You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:

Input: products = [“mobile”,”mouse”,”moneypot”,”monitor”,”mousepad”], searchWord = “mouse”

Output: [[“mobile”,”moneypot”,”monitor”], [“mobile”,”moneypot”,”monitor”], [“mouse”,”mousepad”], [“mouse”,”mousepad”], [“mouse”,”mousepad”] ]

Explanation: products sorted lexicographically = [“mobile”,”moneypot”,”monitor”,”mouse”,”mousepad”] After typing m and mo all products match and we show user [“mobile”,”moneypot”,”monitor”] After typing mou, mous and mouse the system suggests [“mouse”,”mousepad”]

Example 2:

Input: products = [“havana”], searchWord = “havana”

Output: [[“havana”],[“havana”],[“havana”],[“havana”],[“havana”],[“havana”]]

Example 3:

Input: products = [“bags”,”baggage”,”banner”,”box”,”cloths”], searchWord = “bags”

Output: [[“baggage”,”bags”,”banner”],[“baggage”,”bags”,”banner”],[“baggage”,”bags”],[“bags”]]

Constraints:

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 <= sum(products[i].length) <= 2 * 10⁴
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• 1 <= searchWord.length <= 1000
• searchWord consists of lowercase English letters.

Answer 8

Topic: Binary Search for Prefix / Tries (Medium - Search Suggestions System)

Discuss Link: https://leetcode.com/problems/search-suggestions-system/discuss/436674/C%2B%2BJavaPython-Sort-and-Binary-Search-the-Prefix

Approach:

Intuition

In a sorted list of words, for any word array[i], all its suggested words must following this word in the list. For example, if array[i] is a prefix of array[j],
array[i] must be the prefix of array[i + 1], array[i + 2], …, array[j]

Explanation

With this observation, we can binary search the position of each prefix of search word, and check if the next 3 words is a valid result.

Optimal TC: O(NlogN) + MlogN), where N is number of elements in products, M is length of searchWord string. Here we treat compare strings in O(1).

Optimal SC: O(logN) for sorting buffer

Question 9

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

• LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
• int get(int key) Return the value of the key if the key exists, otherwise return -1.
• void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

Output[null, null, null, 1, null, -1, null, -1, 3, 4]

ExplanationLRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 10⁴
• 0 <= value <= 10⁵
• At most 2 * 10⁵ calls will be made to get and put.

Answer 9

Topic: Doubly Linked List + Hashmap (Medium - LRU Cache) 🔙Neetcode 150!

Source: have neetcode solution

Approach: This problem can be solved with a hashmap that keeps track of the keys and its values in a double linked list. That results in O(1) time for put and get operations and allows to remove the first added node in O(1) time as well. One advantage of double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail. One particularity about the double linked list implemented here is that there are pseudo head and pseudo tail to mark the boundary, so that we don’t need to check the null node during the update.

Optimal TC: O(1) both for put and get.

Optimal SC: O(capacity) since the space is used only for a hashmap and double linked list with at most capacity + 1 elements.

Question 10

You are playing a game that has n levels numbered from 0 to n - 1. You are given a 0-indexed integer array damage where damage[i] is the amount of health you will lose to complete the i^th level.

You are also given an integer armor. You may use your armor ability at most once during the game on any level which will protect you from at most armor damage.

You must complete the levels in order and your health must be greater than 0 at all times to beat the game.

Return the minimum health you need to start with to beat the game.

Example 1:

Input: damage = [2,7,4,3], armor = 4

Output: 13

Explanation: One optimal way to beat the game starting at 13 health is: On round 1, take 2 damage. You have 13 - 2 = 11 health. On round 2, take 7 damage. You have 11 - 7 = 4 health. On round 3, use your armor to protect you from 4 damage. You have 4 - 0 = 4 health. On round 4, take 3 damage. You have 4 - 3 = 1 health. Note that 13 is the minimum health you need to start with to beat the game.

Example 2:

Input: damage = [2,5,3,4], armor = 7

Output: 10

Explanation: One optimal way to beat the game starting at 10 health is: On round 1, take 2 damage. You have 10 - 2 = 8 health. On round 2, use your armor to protect you from 5 damage. You have 8 - 0 = 8 health. On round 3, take 3 damage. You have 8 - 3 = 5 health. On round 4, take 4 damage. You have 5 - 4 = 1 health. Note that 10 is the minimum health you need to start with to beat the game.

Example 3:

Input: damage = [3,3,3], armor = 0

Output: 10

Explanation: One optimal way to beat the game starting at 10 health is: On round 1, take 3 damage. You have 10 - 3 = 7 health. On round 2, take 3 damage. You have 7 - 3 = 4 health. On round 3, take 3 damage. You have 4 - 3 = 1 health. Note that you did not use your armor ability.

Constraints:

• n == damage.length
• 1 <= n <= 10⁵
• 0 <= damage[i] <= 10⁵
• 0 <= armor <= 10⁵

Answer 10

Topic: Array + Greedy (Medium - Minimum Health to Beat Game)

Discuss Link: https://leetcode.com/problems/minimum-health-to-beat-game/discuss/1883509/Python-Easy-to-understand-beats-88-runtime-and-36-memory

Approach: Without considering the armor, we need 1 + total_damage amount of health to pass. Considering the armor, we just use it to shield the most severe damage, call it max_damage, and it should save us min(armor, max_damage) amount of health. For example, armor=4, when max_damage=5, then we still take 1 health loss (saved 4 health points), and if max_damage=3, then we take 0 health loss (saved 3 health points). Based on this idea, we just sums up all damages, and remove the amount saved by the armor, then plus 1.

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 11

Given an m x n 2D binary grid grid which represents a map of ‘1’s (land) and ‘0’s (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [[“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ]

Output: 1

Example 2:

Input: grid = [[“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ]

Output: 3

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is ‘0’ or ‘1’.

Answer 11

Topic: DFS Graph (Medium - Number of Islands) 🔙Neetcode 150!

Source: Neetcode solution

Approach: I went with a Depth First Search approach for this problem. Inside my DFS function I would first check for a valid land position as a base case. Once I have confirmed I have a valid land position I would mark the cell, then run a recursive DFS call on all neighbors.

Optimal TC: O(M*N)

Optimal SC: O(M*N)

Question 12

Given an array of points where points[i] = [x_i, y_i] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x₁ - x₂)² + (y₁ - y₂)²).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

Input: points = [[1,3],[-2,2]], k = 1

Output: [[-2,2]]

Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2

Output: [[3,3],[-2,4]]

Explanation: The answer [[-2,4],[3,3]] would also be accepted.

Constraints:

• 1 <= k <= points.length <= 10⁴
• -10⁴ < x_i, y_i < 10⁴

Answer 12

Topic: Heap (Medium - K Closest Points to Origin) 🔙Neetcode 150!

Source: Neetcode Solution

Approach: I feel like using a min Heap data structure would work best for this problem. I would keep a min heap of size K. For each item I would calculate the distance (as the formula is given by the problem) for each set of points and store them in the heap. If inserting an item makes heap size larger than k, then we immediately pop an item after inserting

Optimal TC: O(N * logK) where N is the length of points.

Optimal SC: O(K)

Question 13

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s₁ -> s₂ -> … -> s_k such that:

• Every adjacent pair of words differs by a single letter.
• Every s_i for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
• s_k == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

Example 1:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

Output: 5

Explanation: One shortest transformation sequence is “hit” -> “hot” -> “dot” -> “dog” -> cog”, which is 5 words long.

Example 2:

Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]

Output: 0

Explanation: The endWord “cog” is not in wordList, therefore there is no valid transformation sequence.

Constraints:

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord, endWord, and wordList[i] consist of lowercase English letters.
• beginWord != endWord
• All the words in wordList are unique.

Answer 13

Topic: Hash Table + BFS (Hard - Word Ladder) 🔙Neetcode 150!

Source: Neetcode Solution

Approach: This problem is asking us to find a shortest path from our start word to end word using only word inside our list. Now any time I think, find the shortest sequence I immediately think, alright I need to use some shortest path algorithm like Breadth-First-Search. I would begin by building an adjacency list. Then I want to use a deque and run a BFS to find shortest sequence path in the graph

Optimal TC: O(M^2*N) where M is the length of each word and N is the total number of words in the input word list.

Optimal SC: O(M^2*N)

Question 14

Convert a non-negative integer num to its English words representation.

Example 1:

Input: num = 123

Output:“One Hundred Twenty Three”

Example 2:

Input: num = 12345

Output:“Twelve Thousand Three Hundred Forty Five”

Example 3:

Input: num = 1234567

Output:“One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

Constraints:

• 0 <= num <= 2³¹ - 1

Answer 14

Topic: Divide and Conquer (Hard - Integer to English Words)

Discuss Link (used comment below to remove loop): https://leetcode.com/problems/integer-to-english-words/discuss/70632/Recursive-Python

Approach: Divide and Conquer by breaking this down into a lot of sub problems (lots of if statements) ## APPROACH : BRUTE FORCE ## Main intent of the interviewer when asked this question is, he is testing how you are handling the test cases and how elegantly you are using sub problems to get to the final solution so focus on edge cases. For a two digit number if there is no ones digit 20 -> twenty + “ “ (number generally), don’t leave the space behind, use if else case with “” (empty). Similarly for 20,000 etc.

Optimal TC: O(N) output is proportional to the number N of digits in the input.

Optimal SC: O(1) since the output is just a string

Question 15

You are given a string s consisting only of lowercase English letters.

In one move, you can select any two adjacent characters of s and swap them.

Return the minimum number of moves needed to make s a palindrome.

Note that the input will be generated such that s can always be converted to a palindrome.

Example 1:

Input: s = “aabb”

Output: 2

Explanation:We can obtain two palindromes from s, “abba” and “baab”. - We can obtain “abba” from s in 2 moves: “aab**b” -> “ab**ab**” -> “abba”. - We can obtain “baab” from s in 2 moves: “a_abb” -> “ab_**ab” -> “baab”. Thus, the minimum number of moves needed to make s a palindrome is 2.

Example 2:

Input: s = “letelt”

Output: 2

Explanation:One of the palindromes we can obtain from s in 2 moves is “lettel”. One of the ways we can obtain it is “letelt**” -> “let_et_**l” -> “lettel”. Other palindromes such as “tleelt” can also be obtained in 2 moves. It can be shown that it is not possible to obtain a palindrome in less than 2 moves.

Constraints:

• 1 <= s.length <= 2000
• s consists only of lowercase English letters.
• s can be converted to a palindrome using a finite number of moves.

Answer 15

Topic: Greedy (Hard - Minimum Number of Moves to Make Palindrome)

Discuss Link: https://leetcode.com/problems/minimum-number-of-moves-to-make-palindrome/discuss/1822174/C%2B%2BPython-Short-Greedy-Solution

Approach: Considering the first and the last char in final palindrome. If they are neither the first nor the last char in the initial string, you must waste some steps:
Assume start with “…a….a..”
“.a…….a.” can be ealier completed thand “a………a”.

Then compare the situation “a….b..a…b”
It takes same number of steps to “ab………ba” and “ba………ab”.
So we can actually greedily move the characters to match string prefix.

Optimal TC: O(N^2)

Optimal SC: O(N)

Question 16

The appeal of a string is the number of distinct characters found in the string.

• For example, the appeal of “abbca” is 3 because it has 3 distinct characters: ‘a’, ‘b’, and ‘c’.

Given a string s, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = “abbca”

Output: 28

Explanation: The following are the substrings of “abbca”: - Substrings of length 1: “a”, “b”, “b”, “c”, “a” have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5. - Substrings of length 2: “ab”, “bb”, “bc”, “ca” have an appeal of 2, 1, 2, and 2 respectively. The sum is 7. - Substrings of length 3: “abb”, “bbc”, “bca” have an appeal of 2, 2, and 3 respectively. The sum is 7. - Substrings of length 4: “abbc”, “bbca” have an appeal of 3 and 3 respectively. The sum is 6. - Substrings of length 5: “abbca” has an appeal of 3. The sum is 3. The total sum is 5 + 7 + 7 + 6 + 3 = 28.

Example 2:

Input: s = “code”

Output: 20

Explanation: The following are the substrings of “code”: - Substrings of length 1: “c”, “o”, “d”, “e” have an appeal of 1, 1, 1, and 1 respectively. The sum is 4. - Substrings of length 2: “co”, “od”, “de” have an appeal of 2, 2, and 2 respectively. The sum is 6. - Substrings of length 3: “cod”, “ode” have an appeal of 3 and 3 respectively. The sum is 6. - Substrings of length 4: “code” has an appeal of 4. The sum is 4. The total sum is 4 + 6 + 6 + 4 = 20.

Constraints:

• 1 <= s.length <= 10⁵
• s consists of lowercase English letters.

Answer 16

Topic: Dynamic Programming (Hard - Total Appeal of A String)

Discuss Link: https://leetcode.com/problems/total-appeal-of-a-string/discuss/1996390/JavaC%2B%2BPython-Easy-and-Concise-with-Explanation

Approach: (further explanation in first comment above). Assume we have string xxxaxxxxb…, with s[i] = a and s[j] = b. s[i] is the last character a before that b. We want to count, how many substring ending at s[j] contains character a. They are xxxaxxxxb, xxaxxxxb, xaxxxxb, axxxxb ….,i + 1 substring ending with character a at s[i], so we do res += i + 1. We repeatedly do this for every s[i] and every one of 26 characters.

Optimal TC: O(N)

Optimal SC: O(26)

Question 17

Design a data structure that simulates an in-memory file system.

Implement the FileSystem class:

• FileSystem() Initializes the object of the system.
• List ls(String path)
  
  • If path is a file path, returns a list that only contains this file’s name.
  • If path is a directory path, returns the list of file and directory names in this directory.
• void mkdir(String path) Makes a new directory according to the given path. The given directory path does not exist. If the middle directories in the path do not exist, you should create them as well.
• void addContentToFile(String filePath, String content)
  
  • If filePath does not exist, creates that file containing given content.
  • If filePath already exists, appends the given content to original content.
• String readContentFromFile(String filePath) Returns the content in the file at filePath.

Example 1:

Input [“FileSystem”, “ls”, “mkdir”, “addContentToFile”, “ls”, “readContentFromFile”] [[], [”/”], [“/a/b/c”], [“/a/b/c/d”, “hello”], [”/”], [“/a/b/c/d”]]

Output [null, [], null, null, [“a”], “hello”]

Explanation FileSystem fileSystem = new FileSystem(); fileSystem.ls(“/”); // return [] fileSystem.mkdir(“/a/b/c”); fileSystem.addContentToFile(“/a/b/c/d”, “hello”); fileSystem.ls(“/”); // return [“a”] fileSystem.readContentFromFile(“/a/b/c/d”); // return “hello”

Constraints:

• 1 <= path.length, filePath.length <= 100
• path and filePath are absolute paths which begin with ‘/’ and do not end with ‘/’ except that the path is just “/”.
• You can assume that all directory names and file names only contain lowercase letters, and the same names will not exist in the same directory.
• You can assume that all operations will be passed valid parameters, and users will not attempt to retrieve file content or list a directory or file that does not exist.
• 1 <= content.length <= 50
• At most 300 calls will be made to ls, mkdir, addContentToFile, and readContentFromFile.

Answer 17

Topic: Trie (Hard - Design In-Memory File System)

Discuss Link: https://leetcode.com/problems/design-in-memory-file-system/discuss/426854/python-scalable-trie-solution

Approach: Trie solution

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 18

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]

Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]

Output: 1

Constraints:

• 1 <= intervals.length <= 10⁴
• 0 <= start_i < end_i <= 10⁶

Answer 18

Topic: Intervals (Medium - Meeting Rooms II) 🔙Neetcode 150!

Discuss Link: Solved with neetcode

Approach: I want to start by adding all the start and end times into sorted arrays so we can get them into chronological order. We would then loop thru using two pointers for the start and end times. First we would check if position in start is < position of end. When this is true we want to move the start pointer and increment the room count. Else: we need to handle is s >= e where we would instead increment the end pointer and decrement count. Finally before the end of the iteration would would update the result with the max count.

Optimal TC: O(NlogN)

Optimal SC: O(N)

Question 19

You are given a 0-indexed integer array books of length n where books[i] denotes the number of books on the i^th shelf of a bookshelf.

You are going to take books from a contiguous section of the bookshelf spanning from l to r where 0 <= l <= r < n. For each index i in the range l <= i < r, you must take strictly fewer books from shelf i than shelf i + 1.

Return the maximum number of books you can take from the bookshelf.

Example 1:

Input: books = [8,5,2,7,9]

Output: 19

Explanation:- Take 1 book from shelf 1. - Take 2 books from shelf 2. - Take 7 books from shelf 3. - Take 9 books from shelf 4. You have taken 19 books, so return 19. It can be proven that 19 is the maximum number of books you can take.

Example 2:

Input: books = [7,0,3,4,5]

Output: 12

Explanation:- Take 3 books from shelf 2. - Take 4 books from shelf 3. - Take 5 books from shelf 4. You have taken 12 books so return 12. It can be proven that 12 is the maximum number of books you can take.

Example 3:

Input: books = [8,2,3,7,3,4,0,1,4,3]

Output: 13

Explanation:- Take 1 book from shelf 0. - Take 2 books from shelf 1. - Take 3 books from shelf 2. - Take 7 books from shelf 3. You have taken 13 books so return 13. It can be proven that 13 is the maximum number of books you can take.

Constraints:

• 1 <= books.length <= 10⁵
• 0 <= books[i] <= 10⁵

Answer 19

Topic: Dynamic Programming w/ mono stack (Hard - Maximum Number of Books You Can Take

Discuss Link: https://leetcode.com/problems/maximum-number-of-books-you-can-take/discuss/2343220/Python-DP-and-Stack-O(N)

Approach:

• Step 1: Create a dp array where dp[i] is the maximum number of books that we can take from bookshelves 0 to i and we must take all books from bookshelf i.
• Step 2: Keep taking as many books as we can (i.e. starting from bookshelf i and going backwards, you take arr[i], arr[i] - 1, arr[i] - 2, …, books).
• Step 3: Keep a stack of possible indices for j. If x is the number at the top of the stack, keep popping from the stack while arr[x] ≥ arr[i] - (i - x). This is because if the inequality mentioned before is true, x will never be an index j as index i will run out of items first.

Optimal TC: O(N)

Optimal SC: O(N)

Question 20

A scenic location is represented by its name and attractiveness score, where name is a unique string among all locations and score is an integer. Locations can be ranked from the best to the worst. The higher the score, the better the location. If the scores of two locations are equal, then the location with the lexicographically smaller name is better.

You are building a system that tracks the ranking of locations with the system initially starting with no locations. It supports:

• Adding scenic locations, one at a time.
• Querying the i^th best location of all locations already added, where i is the number of times the system has been queried (including the current query).
  
  • For example, when the system is queried for the 4^th time, it returns the 4^th best location of all locations already added.

Note that the test data are generated so that at any time, the number of queries does not exceed the number of locations added to the system.

Implement the SORTracker class:

• SORTracker() Initializes the tracker system.
• void add(string name, int score) Adds a scenic location with name and score to the system.
• string get() Queries and returns the i^th best location, where i is the number of times this method has been invoked (including this invocation).

Example 1:

Input[“SORTracker”, “add”, “add”, “get”, “add”, “get”, “add”, “get”, “add”, “get”, “add”, “get”, “get”] [[], [“bradford”, 2], [“branford”, 3], [], [“alps”, 2], [], [“orland”, 2], [], [“orlando”, 3], [], [“alpine”, 2], [], []]

Output[null, null, null, “branford”, null, “alps”, null, “bradford”, null, “bradford”, null, “bradford”, “orland”]

Example: LONG

Constraints:

• name consists of lowercase English letters, and is unique among all locations.
• 1 <= name.length <= 10
• 1 <= score <= 10⁵
• At any time, the number of calls to get does not exceed the number of calls to add.
• At most 4 * 10⁴ calls in total will be made to add and get.

Answer 20

Topic: Sorting (Hard - Sequentially Ordinal Rank Tracker)

Discuss Link: https://leetcode.com/problems/sequentially-ordinal-rank-tracker/discuss/1626625/python-binary-search-100-faster-4-lines-explained

• Note there are 2 solutions but one uses an external library that may not be available
• Need to look up bisect and insort for 4-liner code
• There is also a double heap variation that is O(LogN). Example: https://leetcode.com/problems/sequentially-ordinal-rank-tracker/discuss/2202661/Python-Two-Heaps-Solution-(Clear)-O(logN)

Approach: The goal is to maintain a sorted list which consists of (-score, name) and maintain a query index.
For the add method: find the insert position by binary searching and then insert the (-score, name) into sorted list
For the get method: update query index and output the i’th name

Optimal TC: O(N)

Optimal SC: O(N) -→ (O(LogN) with the external library)

Question 21

In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.

• For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]

Output: 6

Explanation: Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6. There are no other nodes with twins in the linked list. Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]

Output: 7

Explanation: The nodes with twins present in this linked list are: - Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7. - Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4. Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]

Output: 100001

Explanation: There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

• The number of nodes in the list is an even integer in the range [2, 10⁵].
• 1 <= Node.val <= 10⁵

Answer 21

Topic: Linked List Slow and Fast pointers (Medium - Maximum Twin Sum of a Linked List)

Discuss Link: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/discuss/1676025/Need-to-know-O(1)-space-solution-in-Python

Approach: Fast and slow pointers for this approach. The idea is to reverse the latter half of the linked list. Let’s call this reversed list “second”. Then add first (original linked list) and second values to find the maximum sum.

Optimal TC: O(N)

Optimal SC: O(N) with an O(1) optimal solution

Question 22

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]

Output: [1,1,2,3,4,4,5,6]

Explanation: The linked-lists are: [1->4->5, 1->3->4, 2->6] merging them into one sorted list: 1->1->2->3->4->4->5->6

Example 2:

Input: lists = []

Output: []

Example 3:

Input: lists = [[]]

Output: []

Constraints:

• k == lists.length
• 0 <= k <= 10⁴
• 0 <= lists[i].length <= 500
• -10⁴ <= lists[i][j] <= 10⁴
• lists[i] is sorted in ascending order.
• The sum of lists[i].length will not exceed 10⁴.

Answer 22

Topic: Linked List / Divide and Conquer (Hard - Merge k Sorted Lists) 🔙Neetcode 150!

Hint: Done, but could use some comments from neetcode

Approach: I was able to take a divide and conquer approach for this problem. I would need a helper function to merge 2 linked lists. My main function would aim to pair up k lists and merge each pair. After the first pairing, k lists are merged into k/2 lists with average 2N/k length, then k/4, k/8 and so on. I would repeat this procedure until we get the final sorted linked list.

Optimal TC: O(NlogK)

Optimal SC: O(1)

Question 23

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]

Output: 4

Explanation: The array nums already has a positive product of 24.

Example 2:

Input: nums = [0,1,-2,-3,-4]

Output: 3

Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6. Notice that we cannot include 0 in the subarray since that’ll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]

Output: 2

Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹

Answer 23

Topic: Dynamic Programming (Medium - Maximum Length of Subarray With Positive Product)

Discuss Link: https://leetcode.com/problems/maximum-length-of-subarray-with-positive-product/discuss/819329/Python3GoJava-Dynamic-Programming-O(N)-time-O(1)-space

Approach:

Intuition
At every iteration, tracking maximum length of positive multiplicative result and negative multiplicative result.

Algorithm:

1. If we see a positive number :
   
   1. Increase length of positive multiplicative result till now.
   2. Increase length of negative multiplicative result till now, unless we had not encountered any negative before.
2. If we see a negative number:
   
   1. It’s time to swap positive and negative multiplicative results’ lengths and do similar task as we did in above case.
3. If we see a 0, we need to restart
4. In each iteration, use the length of positive multiplicative result to update the answer.

Optimal TC: O(N)

Optimal SC: O(1)

Question 24

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,
• 1 representing a fresh orange, or
• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Answer 24

Topic: BFS Graph (Medium - Rotting Oranges) 🔙Neetcode 150!

Discuss Link: Neetcode solution with comments

Approach: I went with a Breadth first search approach for this problem. I began with a Brute force check on each cell to see how many fresh oranges we have. When we find a rotten orange, add to the queue. From here I would loop and keep iterating while we have a non-empty queue and fresh oranges in our grid. After the queue is emptied and fully processed I would return the time when we are out of fresh oranges or -1 if not possible.

Optimal TC: O(N) where NN is the size of the grid.

Optimal SC: O(N) where NN is the size of the grid.

Question 25

You are given a 0-indexed integer array nums, where nums[i] is a digit between 0 and 9 (inclusive).

The triangular sum of nums is the value of the only element present in nums after the following process terminates:

1. Let nums comprise of n elements. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n - 1.
2. For each index i, where 0 <= i < n - 1, assign the value of newNums[i] as (nums[i] + nums[i+1]) % 10, where % denotes modulo operator.
3. Replace the array nums with newNums.
4. Repeat the entire process starting from step 1.

Return the triangular sum of nums.

Example 1:

Input: nums = [1,2,3,4,5]

Output: 8

Explanation:The above diagram depicts the process from which we obtain the triangular sum of the array.

Example 2:

Input: nums = [5]

Output: 5

Explanation:Since there is only one element in nums, the triangular sum is the value of that element itself.

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 9

Answer 25

Topic: Math (Medium - Find Triangular Sum of an Array)

Discuss Link: Pascals triangle: https://leetcode.com/problems/find-triangular-sum-of-an-array/discuss/1909302/Pascal-Triangle

Approach: For solving this problem, I thought to use a bit of math to look at an attempt to find an efficient solution. I know that each number in the array contributes to the final sum a certain number of times. We can visualize how to figure out factors for each number using Pascal’s triangle.

For test case [1, 2, 3, 4, 5], we will get 1 * 1 + 2 * 4 + 3 * 6 + 4 * 4 + 5 * 1 = 1 + 8 + 18 + 16 + 5 = 48, or 8 after modulo 10.

The bottom row of Pascal’s triangle are binomial coefficients, which can be computed as nCr(n - 1, i). The nCr can also be computed iteratively as nCr(r + 1) = nCr(r) * (n - r) / (r + 1).

Optimal TC: Guy claims O(N), but I think most everyone else is doing it in O(N^2)

Optimal SC: O(N)

Question 26

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with 2 children) correspond to the operators ‘+’ (addition), ‘-‘ (subtraction), ‘*’ (multiplication), and ‘/’ (division).

For each internal node with operator o, the infix expression it represents is (A o B), where A is the expression the left subtree represents and B is the expression the right subtree represents.

You are given a string s, an infix expression containing operands, the operators described above, and parentheses ‘(‘ and ‘)’.

Return any valid binary expression tree, whose in-order traversal reproduces s after omitting the parenthesis from it.

Please note that order of operations applies in s. That is, expressions in parentheses are evaluated first, and multiplication and division happen before addition and subtraction.

Operands must also appear in the same order in both s and the in-order traversal of the tree.

Example 1:

Input: s = “3*4-2*5”

Output: [-,*,*,3,4,2,5]

Explanation: The tree above is the only valid tree whose inorder traversal produces s.

Example 2:

Input: s = “2-3/(5*2)+1”

Output: [+,-,1,2,/,null,null,null,null,3,*,null,null,5,2]

Explanation: The inorder traversal of the tree above is 2-3/5*2+1 which is the same as s without the parenthesis. The tree also produces the correct result and its operands are in the same order as they appear in s. The tree below is also a valid binary expression tree with the same inorder traversal as s, but it not a valid answer because it does not evaluate to the same value. The third tree below is also not valid. Although it produces the same result and is equivalent to the above trees, its inorder traversal does not produce s and its operands are not in the same order as s.

Example 3:

Input: s = “1+2+3+4+5”

Output: [+,+,5,+,4,null,null,+,3,null,null,1,2]

Explanation: The tree [+,+,5,+,+,null,null,1,2,3,4] is also one of many other valid trees.

Constraints:

• 1 <= s.length <= 100
• s consists of digits and the characters ‘+’, ‘-‘, ‘*’, and ‘/’.
• Operands in s are exactly 1 digit.
• It is guaranteed that s is a valid expression.

Answer 26

Topic: Stacks and Trees (Hard - Build Binary Expression Tree From Infix Expression)

**Discuss Link**: There is a parser solution and a 2-stack solution:
2 Stacks (Make sure to use the ‘while loop’ solution commented below: [https://leetcode.com/problems/build-binary-expression-tree-from-infix-expression/discuss/949053/Python3-Two-stacks-approach-ops-%2B-nums-stacks](https://leetcode.com/problems/build-binary-expression-tree-from-infix-expression/discuss/949053/Python3-Two-stacks-approach-ops-%2B-nums-stacks)

Parser Solution: https://leetcode.com/problems/build-binary-expression-tree-from-infix-expression/discuss/864596/Python-Standard-parser-implementation

Approach (2 Stacks): For this problem I want to maintain an ops stack and a nums stack.
When we see ‘+-‘, if the top of the ops stack is ‘+-*/’, we can merge the top two nodes in the nums stack using the top node in the ops stack.
When we see ‘*/’, we cannot compute the previous ‘+-‘ because of the priority. So only if we see ‘*/’, we can merge the top two nodes in the nums stack using the top node in the ops stack.
When we see ‘)’, we merge the nodes until the top of the ops stack is ‘(‘.
Finally, we merge the rest of the nodes.

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 27

Given a string s and a dictionary of strings wordDict, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = “catsanddog”, wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]

Output: [“cats and dog”,”cat sand dog”]

Example 2:

Input: s = “pineapplepenapple”, wordDict = [“apple”,”pen”,”applepen”,”pine”,”pineapple”]

Output: [“pine apple pen apple”,”pineapple pen apple”,”pine applepen apple”]

Explanation: Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”]

Output: []

Constraints:

• 1 <= s.length <= 20
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 10
• s and wordDict[i] consist of only lowercase English letters.
• All the strings of wordDict are unique.

Answer 27

Topic: Dynamic Programming (Hard - Word Break II)

Discuss Link: Can be solved with DFS, DP or Backtracking: Best solution I found was a bottom-up DP with solid explanation here: https://leetcode.com/problems/word-break-ii/discuss/763221/Python-dp-solution-explained

DFS solution (3rd comment down ‘concise solution’: https://leetcode.com/problems/word-break-ii/discuss/44311/Python-easy-to-understand-solution

Approach: For this problem we need to give all possible splits for each word. First I chose to put all words into set and create two lists:

dp_solution[i] is all possible splits for first i symbols of s
dp[i] is indicator if we can split word or not.
Also we create these two lists with size (n+1) to handle border cases, in dp[-1] we will keep result for empty string “”.

1. First step is to check if our string can be split at all. To candle strings like aaaaa…aaab, with wordDict = [a, aa, aaa, …, aa..aa]. In this case answer will be no, but if we try to build solution directly we will get MLE.
2. Now, we do one more pass over data and start to build solutions: if we found that s[j: k + 1] in wordSet, then for every already built solution sol in dp_solution[j-1] we can add it to dp_solution[k].
3. Finally, we have some extra spaces in the beginning of each solution, and instead of last element [-1] we need to return previous [-2], so we return return [s[1:] for s in dp_solution[-2]]

Optimal TC: O(N^2 * M)

Optimal SC: O(N^2)

Question 28

There is a long table with a line of plates and candles arranged on top of it. You are given a 0-indexed string s consisting of characters ‘*’ and ‘|’ only, where a ‘*’ represents a plate and a ‘|’ represents a candle.

You are also given a 0-indexed 2D integer array queries where queries[i] = [left_i, right_i] denotes the substring s[left_i…right_i] (inclusive). For each query, you need to find the number of plates between candles that are in the substring. A plate is considered between candles if there is at least one candle to its left and at least one candle to its right in the substring.

• For example, s = “||**||**|*”, and a query [3, 8] denotes the substring “*||**|”. The number of plates between candles in this substring is 2, as each of the two plates has at least one candle in the substring to its left and right.

Return an integer array answer where answer[i] is the answer to the i^th query.

Example 1:

[PIC]

Input: s = “**|**|***|”, queries = [[2,5],[5,9]]

Output: [2,3]

Explanation: - queries[0] has two plates between candles. - queries[1] has three plates between candles.

Example 2:

[PIC]

Input: s = “***|**|*****|**||**|*”, queries = [[1,17],[4,5],[14,17],[5,11],[15,16]]

Output: [9,0,0,0,0]

Explanation: - queries[0] has nine plates between candles. - The other queries have zero plates between candles.

Constraints:

• 3 <= s.length <= 10⁵
• s consists of ‘*’ and ‘|’ characters.
• 1 <= queries.length <= 10⁵
• queries[i].length == 2
• 0 <= left_i <= right_i < s.length

Answer 28

Topic: Binary Search (Medium - Plates Between Candles)

Discuss Link: https://leetcode.com/problems/plates-between-candles/discuss/1549018/JavaC%2B%2BPython-Binary-Search-and-O(Q-%2B-N)-Solution

Lee has a decent simple implementation with amazing explanation, but there is a more easy to read approach using binary search and prefix sum as well:
https://leetcode.com/problems/plates-between-candles/discuss/1549015/Python3-binary-search-and-O(N)-approach

Approach: Prefix sum, may need to dig deeper for explanation if this is pulled for OA

Optimal TC: O(N + Q)

Optimal SC: O(N + Q)

Question 29

The boundary of a binary tree is the concatenation of the root, the left boundary, the leaves ordered from left-to-right, and the reverse order of the right boundary.

The left boundary is the set of nodes defined by the following:

• The root node’s left child is in the left boundary. If the root does not have a left child, then the left boundary is empty.
• If a node in the left boundary and has a left child, then the left child is in the left boundary.
• If a node is in the left boundary, has no left child, but has a right child, then the right child is in the left boundary.
• The leftmost leaf is not in the left boundary.

The right boundary is similar to the left boundary, except it is the right side of the root’s right subtree. Again, the leaf is not part of the right boundary, and the right boundary is empty if the root does not have a right child.

The leaves are nodes that do not have any children. For this problem, the root is not a leaf.

Given the root of a binary tree, return the values of its boundary.

Example 1:

Input: root = [1,null,2,3,4]

Output: [1,3,4,2]

Explanation:- The left boundary is empty because the root does not have a left child. - The right boundary follows the path starting from the root’s right child 2 -> 4. 4 is a leaf, so the right boundary is [2]. - The leaves from left to right are [3,4]. Concatenating everything results in [1] + [] + [3,4] + [2] = [1,3,4,2].

Example 2:

Input: root = [1,2,3,4,5,6,null,null,null,7,8,9,10]

Output: [1,2,4,7,8,9,10,6,3]

Explanation:- The left boundary follows the path starting from the root’s left child 2 -> 4. 4 is a leaf, so the left boundary is [2]. - The right boundary follows the path starting from the root’s right child 3 -> 6 -> 10. 10 is a leaf, so the right boundary is [3,6], and in reverse order is [6,3]. - The leaves from left to right are [4,7,8,9,10]. Concatenating everything results in [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3].

Answer 29

Topic: DFS / Tree traversal (Medium - Boundary of Binary Tree)

Discuss Link: https://leetcode.com/problems/boundary-of-binary-tree/discuss/101308/python-dfs-solution

Alternative with better explanation: https://leetcode.com/problems/boundary-of-binary-tree/discuss/101309/Python-Straightforward-with-Explanation

Approach: I went with three separate traversals here to calculate the boundary of the tree accurately, all of which are Depth first searches. First I went with a pre-order traversal for left boundary, then an in-order for bottom boundary (because it’s basically sea-sawing the bottom) and finally post-order (but going right node first) for the right boundary.

Optimal TC: O(N)

Optimal SC: O(N)

Question 30

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]

Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 10⁴
• 0 <= height[i] <= 10⁵

Answer 30

Topic: Two Pointers (Hard - Trapping Rain Water) 🔙(Neetcode 150)

Source: Neetcode solution

Approach: Best solved with a two pointer approach, but this can also be solved with Brute force, Stacks and Dynamic programming although less optimal. Trick here is to understand how maxLeft and maxRight work. An ith bar can trap the water if and only if there exists a higher bar to the left and a higher bar to the right of ith bar. To calculate how much amount of water the ith bar can trap, we need to look at the maximum height of the left bar and the maximum height of the right bar, then
we can calculate the water level. if maxLeft < maxRight we move the left pointer, update the new maxLeft against height[left] and then we know it can trap an amount of water and we can update our answer with maxLeft - height[left]. Else (maxRight ≤ maxLeft) we move the right pointer, update the new maxRight against height[right] and then we know it can trap an amount of water and we can update our answer with maxRight - height[right]

Optimal TC: O(N) time

Optimal SC: O(1) space

Question 31

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: [0,1] .

Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1].

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

Output: [0,2,1,3]

Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []

Output: [0]

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= numCourses * (numCourses - 1)
• prerequisites[i].length == 2
• 0 <= a_i, b_i < numCourses
• a_i != b_i
• All the pairs [a_i, b_i] are distinct.

Answer 31

Topic: DFS Graph (Medium - Course Schedule II) 🔙Neetcode 150!

Source: Neetcode Solution with comments

Approach:
A course has 3 possible states, as noted:
1. Visited –> course has been added to the result
2. Visiting –> course not added to result, but added to curr cycle
3. Unvisited –> course not added to result or cycle

First I want to create a hashmap to store courses and map each course to the prereq list. I will also want to create 1 set to store visited vertices and 1 set for a vertices along the current path. I will then run a DFS on all course in case we have disconnected graph. (Can add on to approach as I have several comments within the code)

Optimal TC: O(V+E) where V represents the number of vertices and E represents the number of edges. Essentially we iterate through each node and each vertex in the graph once and only once.

Optimal SC: O(V+E) where V represents the number of vertices and E represents the number of edges.

Question 32

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 10⁹ + 7.

Example 1:

Input: arr = [3,1,2,4]

Output: 17

Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.

Example 2:

Input: arr = [11,81,94,43,3]

Output: 444

Constraints:

• 1 <= arr.length <= 3 * 10⁴
• 1 <= arr[i] <= 3 * 10⁴

Answer 32

Topic: Stacks (Medium - Sum of Subarray Minimums)

Discuss Link: https://leetcode.com/problems/sum-of-subarray-minimums/discuss/257811/Python-O(n)-slightly-easier-to-grasp-solution-(explained)

Approach (may need to find a better explanation): I use a monotonous non-decreasing stack to store the left boundary and right boundary where a number is the minimal number in the sub-array

e.g. given [3,1,2,4],
For 3, the boundary is: | 3 | …
For 1, the boundary is: | 3 1 2 4 |
For 2, the boundary is: … | 2 4 |
For 4, the boundary is: … | 4 |

The times a number n occurs in the minimums is |left_bounday-indexof(n)| * |right_bounday-indexof(n)|

The total sum is sum([n * |left_bounday - indexof(n)| * |right_bounday - indexof(n)| for n in array])

After a number n pops out from an increasing stack, the current stack top is n’s left_boundary, the number forcing n to pop is n’s right_boundary.

A tricky here is to add MIN_VALUE at the head and end.

Optimal TC: O(N)

Optimal SC: O(N)

Question 33

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Example 2:

Input: strs = [””]

Output: [[””]]

Example 3:

Input: strs = [“a”]

Output: [[“a”]]

Constraints:

• 1 <= strs.length <= 10⁴
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

Answer 33

Topic: Arrays & Hashing (Medium - Group Anagrams) 🔙Neetcode 150

Approach:

• Initial thought: sort the strings and store in a hashmap. Make sure to convert strings to a tuple before setting that as the key of the map. O(N Log N)
• Optimal solution: would be to initialize an array with 26 zeroes and use the ascii trick “ord(char) - ord(‘a’)” to set the key value + 1. Then convert to tuple again and append to result map

Optimal TC: O(N * K) time - where N is the length of strs, and K is the maximum length of a string in strs

Optimal SC: O(N * K) space - the total information content stored in the results

Question 34

You are assigned to put some amount of boxes onto one truck. You are given a 2D array boxTypes, where boxTypes[i] = [numberOfBoxes_i, numberOfUnitsPerBox_i]:

• numberOfBoxes_i is the number of boxes of type i.
• numberOfUnitsPerBox_i is the number of units in each box of the type i.

You are also given an integer truckSize, which is the maximum number of boxes that can be put on the truck. You can choose any boxes to put on the truck as long as the number of boxes does not exceed truckSize.

Return the maximum total number of units that can be put on the truck.

Example 1:

Input: boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4

Output: 8

Explanation: There are: - 1 box of the first type that contains 3 units. - 2 boxes of the second type that contain 2 units each. - 3 boxes of the third type that contain 1 unit each. You can take all the boxes of the first and second types, and one box of the third type. The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.

Example 2:

Input: boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10

Output: 91

Constraints:

• 1 <= boxTypes.length <= 1000
• 1 <= numberOfBoxes_i, numberOfUnitsPerBox_i <= 1000
• 1 <= truckSize <= 10⁶

Answer 34

Topic: Arrays + Bucket Sort + Greedy (Easy - Maximum Units on a Truck)

Discuss Link: Counting/bucket sort version with good explanation: https://leetcode.com/problems/maximum-units-on-a-truck/discuss/999125/JavaPython-3-Sort-by-the-units-then-apply-greedy-algorithm

Approach:

Intuition:

The constraint that “boxes per unit” will be max 1000 allows us to use 1000 buckets to sort by boxes per unit. Ie., we can create an array where the indices represent 0 boxes per unit, 1 boxes per unit, 2 boxes per unit, 3 boxes per unit, … 1000 boxes per unit. And the buckets[i] will represent the number of boxes at each index.

Optimal TC: O(N)

Optimal SC: O(N)

Question 35

The distance of a pair of integers a and b is defined as the absolute difference between a and b.

Given an integer array nums and an integer k, return the k^th smallest distance among all the pairs nums[i] and nums[j] where 0 <= i < j < nums.length.

Example 1:

Input: nums = [1,3,1], k = 1

Output: 0

Explanation: Here are all the pairs: (1,3) -> 2 (1,1) -> 0 (3,1) -> 2 Then the 1^st smallest distance pair is (1,1), and its distance is 0.

Example 2:

Input: nums = [1,1,1], k = 2

Output: 0

Example 3:

Input: nums = [1,6,1], k = 3

Output: 5

Constraints:

• n == nums.length
• 2 <= n <= 10⁴
• 0 <= nums[i] <= 10⁶
• 1 <= k <= n * (n - 1) / 2

Answer 35

Topic: Binary Search + sliding window (Hard - Find K-th Smallest Pair Distance)

Discuss Link: https://leetcode.com/problems/find-k-th-smallest-pair-distance/discuss/769705/Python-Clear-explanation-Powerful-Ultimate-Binary-Search-Template.-Solved-many-problems

Approach: Let’s binary search for the answer. It’s definitely in the range [0, W], where W = max(nums) - min(nums)]. Let enough(distance) be true if and only if there are k or more pairs with distance less than or equal to guess. We will focus on evaluating our enough function quickly. We will use a sliding window approach to count the number of pairs with distance <= guess. For every possible right, we maintain the loop invariant: left is the smallest value such that nums[right] - nums[left] <= guess. Then, the number of pairs with right as it’s right-most endpoint is right - left, and we add all of these up.

Optimal TC: O(NlogW + NlogN), where N is the length of nums, and W is equal to nums[nums.length - 1] - nums[0]. The logW factor comes from our binary search, and we do O(N) work inside our call to possible. The final O(NlogN) factor comes from sorting.

Optimal SC: O(1)

Question 36

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

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

Output: [1,2,3,null,null,4,5]

Example 2:

Input: root = []

Output: []

Constraints:

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

Answer 36

Topic: DFS Trees (Hard - Serialize and Deserialize Binary Tree) 🔙Neetcode 150!

Source: Neetcode Solution

Approach: Several comments in the code, but essentially we run DFS on left and right

Optimal TC: O(N) where N is the number of nodes, i.e. the size of tree.

Optimal SC: O(N) in both serialization and deserialization functions, we keep the entire tree, either at the beginning or at the end

Question 37

You are starving and you want to eat food as quickly as possible. You want to find the shortest path to arrive at any food cell.

You are given an m x n character matrix, grid, of these different types of cells:

• ’*’ is your location. There is exactly one’*’ cell.
• ’#’ is a food cell. There may be multiple food cells.
• ‘O’ is free space, and you can travel through these cells.
• ‘X’ is an obstacle, and you cannot travel through these cells.

You can travel to any adjacent cell north, east, south, or west of your current location if there is not an obstacle.

Return the length of the shortest path for you to reach any food cell. If there is no path for you to reach food, return -1.

Example 1:

[PIC]

Input: grid = [[“X”,”X”,”X”,”X”,”X”,”X”],[“X”,”*”,”O”,”O”,”O”,”X”],[“X”,”O”,”O”,”#”,”O”,”X”],[“X”,”X”,”X”,”X”,”X”,”X”]]

Output: 3

Explanation: It takes 3 steps to reach the food.

Example 2:

[PIC]

Input: grid = [[“X”,”X”,”X”,”X”,”X”],[“X”,”*”,”X”,”O”,”X”],[“X”,”O”,”X”,”#”,”X”],[“X”,”X”,”X”,”X”,”X”]]

Output: -1

Explanation: It is not possible to reach the food.

Example 3:

[PIC]

Input: grid = [[“X”,”X”,”X”,”X”,”X”,”X”,”X”,”X”],[“X”,”*”,”O”,”X”,”O”,”#”,”O”,”X”],[“X”,”O”,”O”,”X”,”O”,”O”,”X”,”X”],[“X”,”O”,”O”,”O”,”O”,”#”,”O”,”X”],[“X”,”X”,”X”,”X”,”X”,”X”,”X”,”X”]] x

Output: 6

Explanation: There can be multiple food cells. It only takes 6 steps to reach the bottom food.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[row][col] is ‘*’, ‘X’, ‘O’, or ‘#’.
• The grid contains exactly one’*’.

Answer 37

Topic: BFS Graph (Medium - Shortest Path to Get Food)

Discuss Link: https://leetcode.com/problems/shortest-path-to-get-food/discuss/1051229/Easy-%2B-Clean-Python-beats-90-with-Comments!

Approach: BFS traversal of graph approach since this is shortest path problem. Start by iterating through graph until we find the starting point then add the starting point to the queue and marking the cell as visited. Continue by processing the queue and checking neighbors in all 4 directions. For each neighbor we need to ensure that the new row and col is in the grid and an it is unvisited or a food node. If we found a food node we can return as we are finished, otherwise if the cell is in bounds we will add it to the queue to be processed on the next iteration.

Optimal TC: O(M*N)

Optimal SC: O(M*N)

Question 38

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is “”.

Example 1:

Input: s = “banana”

Output:“ana”

Example 2:

Input: s = “abcd”

Output:””

Constraints:

• 2 <= s.length <= 3 * 10⁴
• s consists of lowercase English letters.

Answer 38

Topic: Binary Search (Hard - Longest Duplicate Substring)

Discuss Link: https://leetcode.com/problems/longest-duplicate-substring/discuss/290890/Python-Binary-Search-%2B-Rabin-Karp-Solution

Approach:

Binary search algorithm

Use binary search by a substring length to check lengths from 1 to N left = 1, right = N. While left != right:

L = left + (right - left) / 2

If search(L) != -1 (i.e. there is a duplicate substring), left = L + 1

Otherwise (no duplicate substring), right = L.

Return a duplicate string of length left - 1, or an empty string if there is no such a string.

Rabin-Karp algorithm

Compute the hash of the substring consisting of the first L characters of string S.

We will initialize the hash map of already seen substrings with this hash value as a key and a list containing the starting index of the substring (0) as the value.

The reason we store the first index of the substring is so that if we see this hash value again, we can compare the current substring to each substring that has the same hash value to see if the two strings actually match or if this is a hash collision.

Every time we compare two strings will cost O(L) time. If we designed a very poor hash function or picked a very weak modulus value (like 1), we could potentially spend O(L(N - L)^2) time comparing each substring of length L to all previous substrings of length L on each call to search.

Fortunately, the hash function we are using guarantees that there will not be any collisions between hash values that are less than MOD (before taking the modulus). Furthermore, selecting a large, prime modulus helps create a more uniform distribution of the hash values that are greater than MOD. So the probability of two hash values colliding is very small, and on average, we expect the number of collisions to be negligible. Therefore, we can expect the search function to take O(N) time on average.

Iterate over the start position of each substring in S from 11 to N - L. Note we already initialized our hashmap with the substring starting at index zero.

Compute the rolling hash based on the previous hash value.

If the hash is in t

Optimal TC: O(NlogN)

Optimal SC: O(N)

Question 39

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

Example 1:

[PIC]

Input: board = [[“o”,”a”,”a”,”n”],[“e”,”t”,”a”,”e”],[“i”,”h”,”k”,”r”],[“i”,”f”,”l”,”v”]], words = [“oath”,”pea”,”eat”,”rain”]

Output: [“eat”,”oath”]

Example 2:

[PIC]

Input: board = [[“a”,”b”],[“c”,”d”]], words = [“abcb”]

Output: []

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 12
• board[i][j] is a lowercase English letter.
• 1 <= words.length <= 3 * 10⁴
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.
• All the strings of words are unique.

Answer 39

Topic: Tries + backtracking (Hard - Word Search II) 🔙Neetcode 150!

Discuss Link: Done, could use more comments for neetcode version and it also gets a TLE

Alternate solution: https://leetcode.com/problems/word-search-ii/discuss/59790/Python-dfs-solution-(directly-use-Trie-implemented).

Approach: Basically use a Trie data structure to store the words in the dictionary, which would be used for the matching process later. Starting from each cell, we start the backtracking exploration (i.e. backtracking(cell)), if there exists any word in the dictionary that starts with the letter in the cell. During the recursive function call backtracking(cell), we explore the neighbor cells (i.e. neighborCell) around the current cell for the next recursive call backtracking(neighborCell). At each call, we check if the sequence of letters that we traverse so far matches any word in the dictionary, with the help of the Trie data structure that we built at the beginning.

Optimal TC: O(N)

Optimal SC: O(N)

Question 40

Given the postfix tokens of an arithmetic expression, build and return the binary expression tree that represents this expression.

Postfix notation is a notation for writing arithmetic expressions in which the operands (numbers) appear before their operators. For example, the postfix tokens of the expression 4*(5-(7+2)) are represented in the array postfix = [“4”,”5”,”7”,”2”,”+”,”-“,”*”].

The class Node is an interface you should use to implement the binary expression tree. The returned tree will be tested using the evaluate function, which is supposed to evaluate the tree’s value. You should not remove the Node class; however, you can modify it as you wish, and you can define other classes to implement it if needed.

A binary expression tree is a kind of binary tree used to represent arithmetic expressions. Each node of a binary expression tree has either zero or two children. Leaf nodes (nodes with 0 children) correspond to operands (numbers), and internal nodes (nodes with two children) correspond to the operators ‘+’ (addition), ‘-‘ (subtraction), ‘*’ (multiplication), and ‘/’ (division).

It’s guaranteed that no subtree will yield a value that exceeds 10⁹ in absolute value, and all the operations are valid (i.e., no division by zero).

Follow up: Could you design the expression tree such that it is more modular? For example, is your design able to support additional operators without making changes to your existing evaluate implementation?

Example 1:

Input: s = [“3”,”4”,”+”,”2”,”*”,”7”,”/”]

Output: 2

Explanation: this expression evaluates to the above binary tree with expression ((3+4)*2)/7) = 14/7 = 2.

Example 2:

Input: s = [“4”,”5”,”2”,”7”,”+”,”-“,”*”]

Output: -16

Explanation: this expression evaluates to the above binary tree with expression 4*(5-(2+7)) = 4*(-4) = -16.

Constraints:

• 1 <= s.length < 100
• s.length is odd.
• s consists of numbers and the characters ‘+’, ‘-‘, ‘*’, and ‘/’.
• If s[i] is a number, its integer representation is no more than 10⁵.
• It is guaranteed that s is a valid expression.
• The absolute value of the result and intermediate values will not exceed 10⁹.
• It is guaranteed that no expression will include division by zero.

Answer 40

Topic: Trees Design + DFS and Stack (Medium - Design an Expression Tree With Evaluate Function)

Discuss Link: https://leetcode.com/problems/design-an-expression-tree-with-evaluate-function/discuss/1402172/Python-or-Stack-or-Explained

Approach: I decided to emulate a DFS process, all digits are at leaf nodes; otherwise we will calculate the result recursively. Building the tree based on postfix is accomplished with the help of a stack structure. Algorithm:

• We will iterate through each value in postfix array
• if its an integer, just create a node with that integer value and append it to your stack
• if its an operator:
  
  • create a node with that operator as its value
  • pop the first two elements in your stack
    
    • This is always guaranteed to work because postfix provides you a valid tree
  • store right tree then left tree
  • If you did everything right, you are always guaranteed to have a stack of length 1 since everything should have been popped out but the root node

Optimal TC: O(N)

Optimal SC: O(N)

Question 41

Design a parking system for a parking lot. The parking lot has three kinds of parking spaces: big, medium, and small, with a fixed number of slots for each size.

Implement the ParkingSystem class:

• ParkingSystem(int big, int medium, int small) Initializes object of the ParkingSystem class. The number of slots for each parking space are given as part of the constructor.
• bool addCar(int carType) Checks whether there is a parking space of carType for the car that wants to get into the parking lot. carType can be of three kinds: big, medium, or small, which are represented by 1, 2, and 3 respectively. A car can only park in a parking space of its carType. If there is no space available, return false, else park the car in that size space and return true.

Example 1:

Input [“ParkingSystem”, “addCar”, “addCar”, “addCar”, “addCar”] [[1, 1, 0], [1], [2], [3], [1]]

Output [null, true, true, false, false]

Explanation ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0); parkingSystem.addCar(1); // return true because there is 1 available slot for a big car parkingSystem.addCar(2); // return true because there is 1 available slot for a medium car parkingSystem.addCar(3); // return false because there is no available slot for a small car parkingSystem.addCar(1); // return false because there is no available slot for a big car. It is already occupied.

Constraints:

• 0 <= big, medium, small <= 1000
• carType is 1, 2, or 3
• At most 1000 calls will be made to addCar

Answer 41

Topic: Design (Easy - Design Parking System)

Discuss Link: https://leetcode.com/problems/design-parking-system/discuss/876953/JavaC%2B%2BPython-3-Lines

Approach: Pretty straight forward. Use an array to store the small / medium / large spaces inside the constructor. Inside the addCar function we has 1, 2, 3 as integers to represent the car spaces. So basically we just do a self.spaces[int -1] to find the correct space and then we decrement the count each time we add a car. We will then return a logic statement that will return true if we still have available spots or false if we do not.

Optimal TC: O(1)

Optimal SC: O(1)

Question 42

You are given a 0-indexed binary string s which represents the types of buildings along a street where:

• s[i] = ‘0’ denotes that the i^th building is an office and
• s[i] = ‘1’ denotes that the i^th building is a restaurant.

As a city official, you would like to select 3 buildings for random inspection. However, to ensure variety, no two consecutive buildings out of the selected buildings can be of the same type.

• For example, given s = “00**1**1**0**1**”, we cannot select the 1^st, 3^rd, and 5^th buildings as that would form “0**11” which is not allowed due to having two consecutive buildings of the same type.

Return the number of valid ways to select 3 buildings.

Example 1:

Input: s = “001101”

Output: 6

Explanation: The following sets of indices selected are valid: - [0,2,4] from “0**0**1**1**0**1” forms “010” - [0,3,4] from “**0**01**10**1” forms “010” - [1,2,4] from “0**01**1**0**1” forms “010” - [1,3,4] from “0**0**1**10**1” forms “010” - [2,4,5] from “00**1**1**01**” forms “101” - [3,4,5] from “001**101” forms “101” No other selection is valid. Thus, there are 6 total ways.

Example 2:

Input: s = “11100”

Output: 0

Explanation: It can be shown that there are no valid selections.

Constraints:

• 3 <= s.length <= 10⁵
• s[i] is either ‘0’ or ‘1’.

Answer 42

Topic: Dynamic Programming / Prefix Sum (Medium - Number of Ways to Select Buildings)

Discuss Link: https://leetcode.com/problems/number-of-ways-to-select-buildings/discuss/1907179/JavaPython-3-One-pass-T-O(n)-S-O(1)-codes-and-follow-up-w-brief-explanation-and-analysis.

Approach:

Traverse the input s:

• If encountering 0, count subsequences ending at current 0: 0, 10 and 010’s; The number of 10 depends on how many 1s before current 0, and the number of 010 depends on how many 01 before current 0.
• Similarly, If encountering 1, count subsequences ending at current 1: 1, 01 and 101’s; The number of 01 depends on how many 0s before current 1, and the number of 101 depends on how many 10 before current 1

Optimal TC: O(N)

Optimal SC: O(1)

Question 43

Assume the following rules are for the tic-tac-toe game on an n x n board between two players:

1. A move is guaranteed to be valid and is placed on an empty block.
2. Once a winning condition is reached, no more moves are allowed.
3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

• TicTacToe(int n) Initializes the object the size of the board n.
• int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move.

Example 1:

Input[“TicTacToe”, “move”, “move”, “move”, “move”, “move”, “move”, “move”] [[3], [0, 0, 1], [0, 2, 2], [2, 2, 1], [1, 1, 2], [2, 0, 1], [1, 0, 2], [2, 1, 1]]

Output[null, 0, 0, 0, 0, 0, 0, 1]

ExplanationTicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is “X” and player 2 is “O” in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | | ticTacToe.move(0, 2, 2); // return 0 (no one wins) |X| |O| | | | | // Player 2 makes a move at (0, 2). | | | | ticTacToe.move(2, 2, 1); // return 0 (no one wins) |X| |O| | | | | // Player 1 makes a move at (2, 2). | | |X| ticTacToe.move(1, 1, 2); // return 0 (no one wins) |X| |O| | |O| | // Player 2 makes a move at (1, 1). | | |X| ticTacToe.move(2, 0, 1); // return 0 (no one wins) |X| |O| | |O| | // Player 1 makes a move at (2, 0). |X| |X| ticTacToe.move(1, 0, 2); // return 0 (no one wins) |X| |O| |O|O| | // Player 2 makes a move at (1, 0). |X| |X| ticTacToe.move(2, 1, 1); // return 1 (player 1 wins) |X| |O| |O|O| | // Player 1 makes a move at (2, 1). |X|X|X|

Constraints:

• 2 <= n <= 100
• player is 1 or 2.
• 0 <= row, col < n
• (row, col) are unique for each different call to move.
• At most n² calls will be made to move.

Answer 43

Topic: 2D Array / Design (Medium - Design Tic-Tac-Toe)

Discuss Link: Minor optimization in comments: https://leetcode.com/problems/design-tic-tac-toe/discuss/81932/Python-13-lines-easy-to-understand

Approach:

• Record the number of moves for each rows, columns, and two diagonals.
• For each move, we -1 for each player 1’s move and +1 for player 2’s move.
• Then we just need to check whether any of the recorded numbers equal to n or -n.

Optimal TC: O(1)

Optimal SC: O(N)

Question 44

You are given an n x n integer matrix board where the cells are labeled from 1 to n² in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

You start on square 1 of the board. In each move, starting from square curr, do the following:

• Choose a destination square next with a label in the range [curr + 1, min(curr + 6, n²)].
  
  • This choice simulates the result of a standard 6-sided die roll: i.e., there are always at most 6 destinations, regardless of the size of the board.
• If next has a snake or ladder, you must move to the destination of that snake or ladder. Otherwise, you move to next.
• The game ends when you reach the square n².

A board square on row r and column c has a snake or ladder if board[r][c] != -1. The destination of that snake or ladder is board[r][c]. Squares 1 and n² do not have a snake or ladder.

Note that you only take a snake or ladder at most once per move. If the destination to a snake or ladder is the start of another snake or ladder, you do not follow the subsequent snake or ladder.

• For example, suppose the board is [[-1,4],[-1,3]], and on the first move, your destination square is 2. You follow the ladder to square 3, but do not follow the subsequent ladder to 4.

Return the least number of moves required to reach the square n². If it is not possible to reach the square, return -1.

Example 1:

[PIC]

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]

Output: 4

Explanation: In the beginning, you start at square 1 (at row 5, column 0). You decide to move to square 2 and must take the ladder to square 15. You then decide to move to square 17 and must take the snake to square 13. You then decide to move to square 14 and must take the ladder to square 35. You then decide to move to square 36, ending the game. This is the lowest possible number of moves to reach the last square, so return 4.

Example 2:

Input: board = [[-1,-1],[-1,3]]

Output: 1

Constraints:

• n == board.length == board[i].length
• 2 <= n <= 20
• grid[i][j] is either -1 or in the range [1, n²].
• The squares labeled 1 and n² do not have any ladders or snakes.

Answer 44

Topic: BFS Graph (Medium - Snakes and Ladders)

Discuss Link: https://leetcode.com/problems/snakes-and-ladders/discuss/173663/Python-BFS-solution

Approach: Transform grid into 1D array then run BFS? Not very detailed.

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 45

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, ‘+’, ‘-‘, ‘*’, ‘/’ operators, and open ‘(‘ and closing parentheses ‘)’. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2³¹, 2³¹ - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “1+1”

Output: 2

Example 2:

Input: s = “6-4/2”

Output: 4

Example 3:

Input: s = “2*(5+5*2)/3+(6/2+8)”

Output: 21

Constraints:

• 1 <= s <= 10⁴
• s consists of digits, ‘+’, ‘-‘, ‘*’, ‘/’, ‘(‘, and ‘)’.
• s is a valid expression.

Answer 45

Topic: Stack + Math (Hard - Basic Calculator III)

Discuss Link: Python 3 answer in comments: https://leetcode.com/problems/basic-calculator-iii/discuss/159550/Python-short-iterative-solution-with-brief-explanation

Approach:

The idea is to compute each independent item of the expression and then sum them up. For example in 3 - 4 / (4* 6 ), 3 is an item and -4/(4*6) is also an item.

We use num as the variable of the current operand, op as the operation of the partial expression not yet evaluated (the operation before num). Then iterative go though each char, and check following condition:

• If the char is a digit, we continue construct number with it.
• If the char is one of +, -, *, /, ), we have reached end of an partial expression. so we evaluate the result of the partial expression. If the char is ), we have to pop all the items out until we reach the last op before (, and then evaluate the partial expression. We then set op as current char.
• If the char is (, we need to push the op in stack, and reset op to +
• Finally, after we reach the end of the string, we do another evaluation of the expression to include the last num.

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed

Question 46

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random –> Y, then for the corresponding two nodes x and y in the copied list, x.random –> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

• val: an integer representing Node.val
• random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

[PIC]

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

[PIC]

Input: head = [[1,1],[2,1]]

Output: [[1,1],[2,1]]

Example 3:

[PIC]

Input: head = [[3,null],[3,0],[3,null]]

Output: [[3,null],[3,0],[3,null]]

Constraints:

• 0 <= n <= 1000
• -10⁴ <= Node.val <= 10⁴
• Node.random is null or is pointing to some node in the linked list.

Answer 46

Topic: Linked List (Medium - Copy List with Random Pointer) 🔙Completed already (related to Neetcode 150?)

Discuss Link: Neetcode solution with comments

Approach:

• First pass to make basic copy of list
• Reset curr back to head of original list
• Do a second pass to set the pointers of the new list

Optimal TC: O(N) unconfirmed

Optimal SC: O(N) unconfirmed