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

Neetcode 150 Flashcards by Joseph Schell

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

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)

How well did you know this?

Not at all

Perfectly

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 * 10⁴
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

How well did you know this?

Not at all

Perfectly

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 <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) 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

How well did you know this?

Not at all

Perfectly

Given an array of strings strs, group the anagrams together. You can return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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

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

Example 2:

Input: strs = [””] Output: [[””]]

Example 3:

Input: strs = [“a”] Output: [[“a”]]

Constraints:

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

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

How well did you know this?

Not at all

Perfectly

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
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

How well did you know this?

Not at all

Perfectly

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 <= 10⁵
-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

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

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)

Optimal TC: O(N) time

Optimal SC: O(N) space

How well did you know this?

Not at all

Perfectly

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 * 10⁵
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

How well did you know this?

Not at all

Perfectly

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[index₁] and numbers[index₂] where 1 <= index₁ < index₂ <= numbers.length. Return the indices of the two numbers, index₁ and index₂, added by one as an integer array [index₁, index₂] 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, index₁ = 1, index₂ = 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 index₁ = 1, index₂ = 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 index₁ = 1, index₂ = 2. We return [1, 2].

Constraints:

2 <= numbers.length <= 3 * 10⁴
-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

How well did you know this?

Not at all

Perfectly

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
-10⁵ <= nums[i] <= 10⁵

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)

How well did you know this?

Not at all

Perfectly

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i^th 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 <= 10⁵
0 <= height[i] <= 10⁴

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

How well did you know this?

Not at all

Perfectly

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

Example 1:

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

Output: 6

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

Example 2:

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

Output: 9

Constraints:

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

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

How well did you know this?

Not at all

Perfectly

You are given an array prices where prices[i] is the price of a given stock on the i^th 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 <= 10⁵
0 <= prices[i] <= 10⁴

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

How well did you know this?

Not at all

Perfectly

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 * 10⁴
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

How well did you know this?

Not at all

Perfectly

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 <= 10⁵
s consists of only uppercase English letters.
0 <= k <= s.length

Study These Flashcards

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.

Study These Flashcards

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.

Study These Flashcards

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 <= 10⁵
s and t consist of uppercase and lowercase English letters.

Study These Flashcards

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 <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

Study These Flashcards

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 <= 10⁴
s consists of parentheses only ‘()[]{}’.

Study These Flashcards

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
- 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)
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:

-2³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Study These Flashcards

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 <= 10⁴
tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200].

Study These Flashcards

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))
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

Study These Flashcards

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()
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

Given an array of integers temperatures represents the daily temperatures, return *an array* answer *such that* answer[i] *is the number of days you have to wait after the* i^th *day to get a warmer temperature*. If there is no future day for which this is possible, keep answer[i] == 0 instead. **Example 1:** **Input:** temperatures = [73,74,75,71,69,72,76,73] **Output:** [1,1,4,2,1,1,0,0] **Example 2:** **Input:** temperatures = [30,40,50,60] **Output:** [1,1,1,0] **Example 3:** **Input:** temperatures = [30,60,90] **Output:** [1,1,0] **Constraints:** * 1 \<= temperatures.length \<= 10⁵ * 30 \<= temperatures[i] \<= 100

**Topic**: Stacks (Medium - Daily Temperatures) 🔙(**marked to rewatch video**) **Hint**: The trick here is to use a “monotonic stack” which I will need more clarification on from the video. * First need to initialize both a stack and an answer array filled with zeros: **stack = []** and **answer = [0] \* len(temperatures)** * Then we will do a for loop enumeration style since we will need both the indexes and values: **for i, t in enumerate(temperatures):** * Inside the loop we need another while loop to check if the stack is not empty AND is the current temp \> the value at the top of the stack: **while stack and t \> stack[-1][0]:** (note the double indexing is -1 for the top and the 0th element at the top, which should give us the temp) * Inside the while loop we pop off the top into 2 vars: **stackT, stackIdx = stack.pop()** * Then we want to calculate the number of days it took to find greater temp. We o this by subtracting curr index with popped stackIdx and storing in the answer array at the stackIdx: **answer[stackIdx] = (i - stackIdx)** * Outside of the while loop (when the statement evaluates false) we are just going to append the temp and index to the stack: **stack.append([t, i])** * Finally we are outside both loops and we can **return answer** **Optimal TC**: O(N) time **Optimal SC**: O(N) space

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return *the area of the largest rectangle in the histogram*. **Example 1:** **Input:** heights = [2,1,5,6,2,3] **Output:** 10 **Explanation:** The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units. **Example 2:** **Input:** heights = [2,4] **Output:** 4 **Constraints:** * 1 \<= heights.length \<= 10⁵ * 0 \<= heights[i] \<= 10⁴

**Topic**: Stacks (Hard - Largest Rectangle in Histogram) 🔙(**marked to rewatch video**) **Hint**: I think this is another “monotonic stack” solution which I will need more clarification on from the video. The trick here is calculating the area with h \* (i - idx) * First need to initialize both a maxArea and empty stack: **maxArea = 0** and **stack = []** * Then we will do a for loop enumeration style since we will need both the indexes and values: **for i, h in enumerate(heights):** * Inside the loop we will create a start pointer and set it to i: **start = i** * Next we will start another while loop that checks if our stack is empty and if the top values height \> current height for this iteration: **while stack and stack[-1][1] \> h:** * Inside this while loop we pop off the stack if the logic is true: **idx, height = stack.pop()** * Then we want to update our maxArea value, making sure to calculate the area with the correct formula: **maxArea = max(maxArea, height \* (i - idx))** * Lastly we set the start pointer to this newly popped index: **start = idx** * Outside of the while loop we are just going to append the the new starting index and height to the stack: **stack.append((start, h))** * Outside our original for loop we also want to check for any remaining entries in our stack and compute their heights: **for i, h in stack:** * Inside the loop we will just update the maxArea with the values: **maxArea = max(maxArea, h \* (len(heights) - i))** * Finally we are outside both loops and we can **return maxArea** **Optimal TC**: O(N) time **Optimal SC**: O(N) space

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. **Example 1:** **Input:** nums = [-1,0,3,5,9,12], target = 9 **Output:** 4 **Explanation:** 9 exists in nums and its index is 4 **Example 2:** **Input:** nums = [-1,0,3,5,9,12], target = 2 **Output:** -1 **Explanation:** 2 does not exist in nums so return -1 **Constraints:** * 1 \<= nums.length \<= 10⁴ * -10⁴ \< nums[i], target \< 10⁴ * All the integers in nums are **unique**. * nums is sorted in ascending order.

**Topic**: Binary Search (Easy - Binary Search) **Hint**: Self explanatory, just remember the proper way to calculate mid * First initiate a left and right pointer with: **left, right = 0, len(nums) - 1** * Next we want to start a while loop, make sure to go while left **≤** right: **while left \<= right:** * Inside the loop, we first set the mid point or pivot and make sure to calculate the mid point by adding L + (R - L) to avoid overflow errors: **mid = left + (right - left) // 2** * First we check for target match at mid: **if nums[mid] == target: return mid** * 2nd we check if mid is \> target: **elif nums[mid] \> target: right = mid - 1** * Lastly we check for everything else (mid ≤ target): **else: left = mid + 1** * Finally once we exit the loop we can return -1 if the target is not found: **return -1** **Optimal TC**: O(LogN) time **Optimal SC**: O(1) space

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: * Integers in each row are sorted from left to right. * The first integer of each row is greater than the last integer of the previous row. **Example 1:** ![]() **Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 **Output:** true **Example 2:** ![]() **Input:** matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13**Output:** false **Constraints:** * m == matrix.length * n == matrix[i].length * 1 \<= m, n \<= 100 * -10⁴ \<= matrix[i][j], target \<= 10⁴

**Topic**: Binary Search (Medium - Search a 2D Matrix) **Hint**: Similar to regular binary search problem, just on a 2D array. The trick here is to find the **row** with **idx // n** and **col** with **idx % n** * First we need to set the M and N vars to help with readability: **m, n = len(matrix), len(matrix[0])** * Next we want to check an edge case with: **if m == 0: return False** * Then we want to set a left and right pointer: **left, right = 0, m \* n - 1** * Next we want to start a while loop, make sure to go while left **≤** right: **while left \<= right:** * Inside the loop, we first set the pivotIdx and make sure to calc the mid point by adding L + (R - L) to avoid overflow errors: **pivotIdx = left + (right - left) // 2** * We also need to set the pivotElement with: **pivotElement = matrix[pivotIdx // n][pivotIdx % n]** * First we check for target match at mid: **if target == pivotElement: return True** * Then we open an Else statement: **else:** * Inside here we check if target \< pivotElement and if true, we set right to pivotIdx - 1: **if target \< pivotElement: right = pivotIdx - 1** * Else we check for everything else (target ≥ pivotElement) and then we set left to pivotIdx + 1: **else: left = pivotIdx + 1** * Finally once we exit the loop we can return False if the target is not found: **return False** **Optimal TC**: O(LogM\*N) time **Optimal SC**: O(1) space

Koko loves to eat bananas. There are n piles of bananas, the i^th pile has piles[i] bananas. The guards have gone and will come back in h hours. Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour. Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return. Return *the minimum integer* k *such that she can eat all the bananas within* h *hours*. **Example 1:** **Input:** piles = [3,6,7,11], h = 8 **Output:** 4 **Example 2:** **Input:** piles = [30,11,23,4,20], h = 5 **Output:** 30 **Example 3:** **Input:** piles = [30,11,23,4,20], h = 6 **Output:** 23 **Constraints:** * 1 \<= piles.length \<= 10⁴ * piles.length \<= h \<= 10⁹ * 1 \<= piles[i] \<= 10⁹

**Topic**: Binary Search (Medium - Koko Eating Bananas) **Hint**: Not too difficult. Keep note that there is a brute force solution here that basically leads to the Binary Search optimized version. I did not write that brute force solution here, but it is inside the leetcode solution. Key note here is we can calculate Koko's current eating speed with **math.ceil(pile / mid)** or replace mid with speed for the brute force solution. After we calculate all the hours at each pile we want to see if Koko can eat all the piles within the given hours (h), or basically find a workable solution. If this is true we can update our right pointer to mid, else we will set the left pointer to mid + 1 * **left, right = 1, max(piles)** * **while left \< right:** * # Get the mid index between left and right * # Hours here stands for the total hours Koko spends * **mid = left + (right - left) // 2** * **hours = 0** * **for pile in piles:** * # Calculate hours at each pile * # Increase the hours with ceil(pile / mid) which rounds the division up to nearest integer * **hours += math.ceil(pile / mid)** * # Check if mid is a workable speed and cut the search space in half * **if hours \<= h:** * **right = mid** * **else:** * **left = mid + 1** * # Once the left and right boundaries coincide we find the target value * **return right** **Optimal TC**: O(NLogM) time **Optimal SC**: O(1) space

There is an integer array nums sorted in ascending order (with **distinct** values). Prior to being passed to your function, nums is **possibly rotated** at an unknown pivot index k (1 \<= k \< nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (**0-indexed**). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. Given the array nums **after** the possible rotation and an integer target, return *the index of* target *if it is in* nums*, or* -1 *if it is not in* nums. You must write an algorithm with O(log n) runtime complexity. **Example 1:** **Input:** nums = [4,5,6,7,0,1,2], target = 0 **Output:** 4 **Example 2:** **Input:** nums = [4,5,6,7,0,1,2], target = 3 **Output:** -1 **Example 3:** **Input:** nums = [1], target = 0 **Output:** -1 **Constraints:** * 1 \<= nums.length \<= 5000 * -10⁴ \<= nums[i] \<= 10⁴ * All values of nums are **unique**. * nums is an ascending array that is possibly rotated. * -10⁴ \<= target \<= 10⁴

**Topic**: Binary Search (Medium - Search in Rotated Sorted Array) **Hint**: The trick here is if you look at the array, you can see that there are basically 2 parts to the array and both parts are sorted, which is ideal for a Binary Search solution. The trick here is to figure out if you are in the left sorted portion of the array after checking for the target first, with **elif nums[pivot] \>= nums[left]**. If this is true we can check **if target is \>= left AND target \< pivot we can move the right pointer, otherwise move the left pointer**. Else we can handle the right sorted portion of the array by checking **if target is \<= right AND target \> pivot we can move the left pointer, otherwise move the right pointer**. * **left, right = 0, len(nums) - 1** * **while left \<= right:** * **pivot = left + (right - left) // 2** * **if nums[pivot] == target:** * **return pivot** * # Check if we are in the left sorted portion of the array * # We can do this by comparing the pivot element to the left element * # If the pivot is \>= to the left element, we know we are in the left sorted portion * **elif nums[pivot] \>= nums[left]:** * # If target is \>= left AND target \< pivot we can move the right pointer, * # otherwise move the left pointer * **if target \>= nums[left] and target \< nums[pivot]:** * **right = pivot - 1** * **else:** * **left = pivot + 1** * # Handle right sorted portion of the array * **else:** * # If target is \<= right AND target \> pivot we can move the left pointer, * # otherwise move the right pointer * **if target \<= nums[right] and target \> nums[pivot]:** * **left = pivot + 1** * **else:** * **right = pivot - 1** * # If target is not found, we can return -1 * **return -1** **Optimal TC**: O(LogN) time **Optimal SC**: O(1) space

Suppose an array of length n sorted in ascending order is **rotated** between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become: * [4,5,6,7,0,1,2] if it was rotated 4 times. * [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that **rotating** an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Given the sorted rotated array nums of **unique** elements, return *the minimum element of this array*. You must write an algorithm that runs in O(log n) time. **Example 1:** **Input:** nums = [3,4,5,1,2] **Output:** 1 **Explanation:** The original array was [1,2,3,4,5] rotated 3 times. **Example 2:** **Input:** nums = [4,5,6,7,0,1,2] **Output:** 0 **Explanation:** The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. **Example 3:** **Input:** nums = [11,13,15,17] **Output:** 11 **Explanation:** The original array was [11,13,15,17] and it was rotated 4 times. **Constraints:** * n == nums.length * 1 \<= n \<= 5000 * -5000 \<= nums[i] \<= 5000 * All the integers of nums are **unique**. * nums is sorted and rotated between 1 and n times.

**Topic**: Binary Search (Medium - Find Minimum in Rotated Sorted Array) 🔙(**marked to rewatch video**) **Hint**: The trick here is adjusting the left and right pointers to search the correct portion of the array. After checking if the array is already sorted, we will set a pivot and start by checking if we are in the left sorted portion and we want to search to the right of the pivot with **if nums[pivot] \>= nums[left]: left = pivot + 1.** Else, this is part of the right sorted and we want to search the left portion with **right = pivot - 1.** * **left, right = 0, len(nums) - 1** * **result = nums[0]** * **while left \<= right:** * # Check if subarray is already sorted, then break * **if nums[left] \< nums[right]:** * **result = min(nums[left], result)** * **break** * **pivot = left + (right - left) // 2** * **result = min(nums[pivot], result)** * **if nums[pivot] \>= nums[left]:** * # Then this is part of the left sorted portion and we want to search to the right of the pivot * **left = pivot + 1** * **else:** * # Else, this is part of the right sorted and we want to search the left portion * **right = pivot - 1** * **return result** **Optimal TC**: O(LogN) time **Optimal SC**: O(1) space

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp. Implement the TimeMap class: * TimeMap() Initializes the object of the data structure. * void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. * String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp\_prev \<= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp\_prev. If there are no values, it returns "". **Constraints:** * 1 \<= key.length, value.length \<= 100 * key and value consist of lowercase English letters and digits. * 1 \<= timestamp \<= 10⁷ * All the timestamps timestamp of set are strictly increasing. * At most 2 \* 10⁵ calls will be made to set and get.

**Topic**: Binary Search (Medium - Time Based Key-Value Store) 🔙(**marked to rewatch video**) **Hint**: The trick here is using binary search in the get function. The main thing to remember is how to move the left and right pointers. We do this by checking if the value timestamp is \<= timestamp input, if true we update the result with the value and move the left pointer with **if values[mid][1] \<= timestamp:** then we update the **result = values[mid][0]** and move the left pointer with **left = mid + 1**. Else we do not have a timestamp that works and we move the right pointer with **else: right = mid - 1**. * **def \_\_init\_\_(self):** * # Hashmap to store values and timestamps * **self.keyStore = {}** * **def set(self, key: str, value: str, timestamp: int) -\> None:** * # If the 'key' does not exist in dictionary, initialize empty array * **if key not in self.keyStore:** * **self.keyStore[key] = []** * # Store '(timestamp, value)' pair in 'key' bucket. * **self.keyStore[key].append([value, timestamp])** * **def get(self, key: str, timestamp: int) -\> str:** * **result, values = "", self.keyStore.get(key, [])** #this will get the key or an empty array if no key exists * **left, right = 0, len(values) - 1** * # Binary search * **while left \<= right:** * **mid = left + (right - left) // 2** * # Check is value timestamp is \<= timestamp input, if true we update the result with the value and move the left pointer * **if values[mid][1] \<= timestamp:** * **result = values[mid][0]** * **left = mid + 1** * # Else we do not have a timestamp that works and we move the right pointer * **else:** * **right = mid - 1** * **return result** **Optimal TC**: O(LogN) time unconfirmed **Optimal SC**: O(N) space

Given two sorted arrays nums1 and nums2 of size m and n respectively, return **the median** of the two sorted arrays. The overall run time complexity should be O(log (m+n)). **Example 1:** **Input:** nums1 = [1,3], nums2 = [2] **Output:** 2.00000 **Explanation:** merged array = [1,2,3] and median is 2. **Example 2:** **Input:** nums1 = [1,2], nums2 = [3,4] **Output:** 2.50000 **Explanation:** merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5. **Constraints:** * nums1.length == m * nums2.length == n * 0 \<= m \<= 1000 * 0 \<= n \<= 1000 * 1 \<= m + n \<= 2000 * -10⁶ \<= nums1[i], nums2[i] \<= 10⁶

**Topic**: Binary Search (Hard - Median of Two Sorted Arrays) 🔙(**marked to rewatch video**) **Hint**: The trick here is I don't fucking know, re-watch the video * **A, B = nums1, nums2** * **total = len(A) + len(B)** * **half = total // 2** * **if len(B) \< len(A):** * **A, B = B, A** * **left, right = 0, len(A) - 1** * **while True:** * **i = left + (right - left) // 2** # this is the mid point for A * **j = half - i - 2** # this is mid point for B * # Assign but handle edge cases by checking for in bounds and using infinity * **Aleft = A[i] if i \>= 0 else float("-inf")** * **Aright = A[i + 1] if (i + 1) \< len(A) else float("inf")** * **Bleft = B[j] if j \>= 0 else float("-inf")** * **Bright = B[j + 1] if (j + 1) \< len(B) else float("inf")** * **# Check if partition is correct (unconfirmed)** * **if Aleft \<= Bright and Bleft \<= Aright:** * **# For odd case** * **if total % 2:** * **return min(Aright, Bright)** * # For even case * **return (max(Aleft, Bleft) + min(Aright, Bright)) / 2** * **elif Aleft \> Bright:** * **right = i - 1** * **else:** * **left = i + 1** **Optimal TC**: O(Log(min(M, N)) **Optimal SC**: O(1) space

Given the head of a singly linked list, reverse the list, and return *the reversed list*. **Constraints:** * The number of nodes in the list is the range [0, 5000]. * -5000 \<= Node.val \<= 5000

**Topic**: Linked Lists (Easy - Reverse Linked List) **Hint**: The trick here is to use a rev pointer for the iterative solution (which is more optimal with space complexity) **_Iterative Solution_** * **prev = None** * **curr = head** * # Loop while curr is not null * **while curr:** * # Create a temp pointer and set it to the next node before breaking the link * **temp = curr.next** * # Now we can move the curr.next pointer to the prev pointer * **curr.next = prev** * # Then set prev to curr * **prev = curr** * # Move curr to the next node * **curr = temp** * # Prev should be at the new head so return prev **return prev** **_Recursive solution_** * if not head or not head.next: * return head * newHead = self.reverseList(head.next) * head.next.next = head * head.next = None * return newHead **Optimal TC**: O(N) time **Optimal SC**: O(1) space (iterative)

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists in a one **sorted** list. The list should be made by splicing together the nodes of the first two lists. Return *the head of the merged linked list*. **Constraints:** * The number of nodes in both lists is in the range [0, 50]. * -100 \<= Node.val \<= 100 * Both list1 and list2 are sorted in **non-decreasing** order.

**Topic**: Linked Lists (Easy - Merge Two Sorted Lists) **Hint**: The trick here is to use a rev pointer for the iterative solution (which is more optimal with space complexity) **_Iterative Solution_** * **prev = None** * **curr = head** * # Loop while curr is not null * **while curr:** * # Create a temp pointer and set it to the next node before breaking the link * **temp = curr.next** * # Now we can move the curr.next pointer to the prev pointer * **curr.next = prev** * # Then set prev to curr * **prev = curr** * # Move curr to the next node * **curr = temp** * # Prev should be at the new head so return prev **return prev** **_Recursive solution_** * if not head or not head.next: * return head * newHead = self.reverseList(head.next) * head.next.next = head * head.next = None * return newHead **Optimal TC**: O(N) time **Optimal SC**: O(1) space (iterative)

You are given the head of a singly linked-list. The list can be represented as: L₀ → L₁ → … → L_{n - 1} → L_n *Reorder the list to be on the following form:* L₀ → L_n → L₁ → L_{n - 1} → L₂ → L_{n - 2} → … You may not modify the values in the list's nodes. Only nodes themselves may be changed. **Constraints:** * The number of nodes in the list is in the range [1, 5 \* 10⁴]. * 1 \<= Node.val \<= 1000

**Topic**: Linked Lists (Medium - Reorder List) **Hint**: The trick here is to use a rev pointer for the iterative solution (which is more optimal with space complexity) **_Iterative Solution_** * **prev = None** * **curr = head** * # Loop while curr is not null * **while curr:** * # Create a temp pointer and set it to the next node before breaking the link * **temp = curr.next** * # Now we can move the curr.next pointer to the prev pointer * **curr.next = prev** * # Then set prev to curr * **prev = curr** * # Move curr to the next node * **curr = temp** * # Prev should be at the new head so return prev **return prev** **_Recursive solution_** * if not head or not head.next: * return head * newHead = self.reverseList(head.next) * head.next.next = head * head.next = None * return newHead **Optimal TC**: O(N) time **Optimal SC**: O(1) space (iterative)

Neetcode 150 Flashcards

(36 cards)