Notion Tip: to uncheck all TODOs below, select the block of the first todo (contains duplicate below), scroll down until it’s the bottom-most one → Cmd+Enter
-
[ ] Contains Duplicate
<aside>
💡
Loop through, adding to hashset, but if num if already in hashset → duplicate exists
</aside>
class Solution:
def hasDuplicate(self, nums: List[int]) -> bool:
hashset = set();
for n in nums:
if n in hashset:
return True
else:
hashset.add(n)
return False
-
[ ] Valid Anagram
<aside>
💡
counts lists of [0] * 26 for every letter of alphabet. Loop through first string, adding to counts at the right index by doing counts[ord(char) - ord("a")] (difference in ASCII value from char to a will give proper index in counts. Then, loop through other string, decrementing that count at that char’s index in counts. Then, loop through counts → if there’s a count != 0, then return False. Otherwise, return True.
</aside>
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# hash set - optimal O(26) -> O(1) memory
if len(s) != len(t):
return False
count = [0] * 26
for i in range(len(s)):
count[ord(s[i]) - ord('a')] += 1
count[ord(t[i]) - ord('a')] -= 1
for val in count:
if val != 0:
return False
return True
-
[ ] Two Sum
<aside>
💡
If not sorted (regular): Iterate through array (enumerate, to get indexes), storing each num in a hashmap (num: index), then if you calculate the current needed num, target - num to be in the hashmap, return their indexes.
If sorted: could use two pointers, such that if the sum is too large, move right pointer in, and if the sum is too small, move the left pointer in. If the pointers cross → return False
</aside>
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dictionary = {} # {number: index} #hashmap
for index, number in enumerate(nums):
number_needed = target - number
if number_needed in dictionary:
return [dictionary[number_needed], index]
# essentially else to that condition ^^ above
if number not in dictionary:
dictionary[number] = index
# if number is in dictionary already, then nothing needs to be done
-
[ ] Group Anagrams
<aside>
💡
Iterate through every string, populating counts (just like in Valid Anagram) → append it to the res defaultdict(list) at the index of the tuple of the counts . So, anagrams will be grouped in a hashmap of the indexes being tuples of counts (i.e. {[1, 1, 1, 0, ..., 0]: 'cab', 'acb'})
Therefore, return [res.values()] since the values will be the word groups
Remember to do res[tuple(count)] as the index, not res[list(count)] since indexes have to be immutable.
</aside>
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
res = defaultdict(list) # to avoid issues with unknown indexes
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
res[tuple(count)].append(s)
return list(res.values())
-
[ ] Top K Frequent Elements
<aside>
💡
(check whole code from the NeetCode problem)
</aside>
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq = [[] for i in range(len(nums) + 1)] # + 1, because I need 0 to len(nums)
# [1, 4, 2, 2, 5, 5]
# [[1, 4], [2, 5]], since indexes in this freq list rep nums that occurred that num times
counts = defaultdict(int) # e.g. {3: 2}, means the number 3 has 2 occurrences
for number in nums:
counts[number] += 1
# could've also used counts[number] = 1 + counts.get(number, 0)
for number, count in counts.items(): # e.g. {1: 2, 2: 4, 3: 3}
freq[count].append(number) # freq = [[], [], [1], [3], [2]]
# freq = [[], [], [1], [3], [2]]
top_elements = []
# i is iterating from last index to first
for i in range(len(freq) -1, -1, -1):
for element in freq[i]:
top_elements.append(element)
if len(top_elements) >= k:
# stop
return top_elements
return top_elements
-
[ ] Encode and Decode Strings
<aside>
💡
Encode the string by putting the number of digits, followed by a delimiter character like ‘#’, then the string. When decoding, you can then get the number of digits by looping over the string until the delimiter is reached → this is the number of digits as a string → convert to int → skip over the delimiter → loop through the string numDigits times to get that word
</aside>
class Solution:
def encode(self, strs: List[str]) -> str:
words = []
for word in strs:
words.append(f'{len(word)}#word')
# joining once at the end for performance, since += would
# recreate a new string every time, since strings are immutable.
return "".join(words)
def decode(self, s: str) -> List[str]:
cur_index = 0
words = []
# DEBUG: s = "4#neet4#code4#love3#you"
while cur_index < len(s):
# 1. get the number before '#' (which separates)
# the number from the word itself
letter_count_str = ""
while s[cur_index] != '#':
# this means we're still getting the letter_count
letter_count_str += (s[cur_index]) # DEBUG: 4 (string)
cur_index += 1
letter_count = int(letter_count_str) # DEBUG: 4 (int)
# 2. get the word after the #, which I'll know
# when to stop looking for, based on the letter_count
# Now, we should be at the '#' delimiter, so to skip:
cur_index += 1
word = ""
# Now, we're at the word
for i in range(letter_count): # DEBUG: 0, 3
# for as many times as letter_count, we add the char
# to our word
word += (s[cur_index])
cur_index += 1
words.append(word)
# 3. Move onto the next word once letter_count reached
# when looking for the word
return words
-
[ ] Product of Array Except Self
<aside>
💡
Calculate the prefix sums in order, with prefix = 1 to start. Then, calculate the postfix sums in order, with postfix = 1 to start (by iterating in reverse using for i in range(len(nums) - 1, -1, -1): . As going through each list, multiply the pre/postfix with the res[i] : res[i] *= postfix
</aside>
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
res = [1] * len(nums)
prefix, postfix = 1, 1
# [1, 1, 1, 1]
for index, num in enumerate(nums):
res[index] *= prefix
prefix *= num
for index in range(len(nums) - 1, -1, -1):
res[index] *= postfix
postfix *= nums[index]
return res
-
[ ] Valid Sudoku
<aside>
💡
Set columns, rows, and squares = collections.defaultdict(set) . Loop through every cell, adding to those sets if it’s not already in any, current Val in columns[r] or currentVal in rows[c] or currentVal in squares[(r//3, c//3)] → return False if it’s already in any of these (duplicate, by Sudoku rules).
</aside>
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
columns = collections.defaultdict(set)
rows = collections.defaultdict(set)
squares = collections.defaultdict(set)
for r in range(len(board)):
for c in range(len(board[0])):
currentVal = board[r][c]
if currentVal == ".":
continue
if currentVal in columns[r] or currentVal in rows[c] or currentVal in squares[(r//3, c//3)]:
return False
else:
# need to put in columns, rows, squares
columns[r].add(currentVal)
rows[c].add(currentVal)
squares[(r//3, c//3)].add(currentVal)
return True
-
[ ] Longest Consecutive Subsequence
class Solution:
# nums = [] -> 0, [1] -> 1, [2, 3] -> 2, [4, 5, 8] -> 2
def longestConsecutive(self, nums: List[int]) -> int:
hashSet = set(nums)
longest = 0
for i in range(len(nums)): # 0 -> len(nums) - 1, therefore, the indexes
if nums[i] - 1 in hashSet:
# nums[i] isn't the first in its sequence, therefore skip
continue
# now we know it has the potential of being the subsequence start
current_length = 1
while nums[i] + current_length in hashSet:
current_length += 1
longest = max(longest, current_length)
return longest
-
[ ] Valid Palindrome
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while r > l and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l, r = l + 1, r - 1
return True
-
[ ] Two sum II
<aside>
💡
The question states it wants O(1) space, and we can do this by avoiding the hashmap as in Two Sum I, since we can leverage the fact that the input is sorted to use two pointers instead.
</aside>
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
# while they don't cross
while left < right:
current_sum = numbers[left] + numbers[right]
if current_sum == target:
return [left + 1, right + 1] # due to 1-indexing, per question
else:
# not hit target
if current_sum > target:
# too big of sum, therefore we need to decrease it by moving right pointer left
right -= 1
else:
# too small of sum, therefore we need to increase it by moving left pointer right
left += 1
# don't need to handle case where no solution exists
-
[ ] 3Sum
<aside>
💡
Sort first (n log n but that’s fine). Then, iterate through, calling current num a, then search for b and c using two pointers, from current index (left) and end index (right) → search inwards.
</aside>
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
for numIndex in range(len(nums)):
# num is operand a, where a + b + c = 0
a = nums[numIndex]
#(current num is same as last) -> don't bother checking
if numIndex > 0 and a == nums[numIndex - 1]:
continue
# two-pointers to find the other two operands (b and c) for addition
l, r = numIndex + 1, len(nums) - 1
# they have not crossed
# OG two-pointers twoSum
while l < r:
b, c = nums[l], nums[r]
curSum = a + b + c
# later: if different sums are targeted (desired), edit this:
if curSum < 0:
l += 1
elif curSum > 0:
r -= 1
else:
# correct sum
res.append([a, b, c])
# need to move left pointer over to non-duplicate number
l += 1
# same conditional as before:
#(current num is same as last) -> don't bother checking
while l < r and nums[l] == nums[l - 1]:
l += 1
# we've reached a new num
return res
-
[ ] Container with most water
<aside>
💡
Pretty easy - just calculate current area by using the min of the two heights of your two pointers and the difference in indexes (horizontal length). Then, possibly overwrite the overall maxArea
</aside>
class Solution:
def maxArea(self, heights: List[int]) -> int:
l, r = 0, len(heights) - 1
maxArea = 0
while l < r:
computedArea = min(heights[l], heights[r]) * (r - l)
maxArea = max(computedArea, maxArea)
# adjust either the left or right pointer
if heights[l] > heights[r]:
r -= 1
else:
l += 1
return maxArea
-
[ ] Trapping Rain Water
<aside>
💡
See code
</aside>
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
l, r = 0, len(height) - 1
leftMax, rightMax = height[l], height[r]
res = 0
while l < r:
if leftMax < rightMax:
l += 1
leftMax = max(leftMax, height[l])
res += leftMax - height[l]
else:
r -= 1
rightMax = max(rightMax, height[r])
res += rightMax - height[r]
return res
More intuitive in my opinion:
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n == 0:
return 0
leftMax = [0] * n
rightMax = [0] * n
leftMax[0] = height[0]
for i in range(1, n):
leftMax[i] = max(leftMax[i - 1], height[i])
rightMax[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
rightMax[i] = max(rightMax[i + 1], height[i])
res = 0
for i in range(n):
res += min(leftMax[i], rightMax[i]) - height[i]
return res