Neetcode 150 Flashcards
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
Constraints:
- 1 <= nums.length <= 105
- -109 <= nums[i] <= 109
Topic: Arrays & Hashing (Easy - Contains Duplicate)
Hint: This can solved several ways:
- Brute Force (checks all values against all other values in the num array): O(N^2)
- Sorting the array first then check for dups in a single pass: O(N Log N)
- Optimal: Store in a set and return true once a dup is found when comparing against the set O(N)
Optimal TC: O(N)
Optimal SC: O(N)
Given two strings s and t, return true if t is an anagram of s, and false otherwise. 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: s = “anagram”, t = “nagaram”
Output: true
Example 2:
Input: s = “rat”, t = “car”
Output: false
Constraints:
- 1 <= s.length, t.length <= 5 * 104
- s and t consist of lowercase English letters.
Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?
Topic: Arrays & Hashing (Easy - Valid Anagram)
Hint: This can be solved two ways:
- Edge case: don’t forget to check the length of each string and return false if they are different
- First idea would to just be sorting both strings first then compare on return: O(N Log N)
- Optimal: Use two hashmaps, countS and countT. First iteration use the countS.get(s[i], 0) trick on both maps
- Final loop, check each char if countS[char] != countT.get(char, 0): return False
Optimal TC: O(N) time
Optimal SC: O(N) space
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6 Output: [1,2]
Example 3:
Input: nums = [3,3], target = 6 Output: [0,1]
Constraints:
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- Only one valid answer exists.
Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?
Topic: Arrays & Hashing (Easy - Two Sum)
Hint: This can solved two ways:
- Brute Force: just a double loop with j loop starting at i + 1. If target matches, return indices. O(N^2)
- Optimal: Store potential matches inside a hashmap (not a set). Then check if they are in the set on each iteration. If true return indices.
Optimal TC: O(N) time
Optimal SC: O(N) space
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 <= 104
- 0 <= strs[i].length <= 100
- strs[i] consists of lowercase English letters.
Topic: Arrays & Hashing (Medium - Group Anagrams)
- 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
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- k is in the range [1, the number of unique elements in the array].
- It is guaranteed that the answer is unique.
Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Topic: Arrays & Hashing (Medium - Top K Frequent Elements)
- Initial thought: This can be solved using a maxHeap (would be O(K Log N)) or an array + hashmap bucket sort solution (O(N)) . I am thinking the more optimal way could be solved by using two data structures and bucket sorting. First would be a hashmap to store the count. I would set the number as the key and increment the value each time I found that number within the provided list. The second structure would be an array of arrays to store the frequency, where we would store the number at the index of the frequency. freq = [[] for i in range(len(nums) + 1)] where we need + 1 for the edge case that we have only 1 element which would only have a 0th index if we did not have + 1 and cause an out of bounds error.
- Remember: first loop to count each occurrence of the chars: count[n] = 1 + count.get(n, 0)
- Remember: second loop stores the numbers at the index of the frequency freq[c].append(n)
- For the results loop: Decrement starting at end of the array, with 0 as the end point and -1 set to decrement: for i in range(len(freq) - 1, 0, -1): and inside the loop we need another for the array inside the array, for n in freq[i]: result.append(n) then we would end it if len(result) == k:
Optimal TC: O(N) time - bucket sort
Optimal SC: O(N) space
Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Constraints:
- 2 <= nums.length <= 105
- -30 <= nums[i] <= 30
- The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.
Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)
Topic: Arrays & Hashing (Medium - Product of Array Except Self)
Hint: This problem needs the Prefix/Postfix trick to be solved efficiently
- Initialize answer array: answer = [1] * (len(nums))
- For loop to Overwrite each element in answer array to the prefix: answer[i] = prefix
- Multiply the prefix by each element in the nums array: prefix *= nums[i]
- For loop (decrement 3x -1) to Multiply each element in the answer array by the postfix: answer[i] *= postfix
- Multiply the postfix by each element in the nums array: postfix *= nums[i]
Optimal TC: O(N) time
Optimal SC: O(1) space
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings. Implement the encode and decode methods. You are not allowed to solve the problem using any serialize methods (such as eval).
Example 1:
Input: dummy_input = [“Hello”,”World”]
Output: [“Hello”,”World”] Explanation:
Machine 1: Codec encoder = new Codec(); String msg = encoder.encode(strs); Machine 1 —msg—> Machine 2 Machine 2: Codec decoder = new Codec(); String[] strs = decoder.decode(msg);
Example 2:
Input: dummy_input = [””]
Output: [””]
Constraints:
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] contains any possible characters out of 256 valid ASCII characters.
Follow up: Could you write a generalized algorithm to work on any possible set of characters?
Topic: Arrays & Hashing (Medium - Encode and Decode Strings)
Hint:
- Encode with the length of the string + delimiter + the actual string.
- Return a single string with everything appended together
- For Decode need to initialize an empty array and a ptr: i = 0
- first loop we will loop while i < len(s):
- Inside the loop we will:
- Set J as a 2nd ptr so we can find the delimiter: j = i
- Loop until we find the delimiter: while s[j] != “#”
- increment j
- Once we are here, we have found the delimiter
- Now we Set Length to equal the single integer at i, up to j (the delimiter, but not inclusive): length = int(s[i:j])
- With the length we can append the entire string with array magic: decoded.append(s[j + 1: j + 1 + length])
- Donn’t forget to increment i for the next iteration: i = j + 1 + length
Optimal TC: O(N) time
Optimal SC: O(N) space
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9
Constraints:
- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109
Topic: Arrays & Hashing (Medium - Longest Consecutive Sequence)
Hint: Can brute force this, but it will timeout. Optimal solution involves a set and checking for the beginning of a sequence
- The trick here is to take the array and turn it into a set with numSet = set(nums)
- After turning the array into a set, we can check inside a for loop for the beginning of a sequence: if num - 1 not in numSet
- inside the if statement we do length = 1. Then we can just do another while loop to check for num + length and increment length
-
while (num + length) in numSet:
- length += 1
- Once we break out of the loop we will do a max update on the maxStreak with maxStreak = max(maxStreak, length)
-
while (num + length) in numSet:
Optimal TC: O(N) time
Optimal SC: O(N) space
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.
Example 1:
Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation:“amanaplanacanalpanama” is a palindrome.
Example 2:
Input: s = “race a car”
Output: false
Explanation:“raceacar” is not a palindrome.
Example 3:
Input: s = “ “
Output: true
Explanation: s is an empty string “” after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.
Constraints:
- 1 <= s.length <= 2 * 105
- s consists only of printable ASCII characters.
Topic: Two Pointers (Easy - Valid Palindrome)
Hint: Can python hack this with some easy code, but this is probably best solved with a two pointer approach
- First initiate your right and left pointers. Make sure to set right to len(str) - 1
- while left < right, check for non alnum chars. We can do this with: if not s[left].isalnum():
- left += 1
- continue
- Dupe this for the right pointer and don’t forget to continue
- Last if statement while check if s[left].lower() ≠ s[right].lower then return False
- Lastly don’t forget to update both left and right pointers before exiting the loop and returning True
Optimal TC: O(N) time
Optimal SC: O(1) space
Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated such that there is exactly one solution. You may not use the same element twice. Your solution must use only constant extra space.
Example 1:
Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
Example 2:
Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
Example 3:
Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
Constraints:
- 2 <= numbers.length <= 3 * 104
- -1000 <= numbers[i] <= 1000
- numbers is sorted in non-decreasing order.
- -1000 <= target <= 1000
- The tests are generated such that there is exactly one solution.
Topic: Two Pointers (Medium - Two Sum II)
Hint: Best solved with a two pointer approach. Trick here is that we want to return the indices + 1 when target is found because it is a 1-indexed array for some reason
- While loop while left < right
- Check for target match and return true is found
- if numSum < target, we want to increment the left pointer
- if numSum > target, we want to decrement the right pointer
Optimal TC: O(N) time
Optimal SC: O(N) space
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.
Constraints:
- 3 <= nums.length <= 3000
- -105 <= nums[i] <= 105
Topic: Two Pointers (Medium - 3 Sum)
Hint: We know the target must be 0 and so this is what we check for. We also need to re-use Two Sum 2 in order to solve this problem.
- Make sure to sort first, and create a results array
- We are going to need both the value and the index of the array so we will: for i, a in enumerate(nums):
- inside the loop we are going to check for an edge case is a > 0 then we know we cannot add to 0 since all numbers are great than 0: if a > 0: break
- After this we need to do an initial handling of dupes where we skip and continue to next iteration: if i > 0 and a == nums[i - 1]: continue
- then we will call the twoSum function where we send in the array, index and results: self.twoSum(nums, i, results)
- The two sum function is basically two sum 2 problem where we check again 0. If we have a sum match against 0 we will append the result, increment left and then check for dupes again:
- results.append([nums[i], nums[left], nums[right]])
- left += 1
- # Dupe shifting
-
while nums[left] == nums[left - 1] and left < right:
- left += 1
Optimal TC: O(N^2) time
Optimal SC: O(N) space (depending on sorting for space)
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
- n == height.length
- 2 <= n <= 105
- 0 <= height[i] <= 104
Topic: Two Pointers (Medium - Container With Most Water)
Hint: Best solved with a two pointer approach. Trick here is to know the area formula
- Set left to 0 and right to len(height) - 1
- Loop while left < right
- Most important part is calculating the area: area = (right - left) * min(height[left], height[right])
- Then we update the max area with: result = max(result, area)
- Lastly we update the left/right pointers depending on which is higher.
- if height[left] < height[right]: left +=1 and else: right -= 1
Optimal TC: O(N) time
Optimal SC: O(1) space
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 * 104
- 0 <= height[i] <= 105
Topic: Two Pointers (Hard- Trapping Rain Water) 🔙(marked to rewatch video)
Hint: 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
- Lots of vars. Set an answer = 0, left, right to 0 and len(height) -1
- We also need a maxLeft and maxRight which can be set to height[left, height[right]
- Loop while left < right
- if maxLeft < maxRight:
- increment left first: left += 1
- update maxLeft with max(maxLeft, height[left])
- update answer with += maxLeft - height[left]
- Do the same with the right ptr inside an else statement
- don’t forget to return the answer
Optimal TC: O(N) time
Optimal SC: O(1) space
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
Topic: Sliding Window (Easy- Best Time to Buy and Sell Stock)
Hint: Basic sliding window problem. Trick here is to compare left and right ptrs and set the left ptr to the right each time right is bigger.
- For vars just set a maxGain and a left pointer both to 0
- Then we start a loop at 1 where the right ptr will start: for right in range(1, len(prices))
- Then we check if prices[right] < prices[left]:
- When this is true we want to reset the left pointer to where the right pointer is which creates a new low point: left = right
- Outside of the if statement we will update the max gain for each iteration: maxGain = max(maxGain, prices[right] - prices[left])
- We use “prices[right] - prices[left]” because this determines the profit
- Finally outside of the loop we will return maxGain
Optimal TC: O(N) time
Optimal SC: O(1) space
Given a string s, find the length of the longest substring without repeating characters.
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3. Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
Constraints:
- 0 <= s.length <= 5 * 104
- s consists of English letters, digits, symbols and spaces.
Topic: Sliding Window (Medium - Longest Substring Without Repeating Characters)
Hint: Trick here is to use a set and check for s[right} being inside the set first before adding the new char to the set. Result is always max of right - left + 1 which is the current window size.
- For vars just left and longest to 0. Also create an empty set to store the chars
- Then we start a loop to increment the right ptr only: for right in range(len(s))
- Then we check while s[right] in set:
- While this is true we want to remove the left char from the set with set.remove(s[left]), after this we want to increment the left ptr to shorten the window
- Outside of the while loop we will now add the right char to the set with set.add(s[right])
- Lastly inside this loop we will update the result with longest = max(longest, right - left + 1) because this is how we calculate the curr window
- Finally outside of the loop we will return longest
Optimal TC: O(N) time
Optimal SC: O(N) space, for the use of a set that is the size of the longest sequence
You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.
Example 1:
Input: s = “ABAB”, k = 2
Output: 4
Explanation: Replace the two ‘A’s with two ‘B’s or vice versa.
Example 2:
Input: s = “AABABBA”, k = 1
Output: 4
Explanation: Replace the one ‘A’ in the middle with ‘B’ and form “AABBBBA”. The substring “BBBB” has the longest repeating letters, which is 4.
Constraints:
- 1 <= s.length <= 105
- s consists of only uppercase English letters.
- 0 <= k <= s.length
Topic: Sliding Window (Medium - Longest Repeating Character Replacement) 🔙(marked to rewatch video)
Hint: Trick here is to check for a valid window size which is “current window size - max frequency <= K”.
- For vars we will need a hashmap count and a left and result set to 0.
- Then we start a loop to increment the right ptr only: for right in range(len(s))
- Inside the loop we will first add the current char at the right ptr to the hashmap with: count[s[right]] = 1 + count.get(s[right], 0)
- After this we need to check for a valid window with: if (right - left + 1) - max(count.values()) > k:
- The importance of this is that if we are NOT inside a valid window (the IF statement being TRUE) then we need to decrement the count of the current left pointer char with: count[s[left]] -= 1
- We will also need to shrink the window from the left side with: left += 1
- Outside of the IF statement we will also need to update the result with: result = max(result, right - left + 1)
- Lastly we will return result
Optimal TC: O(N) time
Optimal SC: O(N) space, for the use of a hashmap to store the char counts
Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = “babad”
Output:“bab”
Explanation:“aba” is also a valid answer.
Example 2:
Input: s = “cbbd”
Output:“bb”
Constraints:
- 1 <= s.length <= 1000
- s consist of only digits and English letters.
Topic: Sliding Window (Medium - Longest Palindromic Substring)
Hint: Trick here is to check for a valid palindrome for both an even and odd length. We will use a helper function to check palindromes with an expand from center approach.
- For vars we will just need a result set to an empty string.
- Then we should start a for loop and inside the loop we need to check both even and odd length strings
- For odd length we will do
- left, right = i, i
- found = self.findPalin(s, left, right)
- After this we will need to check and compare string lengths with: if len(results) < len(found):
- results = found
- We will then repeat this same code with: left, right = i, i + 1 for the even length strings
- Repeat the check to compare string lengths as noted above
- Finally outside of the loop we will return results
- Now the last thing we need to do is right a helper function to check for palindrome substrings: def findPalin(self, s, left, right):
- Inside here lets store the length of the string with: sLen = len(s)
- Now we need to loop while left and right ptrs are in bounds and s[left] == s[right]: while left >= 0 and right < sLen and s[left] == s[right]:
- Note: This is the “expanding loop” to check for palindromes. Inside the loop we will move the ptrs with: left -= 1 and right += 1
- Lastly we will return the current palindrome size to compare with: return s[left + 1: right]
Optimal TC: O(N^2) time
Optimal SC: O(1) space
Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = “abc”
Output: 3
Explanation: Three palindromic strings: “a”, “b”, “c”.
Example 2:
Input: s = “aaa”
Output: 6
Explanation: Six palindromic strings: “a”, “a”, “a”, “aa”, “aa”, “aaa”.
Constraints:
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Topic: Sliding Window (Medium - Palindromic Substrings)
Hint: Trick here is to update the result by checking for a valid palindrome for both an even and odd length. We will use a helper function to check palindromes with an expand from center approach.
- For vars we will just need a result set to 0.
- Then we should start a for loop and inside the loop we need to check both even and odd length strings
- For odd length we will do:
- result += self.findPalin(s, i, i)
- For even length we will do: result += self.findPalin(s, i, i + 1)
- Finally outside of the loop we will return results
- Now the last thing we need to do is right a helper function to check for palindrome substrings: def findPalin(self, s, left, right):
- Inside here lets store the length of the string with: sLen = len(s). We will also need a new Result var and set it to 0
- Now we need to loop while left and right ptrs are in bounds and s[left] == s[right]: while left >= 0 and right < sLen and s[left] == s[right]:
- Note: This is the “expanding loop” to check for palindromes. Inside the loop we will increment the result += 1 then move the ptrs with: left -= 1 and right += 1
- Lastly we will return the current palindrome size to compare with: return result
Optimal TC: O(N^2) time
Optimal SC: O(1) space
Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string ““. The testcases will be generated such that the answer is unique. A substring is a contiguous sequence of characters within the string.
Example 1:
Input: s = “ADOBECODEBANC”, t = “ABC”
Output:“BANC”
Explanation: The minimum window substring “BANC” includes ‘A’, ‘B’, and ‘C’ from string t.
Example 2:
Input: s = “a”, t = “a”
Output:“a”
Explanation: The entire string s is the minimum window.
Example 3:
Input: s = “a”, t = “aa”
Output:””
Explanation: Both ‘a’s from t must be included in the window. Since the largest window of s only has one ‘a’, return empty string.
Constraints:
- m == s.length
- n == t.length
- 1 <= m, n <= 105
- s and t consist of uppercase and lowercase English letters.
Topic: Sliding Window (Hard - Minimum Window Substring) 🔙(marked to rewatch video)
Hint: Trick here is to rewatch the video lmao
- For vars we will just need a result set to 0.
Optimal TC: O(S + T) time
Optimal SC: O(S + T) space
You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Constraints:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- 1 <= k <= nums.length
Topic: Sliding Window (Hard - Sliding Window Maximum) 🔙(marked to rewatch video)
Hint: Trick here is to rewatch the video lmao
- For vars we will just need a result set to 0.
Optimal TC: O(N) time
Optimal SC: O(K) space where we have the deque store K elements
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid. An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
Example 1:
Input: s = “()”
Output: true
Example 2:
Input: s = “()[]{}”
Output: true
Example 3:
Input: s = “(]”
Output: false
Constraints:
- 1 <= s.length <= 104
- s consists of parentheses only ‘()[]{}’.
Topic: Stacks (Easy - Valid Parentheses)
Hint: We need to use a stack here and to remember 2 things: 1: Open brackets must be closed by the same type of brackets. 2: Open brackets must be closed in the correct order. Need to remember to use a hashmap to store the closing brackets as the keys to the value of the opening brackets.
- First initiate and empty stack - stack = [] and a hashmap pairs, making sure to set the key to all of the closing brackets - brackets = {“)” : “(“, “]”, “[”, “}”, “{“}
- First we start with a loop to go thru each char within the input string: for c in s:
- Then we want to check if the current char is a closing bracket with: if c in brackets:
- Next we check is stack if non-empty and if we have a MATCH (note: brackets[c] will compare a closing bracket to the value which is an opening bracket) at the top of the stack, we pop with: if stack and stack[-1] == brackets[c]:
- stack.pop()
- Else we don’t have a match and we need to return false (not valid) with: else: return False
- Next we check is stack if non-empty and if we have a MATCH (note: brackets[c] will compare a closing bracket to the value which is an opening bracket) at the top of the stack, we pop with: if stack and stack[-1] == brackets[c]:
- Pivoting back to the outside IF statement, “Else” we have a opening bracket and need to append to the stack with: else:
- stack.append(c)
- Then we want to check if the current char is a closing bracket with: if c in brackets:
- Lastly we are outside of the original for loop and we want to check for an empty stack (which would be valid): return not stack
Optimal TC: O(N) time
Optimal SC: O(N) space
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
- MinStack() initializes the stack object.
- void push(int val) pushes the element val onto the stack.
- void pop() removes the element on the top of the stack.
- int top() gets the top element of the stack.
- int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
Example 1:
Input [“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”] [[],[-2],[0],[-3],[],[],[],[]]
Output [null,null,null,null,-3,null,0,-2]
Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2
Constraints:
- -231 <= val <= 231 - 1
- Methods pop, top and getMin operations will always be called on non-empty stacks.
- At most 3 * 104 calls will be made to push, pop, top, and getMin.
Topic: Stacks (Medium - Min Stack)
Hint: The trick here is inside the push and method, Where we are checking if there is no value in the minStack or if the new value is less than the current top of the minStack and then appending only if true
- First need to initialize 2 stacks. A regular stack and a minStack. Don’t forget to use “self” like: self.stack = []
- Next, inside the push method we can annd to the main stack with: self.stack.append(val), but before we add to the minStack we need to check if there is no value in the minStack or if the new value is less than the curr top of the minStack and then appending only if true, with: if not self.minStack or val <= self.minStack[-1]:
- self.minStack.append(val)
- For the pop method we also need to compare the top of both stack and pop from the minStack first if the match with: if self.minStack[-1] == self.stack[-1]:
- self.minStack.pop()
- Then self.stack.pop()
- The Top function is just returning the top of the main stack: return self.stack[-1]
- and the getMin function is just returning the top of the minStack: return self.minStack[-1]
Optimal TC: O(1) time
Optimal SC: O(N) space
Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero. It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.
Example 1:
Input: tokens = [“2”,”1”,”+”,”3”,”*”]
Output: 9
Explanation: ((2 + 1) * 3) = 9
Example 2:
Input: tokens = [“4”,”13”,”5”,”/”,”+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:
Input: tokens = [“10”,”6”,”9”,”3”,”+”,”-11”,”*”,”/”,”*”,”17”,”+”,”5”,”+”]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22
Constraints:
- 1 <= tokens.length <= 104
- tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].
Topic: Stacks (Medium - Evaluate Reverse Polish Notation)
Hint: The trick here is to use a stack and a bunch of if / elif statements for each operators. WE also need to take special care of the minus and division operators. Should also note we do the operators starting with plus then division would be last.
- First need to initialize a stack: stack = []
- Then we will start a for loop to iterate through each char in the provided array: for char in tokens:
- Inside the loop we want to start with check the plus sign and handling that: if char == “+”:
- stack.append(stack.pop() + stack.pop())
- Next we do the subtraction sign: elif char == “-“:
- NOTE: make sure to pop the chars first before subtracting:
- a, b = stack.pop(), stack.pop()
- stack.append(b - a)
- Next we do the multiply sign: elif char == “*“:
- stack.append(stack.pop() * stack.pop())
- Then we do the division sign:
- NOTE: make sure to pop the chars first before dividing. Also make sure to convert the division solution to an int before appending):
- a, b = stack.pop(), stack.pop()
- stack.append(int(b / a))
- Lastly we do a final “else” statement where we just add the char (converting to int first):
- stack.append(int(char))
- Inside the loop we want to start with check the plus sign and handling that: if char == “+”:
- Outside of the for loop we will then return stack[0] since the answer should already be the only value left in the stack.
Optimal TC: O(N) time
Optimal SC: O(N) space
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Constraints:
- 1 <= n <= 8
Topic: Stacks w/ Backtracking (Medium - Generate Parentheses) 🔙(marked to rewatch video, mainly to understand backtracking)
Hint: The trick here is to use a couple of stacks while using backtracking and also to make note of the following “rules”:
- Only add an open parenthesis if number of open < n
- Only add a closing parenthesis if number of closed < number of open
- Valid If number of open == number of closed == n (base case)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
- First need to initialize our stacks: stack = [] and result = []
- Then we want to create a backtrack function: def backtrack(openNum, closedNum):
- inside this new function we want to set the base case for a valid expression: if openNum == closedNum == n:
- result.append(““.join(stack))
- Then we want to only add an open paren if open < n: if openNum < n:
- stack.append(“(“)
- backtrack(openNum + 1, closedNum)
- stack.pop()
- Lastly, we want to only add a closed paren if closed < open: if closedNum < openNum:
- stack.append(“)”)
- backtrack(openNum, closedNum + 1)
- stack.pop()
- inside this new function we want to set the base case for a valid expression: if openNum == closedNum == n:
- Finally outside of the backtrack function, don’t forget to call it with backtrack(0, 0) then finally return result
Optimal TC: O(4^N/sqrt(N)) time
Optimal SC: O(N) space
