Amazon OA Flashcards
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 <= 104
- s consists of lowercase English letters.
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
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 ith 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 109 + 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 <= 105
- 1 <= strength[i] <= 109
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:
- Find next smallest on the right
- Find next smallest or equal on the left.
- For each array[i] as the minimum, find the possible subarray sums
Optimal TC: O(N) confirmed
Optimal SC: O(N) confirmed
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 <= 105
- s consists of uppercase English letters only.
Topic: Dynamic Programming (Hard - Count Unique Characters of All Substrings of a Given String)
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:
- insert “(“ somewhere between the first and second A
- 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
- index[26][2] record last two occurrence index for every upper characters.
- Initialize all values in index to -1.
- Loop on string S, for every character c, update its last two occurrence index to index[c].
- 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)
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] <= 109
- 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.
Topic: Sorting (Medium - Analyze User Website Visit Pattern)
**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
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
- -109 <= nums[i] <= 109
Follow-up: Could you find a solution with O(n) time complexity?
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
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:
- The letter-logs come before all digit-logs.
- The letter-logs are sorted lexicographically by their contents. If their contents are the same, then sort them lexicographically by their identifiers.
- 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.
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
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 <= 104
- 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) <= 105
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
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 * 104
- All the strings of products are unique.
- products[i] consists of lowercase English letters.
- 1 <= searchWord.length <= 1000
- searchWord consists of lowercase English letters.
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
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 <= 104
- 0 <= value <= 105
- At most 2 * 105 calls will be made to get and put.
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.
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 ith 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 <= 105
- 0 <= damage[i] <= 105
- 0 <= armor <= 105
Topic: Array + Greedy (Medium - Minimum Health to Beat Game)
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
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’.
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)
Given an array of points where points[i] = [xi, yi] 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., √(x1 - x2)2 + (y1 - y2)2).
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 <= 104
- -104 < xi, yi < 104
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)
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> … -> sk such that:
- Every adjacent pair of words differs by a single letter.
- Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
- sk == 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.
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)
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 <= 231 - 1
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
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.
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)
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 <= 105
- s consists of lowercase English letters.
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)
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.
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
Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], 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 <= 104
- 0 <= starti < endi <= 106
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)
