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
