217. Contains Duplicate
from typing import List
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
new_set = set();
for i in range(0, len(nums)):
if nums[i] not in new_set:
new_set.add(nums[i])
else:
return True;
return False;
242. Valid Anagram
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
hash_table = {}
for ch in s:
if ch not in hash_table:
hash_table[ch] = 1
else:
hash_table[ch] = hash_table[ch] + 1
for ch in t:
if ch not in hash_table:
return False
else:
hash_table[ch] = hash_table[ch] - 1
for code in range(ord('a'), ord('z') + 1):
if chr(code) in hash_table and hash_table[chr(code)] != 0:
return False
return True
1. Two Sum
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hash_table = {}
for i in range(0, len(nums)):
remainder = target - nums[i]
if remainder in hash_table.keys():
return [hash_table[remainder], i]
hash_table[nums[i]] = i
return []
49. Group Anagrams
from typing import List
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
hash_table = {}
for string in strs:
sorted_str = str(sorted(string))
if sorted_str not in hash_table.keys():
hash_table[sorted_str] = [string]
else:
hash_table[sorted_str].append(string)
sol = []
for key in hash_table.keys():
sol.append(hash_table[key])
return sol
347. Top K Frequent Elements
import heapq
from typing import List
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
hash_table = {}
for x in nums:
if x not in hash_table:
hash_table[x] = 1
else:
hash_table[x] = hash_table[x] + 1
pq = []
for key in hash_table.keys():
heapq.heappush(pq, (hash_table[key], key))
sol = []
for x in heapq.nlargest(iterable=pq, n=k):
sol.append(x[1])
return sol
Better approach (Bucket Sort)
from typing import List
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
hash_table = {}
for i in range(0, len(nums)):
if nums[i] not in hash_table:
hash_table[nums[i]] = 1
else:
hash_table[nums[i]] = hash_table[nums[i]] + 1
count = [[] for i in range(0, len(nums) + 1)]
for key, val in hash_table.items():
count[val].append(key)
sol = []
for i in range(len(count) - 1, 0, -1):
for x in count[i]:
sol.append(x)
if len(sol) == k:
return sol
String Encode and Decode
from typing import List
class Solution:
def encode(self, strs: List[str]) -> str:
encoded_string = ""
for string in strs:
encoded_string += str(len(string)) + "#" + string
return encoded_string
def decode(self, s: str) -> List[str]:
sol = []
i = 0
while i < len(s):
j = i
while s[j] != '#':
j += 1
length = int(s[i:j])
sol.append(s[j + 1 : j + 1 + length])
i = j + 1 + length
return sol
238. Product of Array Except Self
from typing import List
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
sol = []
lt = []
rt = []
for i in range(0, len(nums)):
if i == 0:
lt.append(nums[i])
else:
lt.append(lt[i - 1] * nums[i])
for i in range(len(nums) - 1, -1, -1):
if i == len(nums) - 1:
rt.append(nums[i])
else:
rt.append(rt[len(rt) - 1] * nums[i])
rt.reverse()
for i in range(0, len(nums)):
if i == 0:
sol.append(rt[i + 1])
elif i == len(nums) - 1:
sol.append(lt[i - 1])
else:
sol.append(lt[i - 1] * rt[i + 1])
return sol
36. Valid Sudoku
from typing import List
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
for i in range(0, 9):
sodoku_set = set()
for j in range(0, 9):
if board[i][j] in sodoku_set:
return False
elif board[i][j] != ".":
print(board[i][j])
sodoku_set.add(board[i][j])
for j in range(0, 9):
sudoku_set = set()
for i in range(0, 9):
if board[i][j] in sudoku_set:
return False
elif board[i][j] != ".":
sudoku_set.add(board[i][j])
ist = 0
jst = 0
while True:
sudoku_set = set()
for i in range(ist, ist + 3):
for j in range(jst, jst + 3):
if board[i][j] in sudoku_set:
return False
elif board[i][j] != ".":
sudoku_set.add(board[i][j])
jst += 3
if jst == 9:
jst = 0
ist += 3
if ist == 9:
break
return True
128. Longest Consecutive Sequence
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
nums.sort()
longest = 1
current = 1
for i in range(1, len(nums)):
if nums[i] == nums[i - 1] + 1:
current += 1
elif nums[i] > nums[i - 1] + 1:
current = 1
if longest < current:
longest = current
return longest
Better approach (Using Set())
from typing import List
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nSet = set(nums)
longest = 0
current = 0
for x in nums:
if (x - 1) not in nSet:
current = 1
while (x + current) in nSet:
current += 1
if longest < current:
longest = current
return longest
20. Valid Parentheses
class Solution:
def isValid(self, s: str) -> bool:
st = []
for ch in s:
top = st[len(st) - 1] if len(st) > 0 else -1
if ch == '(' or ch == '[' or ch == '{':
st.append(ch)
elif ch == ')' and top == '(' or ch == ']' and top == '[' or ch == '}' and top == '{':
st.pop()
else:
return False
if len(st) != 0:
return False
return True
155. Min Stack
class MinStack:
def __init__(self):
self.st = []
def push(self, val: int) -> None:
self.st.append(val)
def pop(self) -> None:
self.st.pop()
def top(self) -> int:
return self.st[-1]
def getMin(self) -> int:
minim = self.st[-1]
for x in self.st:
if minim > x:
minim = x
return minim
Better approach (Two Stacks)
class MinStack:
def __init__(self):
self.st = []
self.min_stack = []
def push(self, val: int) -> None:
self.min_stack.append(min(val, self.min_stack[-1] if len(self.min_stack) > 0 else val))
self.st.append(val)
def pop(self) -> None:
self.st.pop()
self.min_stack.pop()
def top(self) -> int:
return self.st[-1]
def getMin(self) -> int:
return self.min_stack[-1]
150. Evaluate Reverse Polish Notation
from typing import List
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operators = {'+', '-', '*', '/'}
st = []
for t in tokens:
if t in operators:
s_item = int(st.pop())
f_item = int(st.pop())
if t == '+':
res = f_item + s_item
elif t == '-':
res = f_item - s_item
elif t == '*':
res = f_item * s_item
else:
res = int(f_item / s_item)
st.append(res)
else:
st.append(t)
return int(st.pop())
22. Generate Parentheses
from typing import List
class Solution:
def __init__(self):
self.sol = []
def isValid(self, s : List[str]) -> bool:
st = []
for p in s:
if p == '(':
st.append(p)
elif p == ')':
top = 0 if len(st) == 0 else st[-1]
if top == '(':
st.pop()
else:
return False
if len(st) > 0:
return False
return True
def bkt(self, n : int, s: List[str], index : int) -> None:
par = {'(', ')'}
for p in par:
s[index] = p
if index == (2 * n - 1) and self.isValid(s) == True:
self.sol.append(''.join(s))
elif index < (2 * n - 1):
self.bkt(n, s, index + 1)
def generateParenthesis(self, n: int) -> List[str]:
s = [0] * 2 * n
self.bkt(n, s, 0)
return self.sol
Better approach
from typing import List
class Solution:
def __init__(self):
self.stack = []
self.sol = []
def bkt(self, openP: int, closeP: int, n: int) -> None:
if openP == closeP == n:
self.sol.append(''.join(self.stack))
return None
if openP < n:
self.stack.append("(")
self.bkt(openP=openP + 1, closeP=closeP, n=n)
self.stack.pop()
if closeP < openP:
self.stack.append(")")
self.bkt(openP=openP, closeP=closeP + 1, n=n)
self.stack.pop()
def generateParenthesis(self, n: int) -> List[str]:
self.bkt(openP=0, closeP=0, n=n)
return self.sol
739. Daily Temperatures
from typing import List
class Solution:
def dailyTemperatures(self, temp: List[int]) -> List[int]:
ans = [0] * len(temp)
st = []
for i in range(0, len(temp)):
while len(st) > 0 and temp[st[-1]] < temp[i]:
ans[st[-1]] = i - st[-1]
st.pop()
st.append(i)
return ans
853. Car Fleet
from typing import List
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [[p, s] for p, s in zip(position, speed)]
st = []
for p, s in sorted(pair)[::-1]:
st.append((target - p) / s)
if len(st) >= 2 and st[-1] <= st[-2]:
st.pop()
return len(st)
84. Largest Rectangle in Histogram
from typing import List
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
st = []
for i, h in enumerate(heights):
start = i
while len(st) > 0 and st[-1][1] > h:
index , height = st.pop()
maxArea = max(maxArea, height * (i - index))
start = index
st.append((start, h))
for i, h in st:
maxArea = max(maxArea, h * (len(heights) - i))
return maxArea
125. Valid Palindrome
class Solution:
def isPalindrome(self, s: str) -> bool:
new_s = ""
for c in s:
c = c.lower()
if c >= 'a' and c <= 'z' or c >= '0' and c <= '9':
new_s += c
i = 0
j = len(new_s) - 1
while i < j :
if new_s[i] != new_s[j]:
return False
i += 1
j -= 1
return True
167. Two Sum II - Input Array Is Sorted
from typing import List
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
i = 0
j = len(numbers) - 1
while i < j:
s = numbers[i] + numbers[j]
if s == target:
return [i + 1, j + 1]
elif s < target:
i += 1
else:
j -= 1
return []
15. 3Sum
from typing import List
class Solution:
def __init__(self):
self.sol = []
def twoSum(self, nums: List[int], target: int, k: int,i : int, j: int ) -> List[int]:
while i < j:
s = nums[i] + nums[j]
if s < target or i == k:
i += 1
elif s > target or j == k:
j -= 1
else:
cand = [nums[i], nums[j], nums[k]]
self.sol.append(cand)
i += 1
while nums[i] == nums[i - 1] and i < j:
i += 1
return []
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
for k in range(0, len(nums) - 2):
if k > 0 and nums[k] == nums[k - 1]:
continue
print(nums[k])
self.twoSum(nums,(nums[k] * -1), k, k + 1,len(nums) - 1)
return self.sol
11. Container With Most Water
from typing import List
class Solution:
def maxArea(self, height: List[int]) -> int:
max_area = -1
i = 0
j = len(height) - 1
while i < j :
c_area = min(height[i], height[j]) * (j - i)
if c_area > max_area or max_area == -1:
max_area = c_area
if height[i] < height[j]:
i += 1
else:
j -= 1
return max_area
42. Trapping Rain Water
from typing import List
class Solution:
def trap(self, h: List[int]) -> int:
diff = [0] * len(h)
maxim = 0
for i in range(0, len(h)):
if maxim < h[i]:
maxim = h[i]
diff[i] = 0
else:
diff[i] = maxim - h[i]
w = 0
maxim = 0
for i in range(len(h) - 1, -1, -1):
if maxim < h[i]:
maxim = h[i]
else:
diff[i] = min(diff[i], maxim - h[i])
w += diff[i]
return w
Better approach (Two Pointers)
from typing import List
class Solution:
def trap(self, h: List[int]) -> int:
i = 0
j = len(h) - 1
w = 0
maxL = 0
maxR = 0
while i < j:
if maxL < h[i]:
maxL = h[i]
if maxR < h[j]:
maxR = h[j]
maxMin = min(maxL, maxR)
if maxMin > h[i]:
w += maxMin - h[i]
if maxMin > h[j]:
w += maxMin - h[j]
if maxL < maxR:
i += 1
else:
j -= 1
return w
121. Best Time to Buy and Sell Stock
from typing import List
class Solution:
def maxProfit(self, p: List[int]) -> int:
i = 0
j = 1
max_profit = 0
while j < len(p):
while p[j] >= p[i]:
if max_profit < p[j] - p[i]:
max_profit = p[j] - p[i]
j += 1
if j == len(p):
break
i = j
j = i + 1
return max_profit
3. Longest Substring Without Repeating
Characters
from typing import List
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hash_table = {}
i = 0
j = 0
l_s = 0
while j < len(s):
if s[j] not in hash_table.keys():
hash_table[s[j]] = j
else:
i = max(i, hash_table[s[j]] + 1)
hash_table[s[j]] = j
l_s = max(l_s, j - i + 1)
j += 1
return l_s
424. Longest Repeating Character
Replacement
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
i = 0
j = 0
max_f = 0
longest = 0
hash_t = {}
while j < len(s):
if s[j] not in hash_t:
hash_t[s[j]] = 1
else:
hash_t[s[j]] += 1
max_f = max(max_f, hash_t[s[j]])
if (j - i + 1) - max_f <= k:
longest = max(longest, (j - i + 1))
else:
hash_t[s[i]] -= 1
i += 1
j += 1
return longest
567. Permutation in String
from typing import List
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
if len(s2) < len(s1):
return False
hash_s1 = {}
hash_s2 = {}
for k in range(ord('a'), ord('z') + 1):
c = chr(k)
hash_s1[c] = 0
hash_s2[c] = 0
for c in s1:
hash_s1[c] += 1
i = 0
j = len(s1) - 1
for x in range(i, j):
hash_s2[s2[x]] += 1
while j < len(s2):
hash_s2[s2[j]] += 1
ok = True
for k in range(ord('a'), ord('z') + 1):
c = chr(k)
if (c in hash_s1) != (c in hash_s2):
ok = False
if (c in hash_s1 ) and ( c in hash_s2):
if hash_s1[c] != hash_s2[c]:
ok = False
if ok == True:
return True
hash_s2[s2[i]] -= 1
i += 1
j += 1
return False
76. Minimum Window Substring
class Solution:
def minWindow(self, s: str, t: str) -> str:
if t == "":
return ""
l = 0
r = 0
hash_t, hash_s = {}, {}
min_seq = float("infinity")
sl, sr = [-1, -1]
for c in t:
hash_t[c] = 1 + hash_t.get(c, 0)
have = 0
need = len(hash_t)
while r < len(s):
hash_s[s[r]] = hash_s.get(s[r], 0) + 1
if s[r] in hash_t and hash_s[s[r]] == hash_t[s[r]]:
have += 1
while have == need:
if min_seq > (r - l + 1):
min_seq = r - l + 1
sl = l
sr = r
hash_s[s[l]] -= 1
if s[l] in hash_t and hash_s[s[l]] < hash_t[s[l]]:
have -= 1
l += 1
r += 1
return s[sl : sr + 1] if min_seq != float("infinity") else ""
239. Sliding Window Maximum
from collections import deque
from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
sol = []
dq = deque()
l = 0
r = l + k - 1
for x in range(r + 1):
while len(dq) > 0 and nums[x] > dq[-1]:
dq.pop()
dq.append(nums[x])
sol.append(dq[0])
while r < (len(nums) - 1):
if nums[l] == dq[0]:
dq.popleft()
l += 1
r += 1
while len(dq) > 0 and nums[r] > dq[-1]:
dq.pop()
dq.append(nums[r])
sol.append(dq[0])
return sol
704. Binary Search
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
r = mid - 1
else:
l = mid + 1
return -1
74. Search a 2D Matrix
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
arr = []
for r in range(len(matrix)):
for c in range(len(matrix[0])):
arr.append(matrix[r][c])
l = 0
r = len(arr) - 1
while l <= r:
mid = (l + r) // 2
if arr[mid] == target:
return True
elif target > arr[mid]:
l = mid + 1
else:
r = mid - 1
return False
Better approach (No Extra Space)
from typing import List
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS, COLS = len(matrix), len(matrix[0])
bot, top = 0, ROWS - 1
while bot <= top:
m_row = (bot + top) // 2
if target > matrix[m_row][-1]:
bot = m_row + 1
elif target < matrix[m_row][0]:
top = m_row - 1
else:
break
if bot > top:
return False
row = (top + bot) // 2
print(row)
l, r = 0, COLS - 1
while l <= r:
m = (l + r) // 2
print(m)
if target > matrix[row][m]:
l = m + 1
elif target < matrix[row][m]:
r = m - 1
else :
return True
return False
875. Koko Eating Bananas
import math
from typing import List
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l = 1
r = max(piles)
sol = float("infinity")
while l <= r:
k = (l + r) // 2
print(k)
h_e = 0
for i in range(len(piles)):
h_e += math.ceil(piles[i] / k)
if h_e <= h:
sol = k
r = k - 1
else:
l = k + 1
return sol
153. Find Minimum in Rotated Sorted
Array
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
res = nums[0]
l, r = 0, len(nums) - 1
while l <= r:
if nums[l] < nums[r]:
res = min(res, nums[l])
break
m = (l + r) // 2
res = min(res, nums[m])
if nums[m] >= nums[l]:
l = m + 1
else:
r = m - 1
return res
33. Search in Rotated Sorted Array
from typing import List
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = (l + r) // 2
if target == nums[m]:
return m
if nums[l] <= nums[m]:
if target > nums[m] or target < nums[l]:
l = m + 1
else:
r = m - 1
else:
if target < nums[m] or target > nums[r]:
r = m - 1
else:
l = m + 1
return -1
981. Time Based Key-Value Store
class TimeMap:
def __init__(self):
self.hash = {}
def set(self, key: str, value: str, timestamp: int) -> None:
if key not in self.hash:
self.hash[key] = { "v" : [], "t" : []}
self.hash[key]["v"].append(value)
self.hash[key]["t"].append(timestamp)
def get(self, key: str, timestamp: int) -> str:
if key not in self.hash:
return ""
arr = self.hash[key]["t"]
l , r = 0, len(arr) - 1
index = float("infinity")
while l <= r:
m = (l + r) // 2
if arr[m] <= timestamp:
index = m
if arr[m] == timestamp:
break
else:
l = m + 1
else:
r = m - 1
if index != float("infinity"):
return self.hash[key]["v"][index]
return ""
4. Median of Two Sorted Arrays
from typing import List
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A, B = nums1, nums2
total = len(nums1) + len(nums2)
half = total // 2
if len(B) < len(A):
A, B = B, A
l, r = 0, len(A) - 1
while True:
i = (l + r) // 2
j = half - i - 2
Aleft = A[i] if i >= 0 else float("-infinity")
Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
Bleft = B[j] if j >= 0 else float("-infinity")
Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")
if Aleft <= Bright and Bleft <= Aright:
if total % 2:
return min(Aright, Bright)
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
r = i - 1
else:
l = i + 1
206. Reverse Linked List
ITERATIVE APPROACH:
RECURSIVE APPROACH:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
current = head;
prev = None;
if current == None:
return current
while current.next != None:
next_node = current.next
current.next = prev
prev = current
current = next_node
current.next = prev
return current
21. Merge Two Sorted Lists
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def recursive(ll, rl):
if not ll:
return rl
return recursive(ll.next, ListNode(ll.val, rl))
return recursive(head, None)
143. Reorder List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1, list2):
head = None
current = None
while list1 != None and list2 != None:
new_node = ListNode()
if list1.val < list2.val:
new_node.val = list1.val
list1 = list1.next
else:
new_node.val = list2.val
list2 = list2.next
if head == None:
head = new_node
current = head
else:
current.next = new_node
current = new_node
if list1 != None:
if current == None:
head = list1
else:
current.next = list1
if list2 != None:
if current == None:
head = list2
else:
current.next = list2
current = head
while current != None:
current = current.next
return head
19. Remove Nth Node From End of List
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# 1 Find the middle and split the list in two segments
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second = slow.next
slow.next = prev = None
# 2 Reverse the second segment
while second:
tmp = second.next
second.next = prev
prev = second
second = tmp
first = head
second = prev
# 3 Merge the two segments
while second:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2
#4 Return the reordered list
return head
138. Copy List with Random Pointer
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
# 1 Initialize two pointers
p1 = head
p2 = head
# 2 Move the second pointer n nodes away from the first pointer
while n > 0:
p2 = p2.next
n -= 1
# 3 Iterate the second pointer until it reaches the end of the list
while p2 and p2.next:
p1 = p1.next
p2 = p2.next
# 4 Remove the n-th node from the end of the list
if p2 == None: # if the first node should be removed
head = head.next
else:
p1.next = p1.next.next
# 5 Return the list
return head
2. Add Two Numbers
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# 1 Initialize a hash table where each node of the orginal list
# will be a key to each node in the copied list
oldToCopy = {None : None}
# 2 Iterate over the list and create a copy of each node with the
# same value
cur = head
while cur:
copy = Node(cur.val)
oldToCopy[cur] = copy
cur = cur.next
# 3 Iterate once again and add the next and random references
cur = head
while cur:
copy = oldToCopy[cur]
copy.next = oldToCopy[cur.next]
copy.random = oldToCopy[cur.random]
cur = cur.next
# 4 Return the head of the copied linked list
return oldToCopy[head]
141. Linked List Cycle
FIRST APPROACH O(n) memory
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
# 1 Initialize the sum variable that will retain the sum of the digits
sum = 0
# 2 Initialize the head of the sum linked list
# and also the last node of this list
l3 = last = None
# 3 Iterate over the l1 and l2 and add the digits to l3
while l1 and l2:
sum += l1.val + l2.val
if l3 == None:
l3 = ListNode(sum % 10)
last = l3
else:
last.next = ListNode(sum % 10)
last = last.next
sum = sum // 10
l1 = l1.next
l2 = l2.next
# 4 Iterate over both lists until the finish node
while l1:
sum += l1.val
last.next = ListNode(sum % 10)
last = last.next
sum = sum // 10
l1 = l1.next
while l2:
sum += l2.val
last.next = ListNode(sum % 10)
last = last.next
sum = sum // 10
l2 = l2.next
# 5 If there is 1 digit remained in the sum
# add it to the sum list
if sum > 0:
last.next = ListNode(sum % 10)
last = last.next
sum = sum // 10
# 6 Return the sum as a linked list
return l3
SECOND APPROACH TWO POINTERS : FLOYD'S TURTOISE
AND HARE
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 1 Create a hash table in order to retain all the nodes in the
# linked list
copy = {}
# 2 Iterate over all the nodes in the list
# If the same node is reached twice, then we have a cycle
# otherwise not
cur = head
while cur:
if cur in copy:
return True
else:
copy[cur] = True
cur = cur.next
return False
287. Find the Duplicate Number
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
# 1 Initialize two pointers at the head
slow = fast = head
# 2 Iterate the pointers over the list
# fast pointer will be iterated twice as fast as
# the slow pointer
# 3 If there is a cycle in the list, then they
# will meet at the same position because
# the difference between them will be decremented
# by one with each iteration when they
# are both in the cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
146. LRU Cache
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# 1 Initialize two pointers slow and fast
slow = fast = 0
# 2 Iterate the fast pointer twice as fast as the slow pointer
# and break when they meet each other
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# 3 Initialize a new pointer at the start
slow2 = 0
# 4 Iterate slow2 and slow until they meet at the start
# of the cycle which is the duplicate number
while True:
slow2 = nums[slow2]
slow = nums[slow]
if slow == slow2:
return slow
23. Merge k Sorted Lists
# Use a doubly linked list that will store at the left side
# the Least Recently Used key
# and at the right side the most recently used key
class Node:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.left = None
self.right = None
def insert(self, node : Node):
if self.left == None:
self.left = node
if self.right == None:
self.right = node
else:
self.right.next = node
node.prev = self.right
self.right = node
def remove(self, node : Node):
if self.right != node and self.left != node:
node.prev.next = node.next
node.next.prev = node.prev
if self.left == node:
if node.next:
node.next.prev = None
self.left = self.left.next
if self.right == node:
if node.prev:
node.prev.next = None
self.right = node.prev
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove(node)
self.insert(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value
self.remove(node)
node.next = None
self.insert(node)
else:
self.cap = self.cap - 1
node = Node(key, value)
self.insert(node)
self.cache[key] = node
if self.cap < 0:
del self.cache[self.left.key]
self.remove(self.left)
self.cap += 1
25. Reverse Nodes in k-Group
FIRST APPROACH O(n) Time, O(k) Memory
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
# 1 Iterate the current node on each k linked lists
# and find the node with the minimum value
# and iterate the list with the minimum value node
res = None
last = None
while True:
min_node = None
minimum = float("inf")
it = -1
for i in range(0, len(lists)):
x = lists[i]
if x is None:
continue
if minimum > x.val:
min_node = x
minimum = x.val
it = i
# if all the lists are finished,
# then stop the search
if min_node == None:
break
if res == None:
res = min_node
last = res
else:
last.next = min_node
last = last.next
lists[it] = lists[it].next
return res
SECOND APPROACH O(n) Time, O(1) Memory
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 1 Traverse the linked list and split the list at every k nodes
# and retain the heads of the segments in an array
seg = []
cur = head
n = 0
while cur:
hs = cur
n = k - 1
seg.append(hs)
while n > 0 and cur:
cur = cur.next
n = n - 1
if cur:
nxt = cur.next
cur.next = None
cur = nxt
# 2 Check if the last segment has k nodes
cnt = 0
cur = seg[len(seg) - 1]
while cur:
cnt = cnt + 1
cur = cur.next
r_l = False
if cnt == k:
r_l = True
# 3 Reverse the segements with k nodes
for i in range(0, len(seg)):
x = seg[i]
if (i == (len(seg) - 1) and r_l) or i < (len(seg) - 1):
cur = x
prev = None
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
seg[i] = prev
# 4 Connect the reversed segments toghether
for i in range(0, len(seg) - 1):
cur = seg[i]
while cur and cur.next:
cur = cur.next
print("CUR" , cur.val, seg[i + 1].val)
cur.next = seg[i + 1]
return seg[0]
226. Invert Binary Tree
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 1 Traverse the list and reverse the k group nodes
head_prev = ListNode(0, head)
group_prev = head_prev
while True:
kth = self.get_kth(group_prev, k)
# 2 If we are in the last group, and it contains less than k nodes
if not kth:
break
group_next = kth.next
# 3 Reverse the cur group
prev = kth.next
cur = group_prev.next
while cur != group_next:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
tmp = group_prev.next
group_prev.next = kth
group_prev = tmp
return head_prev.next
def get_kth(self, cur, k):
while cur and k > 0:
cur = cur.next
k = k - 1
return cur
104. Maximum Depth of Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the binary search tree and reverse
the left and the right subtree of each node """
def invertTreeMet(self, node: TreeNode):
if node:
aux = node.left
node.left = node.right
node.right = aux
if node.left:
self.invertTree(node.left)
if node.right:
self.invertTree(node.right)
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
self.invertTreeMet(node=root)
return root
543. Diameter of Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the list and retain the max stack level,
which is going to be the maximum depth of the binary tree """
def __init__(self):
self.st = 0
self.max = -float("inf")
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0;
self.st = self.st + 1
if self.max < self.st:
self.max = self.st
if root.left:
self.maxDepth(root=root.left)
if root.right:
self.maxDepth(root=root.right)
self.st = self.st - 1
if self.st == 0:
return self.max
110. Balanced Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse each node of the binary tree
and the max diameter is going to be
the max depth of the left subtree +
the max depth of the right subtree of the cur node"""
def __init__(self):
self.diameter = 0
self.max_depth = -float("inf")
def dfs(self, node: TreeNode):
if node == None:
return 0
left = self.dfs(node=node.left)
right = self.dfs(node=node.right)
if self.diameter < (left + right):
self.diameter = (left + right)
return 1 + max(left, right)
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.dfs(node=root)
return self.diameter
100. Same Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the binary tree and for each node
check if the difference between the height of the left subtree and
the right subtree is greater than 1, in which case the binary
tree is not balanced """
def __init__(self):
self.is_balanced = True
def dfs(self, node: TreeNode):
if node is None:
return 0
left = self.dfs(node.left)
right = self.dfs(node.right)
if abs(left - right) > 1:
self.is_balanced = False
return 1 + max(left, right)
def isBalanced(self, root: Optional[TreeNode]) -> bool:
self.dfs(node=root)
return self.is_balanced
572. Subtree of Another Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse both trees at the same time and check if they are the same """
def __init__(self):
self.same = True
def dfs(self, p: TreeNode, q : TreeNode):
if (p == None) != (q == None):
self.same = False
return
if p == None:
return
if p.val != q.val:
self.same = False
return
self.dfs(p.left, q.left)
self.dfs(p.right, q.right)
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
self.dfs(p, q)
return self.same
235. Lowest Common Ancestor of a Binary
Search Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse each node of the root binary tree and check
if the subtree which has the root as the cur node is identical
with the subRoot tree """
def __init__(self):
self.same = True
self.found = False
def is_same_tree(self, p : TreeNode, q : TreeNode):
if (p == None) != (q == None):
self.same = False
return
if p == None:
return
if p.val != q.val:
self.same = False
return
self.is_same_tree(p.left, q.left)
self.is_same_tree(p.right, q.right)
def dfs(self, node: TreeNode, subRoot: TreeNode):
if node == None:
return
self.same = True
self.is_same_tree(node, subRoot)
if self.same == True:
self.found = True
self.dfs(node=node.left, subRoot=subRoot)
self.dfs(node=node.right, subRoot=subRoot)
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
self.dfs(node=root, subRoot=subRoot)
return self.found
102. Binary Tree Level Order Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
""" Traverse the bst with from the root
if both p and q are greater than root then go to the right
if both p and q are lower than root than go to the left
else the current node is the lca """
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
while True:
if p.val == root.val or q.val == root.val:
break
if p.val > root.val and q.val > root.val:
root = root.right
elif p.val < root.val and q.val < root.val:
root = root.left
else:
break
return root
199. Binary Tree Right Side View
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the list and retain a hash table with a key for each level
which is going to have an arr with all the node values ,
then combine the res into a single list"""
def __init__(self):
self.st = 0
self.max_level = 0
self.levels = {}
def dfs(self, node : TreeNode):
if not node:
return
self.st = self.st + 1
self.max_level = max(self.max_level, self.st)
if self.st not in self.levels:
self.levels[self.st] = []
self.levels[self.st].append(node.val)
self.dfs(node.left)
self.dfs(node.right)
self.st = self.st - 1
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
self.dfs(root)
res = []
for i in range(1, self.max_level + 1):
res.append(self.levels[i])
return res
1448. Count Good Nodes in Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the list and append to the res arr the right most node
for each level """
def __init__(self):
self.res = []
def dfs(self,node: TreeNode, depth: int):
if not node:
return
if len(self.res) == depth:
self.res.append([])
self.res[depth] = node.val
self.dfs(node.left, depth + 1)
self.dfs(node.right, depth + 1)
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
self.dfs(node=root, depth=0)
return self.res
98. Validate Binary Search Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the binary tree and retain a stack with the maximum nodes
on the current path every time when we add a new item to stack,
increment the number of good nodes"""
def __init__(self):
self.st = []
self.cnt = 0
def dfs(self, node):
if not node:
return
ok = False
if len(self.st) == 0 or self.st[-1] <= node.val:
self.st.append(node.val)
self.cnt = self.cnt + 1
ok = True
self.dfs(node.left)
self.dfs(node.right)
if ok:
self.st.pop()
def goodNodes(self, root: TreeNode) -> int:
self.dfs(root)
return self.cnt
FIRST APPROACH O(n^2)
SECOND APPROACH O(n)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the binary tree and for each node check if
all the nodes in the right subtree are greater than the current node and
if all the nodes in the left subtree are lower than the current node"""
def __init__(self):
self.val = None
self.part = ""
self.res = True
def dfs(self, node : TreeNode):
if not node:
return
if self.part == "left" and node.val >= self.val:
self.res = False
if self.part == "right" and node.val <= self.val:
self.res = False
self.dfs(node.left)
self.dfs(node.right)
def traverse_bt(self, node: TreeNode):
if not node:
return
self.val = node.val
self.part = "left"
self.dfs(node.left)
self.part = "right"
self.dfs(node.right)
self.traverse_bt(node.left)
self.traverse_bt(node.right)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
self.traverse_bt(root)
return self.res
230. Kth Smallest Element in a BST
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the list and keep track of a left boundary and a right
boundary and check at each iteration if they are in order."""
def dfs(self, left, node, right):
if not node:
return True
if not (left < node.val < right):
return False
return self.dfs(left,node.left ,node.val) and self.dfs(node.val,node.right,right)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
return self.dfs(float("-inf"), root, float("inf"))
APPROACH O(n)
105. Construct Binary Tree from Preorder and
Inorder Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Traverse the bst and keep track of a stack that will contain the
smallest values. When this stack has a size of k, then return
the top"""
def __init__(self):
self.st = []
self.res = None
def dfs(self, node: TreeNode, k : int):
if node == None or self.res != None:
return
self.dfs(node.left, k)
self.st.append(node.val)
if len(self.st) == k and self.res == None:
self.res = self.st[-1]
self.dfs(node.right, k )
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.dfs(root, k)
return self.res
124. Binary Tree Maximum Path Sum
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Recursive approach:
base case: if preorder or inorder arr are empty, then return None,
recursive case : The root is going to be pre[0],
mid is going to be inorder index of pre[0].
The right side until mid in the inorder arr is going to be the left subtree
and the left side, the left subtree."""
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
if not preorder or not inorder:
return None
root = TreeNode(preorder[0])
mid = inorder.index(preorder[0])
root.left = self.buildTree(preorder[1: mid + 1], inorder[:mid])
root.right = self.buildTree(preorder[mid + 1:], inorder[mid + 1:])
return root
297. Serialize and Deserialize Binary Tree
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
""" Recursive approach:
Base case: if node is None then return 0
Recursive case either:
root or root + left subtree or root + right subtree or
root + left + right subtrees"""
def __init__(self):
self.max_path_sum = - float("inf")
def dfs(self, node: TreeNode) -> int:
if not node:
return 0
l = self.dfs(node.left)
r = self.dfs(node.right)
self.max_path_sum = max(self.max_path_sum, node.val, node.val + l, node.val + r, node.val + l + r)
return max(node.val, node.val + l, node.val + r)
def maxPathSum(self, root: Optional[TreeNode]) -> int:
print(self.dfs(root))
return self.max_path_sum
208. Implement Trie (Prefix Tree)
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Codec:
"""Make a preorder traversal and create a string with the node values
Then iterate that string and recreate the binary tree!"""
def __init__(self):
self.res = ""
self.index = 0
def dfs(self, node: TreeNode):
if len(self.res) > 0:
self.res += ","
if not node:
self.res += "N"
return
self.res += str(node.val)
self.dfs(node.left)
self.dfs(node.right)
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
self.dfs(root)
print(self.res)
return self.res
def des(self, data):
if data[self.index] == "N":
return None
root = TreeNode(int(data[self.index]))
self.index = self.index + 1
root.left = self.des(data)
self.index = self.index + 1
root.right = self.des(data)
return root
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
data = data.split(",")
return self.des(data)
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))
211. Design Add and Search Words Data
Structure
class TrieNode:
def __init__(self):
self.child = [None] * 26
self.word_end = False
class Trie:
"""Start wirh an empty root node which is going to have
26 None values and a word_end value which is going
to represent the end of a word in this Trie"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
cur = self.root
for c in word:
index = ord(c) - ord('a')
if cur.child[index] is None:
new_node = TrieNode()
cur.child[index] = new_node
cur = cur.child[index]
cur.word_end = True
def search(self, word: str) -> bool:
cur = self.root
for c in word:
index = ord(c) - ord('a')
if cur.child[index] is None:
return False
cur = cur.child[index]
return cur.word_end
def startsWith(self, prefix: str) -> bool:
cur = self.root
for c in prefix:
index = ord(c) - ord('a')
if cur.child[index] is None:
return False
cur = cur.child[index]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
212. Word Search II
class TrieNode:
def __init__(self):
self.child = {}
self.word_end = False
class WordDictionary:
"""Use a Trie (Prefix Tree)
and for search create a dfs"""
def __init__(self):
self.root = TrieNode()
def addWord(self, word: str) -> None:
print("WORD : " ,word)
cur = self.root
for c in word:
if c not in cur.child:
cur.child[c] = TrieNode()
cur = cur.child.get(c)
cur.word_end = True
def dfs(self, node, index, word):
if index == len(word) and node.word_end == False:
return False
elif index == len(word) and node.word_end == True:
return True
c = word[index]
if c == ".":
for v in node.child.values():
if self.dfs(v, index + 1, word):
return True
return False
elif c in node.child:
return self.dfs(node.child.get(c), index + 1, word)
return False
def search(self, word: str) -> bool:
res = self.dfs(self.root, 0, word)
return res
# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)
973. K Closest Points to Origin
class TrieNode:
def __init__(self):
self.children = {}
self.is_word = False
def add_word(self, word):
cur = self
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
cur.is_word = True
class Solution:
"""Create a trie with all the words in words list
Start a dfs from each cell of the board and check if
the cur word exists in the trie!"""
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
root = TrieNode()
for w in words:
root.add_word(w)
ROWS = len(board)
COLS = len(board[0])
res = set()
vis = set()
def dfs(r, c, node, word):
if r < 0 or c < 0 or r == ROWS or c == COLS or (r, c) in vis or board[r][c] not in node.children:
return
vis.add((r, c))
node = node.children[board[r][c]]
word += board[r][c]
if node.is_word == True:
res.add(word)
dfs(r - 1, c, node, word)
dfs(r + 1, c, node, word)
dfs(r, c - 1, node, word)
dfs(r, c + 1, node, word)
vis.remove((r,c))
for r in range(ROWS):
for c in range(COLS):
dfs(r, c, root, "")
return list(res)
1046. Last Stone Weight
from heapq import heapify, heappush, heappop, nlargest
class KthLargest:
"""Retain k elements in the min heap"""
def __init__(self, k: int, nums: List[int]):
self.min_heap, self.k = nums, k
heapq.heapify(self.min_heap)
while len(self.min_heap) > k:
heapq.heappop(self.min_heap)
def add(self, val: int) -> int:
heapq.heappush(self.min_heap, val)
if len(self.min_heap) > self.k:
heapq.heappop(self.min_heap)
return self.min_heap[0]
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
1046. Last Stone Weight
from heapq import heapify, heappush, heappop
class Solution:
"""Create a max heap and while this heap has at least 2 values
smash the heaviest two stones """
def lastStoneWeight(self, stones: List[int]) -> int:
heap = []
heapify(heap)
for x in stones:
heappush(heap, -x)
while len(heap) > 1:
y = - heappop(heap)
x = - heappop(heap)
if x != y:
heappush(heap, -(y - x))
res = 0
while len(heap) > 0:
res = - heappop(heap)
return res
215. Kth Largest Element in an Array
from heapq import heapify, heappush, nsmallest
class Solution:
"""Create a small heap with tuples where the first element in the tuple
is the dist from a point to the origin and the second element is
the index in points arr, then get the k smallest elements in that heap"""
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
res = []
heapify(heap)
for i in range(0, len(points)):
p = points[i]
x = p[0]
y = p[1]
distance = sqrt(pow(abs(x - 0), 2) + pow(abs(y - 0), 2))
heappush(heap, (distance, i))
k_smallest = nsmallest(k, heap)
for i in k_smallest:
res.append(points[i[1]])
return res
621. Task Scheduler
from heapq import heapify, heappush, heappop, nlargest
class Solution:
"""Create a min heap and return the k_largest element from that heap"""
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = nums
heapify(heap)
k_largest = nlargest(k, heap)
return k_largest[-1]
355. Design Twitter
class Solution:
"""Retain a max heap of the frequencies and deque of the idle times"""
def leastInterval(self, tasks: List[str], n: int) -> int:
count = Counter(tasks)
max_heap = [-cnt for cnt in count.values()]
heapq.heapify(max_heap)
time = 0
q = deque()
while max_heap or q:
time += 1
if max_heap:
cnt = 1 + heapq.heappop(max_heap)
if cnt:
q.append([cnt, time + n])
if q and q[0][1] == time:
heapq.heappush(max_heap, q.popleft()[0])
return time
295. Find Median from Data Stream
from collections import defaultdict, deque
class Twitter:
def __init__(self):
self.follows = defaultdict(set)
self.feed = deque()
def postTweet(self, userId: int, tweetId: int) -> None:
self.feed.appendleft((userId, tweetId))
def getNewsFeed(self, userId: int) -> List[int]:
return [tweetId for user, tweetId in self.feed if userId == user or user in self.follows[userId]][:10]
def follow(self, followerId: int, followeeId: int) -> None:
self.follows[followerId].add(followeeId)
def unfollow(self, followerId: int, followeeId: int) -> None:
self.follows[followerId].discard(followeeId)
# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)
FIRST APPROACH : Sorting O(m∗nlogn)
class MedianFinder:
""""Store numbers in an arr on addNum
and on findMedian sort the arr and find the median"""
def __init__(self):
self.arr = []
def addNum(self, num: int) -> None:
self.arr.append(num)
def findMedian(self) -> float:
self.arr.sort()
if len(self.arr) % 2 == 0:
return (self.arr[len(self.arr) // 2] + self.arr[len(self.arr) // 2 - 1]) / 2
return self.arr[len(self.arr) // 2]
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
SECOND APPROACH: Heaps O(m * logn)
78. Subsets
class MedianFinder:
def __init__(self):
"""Using two heaps, which should be aproximately equal in size"""
self.small = []
self.large = []
def addNum(self, num: int) -> None:
if self.large and num > self.large[0]:
heapq.heappush(self.large, num)
else:
heapq.heappush(self.small, -num)
if len(self.small) > len(self.large) + 1:
val = - heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)
def findMedian(self) -> float:
if len(self.small) > len(self.large):
return -1 * self.small[0]
elif len(self.large) > len(self.small):
return self.large[0]
return (-self.small[0] + self.large[0]) / 2
# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
39. Combination Sum
class Solution:
"""Add an element to the curr path with each iteration"""
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def bkt(start, path):
res.append(path)
for i in range(start, len(nums)):
bkt(i + 1, path + [nums[i]])
bkt(0, [])
return res
FIRST APPROACH
class Solution:
"""Add an element to the curr path with each iteration"""
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
def bkt(start, path):
res.append(path)
for i in range(start, len(nums)):
bkt(i + 1, path + [nums[i]])
bkt(0, [])
return res
SECOND APPROACH
46. Permutations
class Solution:
"""Using dfs with two branches"""
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
def dfs(i, cur, total):
if total == target:
res.append(cur[:])
return
if i >= len(candidates) or total > target:
return
cur.append(candidates[i])
dfs(i, cur, total + candidates[i])
cur.pop()
dfs(i + 1, cur, total)
dfs(0, [], 0)
return res
90. Subsets II
class Solution:
"""A simple bkt solution,
recursive case if v doesn't appear in the cur solution
base case: if len(sol) = len(nums)"""
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
def ok(v):
for val in path:
if v == val:
return False
return True
def bkt():
if len(path) == len(nums):
print(path)
res.append(path[:])
if len(path) >= len(nums):
return
for v in nums:
if ok(v):
path.append(v)
bkt()
path.pop()
bkt()
return res
FIRST APPROACH: Hash Set
40. Combination Sum II
class Solution:
"""Backtracking solution with a hash set"""
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
path = []
hash_set = set()
nums.sort()
def bkt(i):
if tuple(path) not in hash_set:
hash_set.add(tuple(path))
res.append(path[:])
if len(path) >= len(nums):
return
for idx in range(i, len(nums)):
path.append(nums[idx])
bkt(idx + 1)
path.pop()
bkt(idx + 1)
bkt(0)
return res
79. Word Search
class Solution:
"""Backtracking solution, base case: if s == target:
recursive case, if I pass duplicated values and the s is not greater than the target"""
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res = []
path = []
candidates.sort()
s = 0
def bkt(i, s):
if s == target:
res.append(path[:])
return
for idx in range(i, len(candidates)):
if idx > i and candidates[idx] == candidates[idx - 1]:
continue
if (s + candidates[idx] ) > target:
break
path.append(candidates[idx])
s += candidates[idx]
bkt(idx + 1, s)
path.pop()
s -= candidates[idx]
bkt(0, 0)
return res
131. Palindrome Partitioning
class Solution:
"""Backtracking in plane approach with a set for visited indices"""
def exist(self, board: List[List[str]], word: str) -> bool:
m = len(board)
n = len(board[0])
vis = set()
def bkt(i, j, idx):
if idx == len(word):
return True
if i < 0 or j < 0 or i == m or j == n:
return False
if board[i][j] != word[idx] or (i, j) in vis:
return False
vis.add((i, j))
found = bkt(i - 1, j, idx + 1) or bkt(i + 1, j, idx + 1) or bkt(i, j + 1, idx + 1) or bkt(i, j - 1, idx + 1)
vis.remove((i, j))
return found
for i in range(0, m):
for j in range(0, n):
if bkt(i, j, 0):
return True
vis.clear()
return False
17. Letter Combinations of a Phone Number
class Solution:
"""Backtraking approach:
base case : idx == len(s)
recursive case : sub is a palindrome"""
def partition(self, s: str) -> List[List[str]]:
res = []
p = []
def bkt(idx):
if idx == len(s):
res.append(p[:])
return
sub = ""
for i in range(idx, len(s)):
c = s[i]
sub += c
if sub == sub[::-1]:
p.append(sub)
bkt(i + 1)
p.pop()
bkt(0)
return res
51. N-Queens
class Solution:
"""Backtraking recursive function:
Retain in a dict all the posible letters for each digit
Create a board with all the possible letters for each digit
Run a bkt for each row in the board:
Base case : when current row == rows in the board:
Recursive case: add each cell of the curr row to the current comb"""
def letterCombinations(self, digits: str) -> List[str]:
if len(digits) == 0:
return []
d = {
2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r', 's'],
8: ['t', 'u', 'v'],
9: ['w', 'x', 'y', 'z']
}
b = []
for digit in digits:
b.append(d.get(int(digit)))
res = []
comb = []
ROWS = len(b)
COLS = len(b[0])
def bkt(r):
if r == ROWS:
res.append("".join(comb))
return
for c in b[r]:
comb.append(c)
bkt(r + 1)
comb.pop()
bkt(0)
return res
200. Number of Islands
class Solution:
"""Backtraking recursive function:
base case: if r == n
recursive case: Try to add a Q to each column of the current row and
move to the next row"""
def solveNQueens(self, n: int):
res = []
board = [["."] * n for i in range(n)]
def bkt(r):
if r == n:
copy = ["".join(row) for row in board]
res.append(copy)
return
for c in range(n):
if self.isSafe(r, c, board):
board[r][c] = "Q"
bkt(r + 1)
board[r][c] = "."
bkt(0)
return res
def isSafe(self, r: int, c: int, board):
row = r - 1
while row >= 0:
if board[row][c] == "Q":
return False
row -= 1
row, col = r - 1, c - 1
while row >= 0 and col >= 0:
if board[row][col] == "Q":
return False
row -= 1
col -= 1
row, col = r - 1, c + 1
while row >= 0 and col < len(board):
if board[row][col] == "Q":
return False
row -= 1
col += 1
return True
695. Max Area of Island
class Solution:
"""Backtraking in plane:
Base case: if indices are in the grid, are not visitedm and the grid[i][j] is a part
of an island
Recursive case: go in all directions"""
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
cnt = 0
vis = set()
def dfs(i, j):
if i < 0 or j < 0 or i == m or j == n or (i, j) in vis or grid[i][j] == "0":
return
vis.add((i, j))
dfs(i - 1, j)
dfs(i + 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == "1" and (i,j) not in vis:
dfs(i, j)
cnt += 1
return cnt
133. Clone Graph
class Solution:
"""Backtraking in plane:
Base case: if indices are in the grid and represent a part of an island which
was not visited yet.
Recursive case: Go in all directions and return the sum"""
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
max_cells = 0
vis = set()
def bkt(i, j):
if i < 0 or i == m or j < 0 or j == n or (i, j) in vis or grid[i][j] == 0:
return 0
vis.add((i, j))
return 1 + bkt(i - 1, j) + bkt(i + 1, j) + bkt(i, j + 1) + bkt(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and (i, j) not in vis:
max_cells = max(max_cells, bkt(i, j))
return max_cells
994. Rotting Oranges
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
"""Use a hash table in order to store the copy for each node
and call a dfs with the starting node"""
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
oldToNew = {}
def dfs(node):
if node in oldToNew:
return oldToNew[node]
copy = Node(node.val)
oldToNew[node] = copy
for n in node.neighbors:
copy.neighbors.append(dfs(n))
return copy
return dfs(node)
417. Pacific Atlantic Water Flow
from collections import deque
class Solution:
"""Run a bfs from each rotten orange, if there are oranges which are not visited then return -1"""
def orangesRotting(self, grid: List[List[int]]) -> int:
ROWS = len(grid)
COLS = len(grid[0])
vis = set()
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]
q = deque()
for i in range(ROWS):
for j in range(COLS):
if grid[i][j] == 2:
grid[i][j] = -2
q.append((i, j, 0))
elif grid[i][j] == 1:
grid[i][j] = float("inf")
while q:
i, j, time = q.popleft()
grid[i][j] = min(grid[i][j], time)
for k in range(4):
iv = i + di[k]
jv = j + dj[k]
if iv < 0 or jv < 0 or iv == ROWS or jv == COLS or grid[iv][jv] <= 0 or (iv, jv) in vis:
continue
q.append((iv, jv, time + 1))
vis.add((i, j))
res = 0
for i in range(ROWS):
print(grid[i])
for j in range(COLS):
if grid[i][j] == float("inf"):
return -1
res = max(res, grid[i][j])
return res
130. Surrounded Regions
class Solution:
"""Use two sets for pacific and atlantic oceans
Run a dfs for both sets from each cell of the border
The pairs of indices which appear on both sets are
those who reach both pacific and atlantic"""
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS = len(heights)
COLS = len(heights[0])
pac = set()
atl = set()
def dfs(r, c, visit, prev_height):
if (r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or heights[r][c] < prev_height:
return
visit.add((r, c))
dfs(r - 1, c, visit, heights[r][c])
dfs(r + 1, c, visit, heights[r][c])
dfs(r, c - 1, visit, heights[r][c])
dfs(r, c + 1, visit, heights[r][c])
for c in range(COLS):
dfs(0, c, pac, heights[0][c])
dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
for r in range(ROWS):
dfs(r, 0, pac, heights[r][0])
dfs(r, COLS - 1, atl, heights[r][COLS - 1])
res = []
for r in range(ROWS):
for c in range(COLS):
if (r,c) in pac and (r,c) in atl:
res.append([r,c])
return res
1346. Check If N and Its Double Exist
FIRST APPROACH
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Run a DFS from each of the edges which contains an O and change that to an Y
Run a DFS from each O which is not on the edge and change the region to X
Change the Y's with O's
"""
ROWS = len(board)
COLS = len(board[0])
vis = set()
def bkt(i, j, c):
if i < 0 or j < 0 or i == ROWS or j == COLS or board[i][j] == 'X' or (i,j) in vis:
return
vis.add((i,j))
board[i][j] = c
bkt(i + 1, j, c)
bkt(i - 1, j, c)
bkt(i, j + 1, c)
bkt(i, j - 1, c)
for j in range(COLS):
if board[0][j] == 'O':
bkt(0, j, 'Y')
if board[ROWS - 1][j] == 'O':
bkt(ROWS - 1, j, 'Y')
for i in range(ROWS):
if board[i][0] == 'O':
bkt(i, 0, 'Y')
if board[i][COLS - 1] == 'O':
bkt(i, COLS - 1, 'Y')
for i in range(1, ROWS - 1):
for j in range(1, COLS - 1):
if board[i][j] == 'O':
bkt(i, j, 'X')
for i in range(ROWS):
for j in range(COLS):
if board[i][j] == 'Y':
board[i][j] = 'O'
class Solution:
""""
Brute Force solution
Test for each pair of indices if the condition applies
Time: O(n^2)
Space: O(1)
""""
def checkIfExist(self, arr: List[int]) -> bool:
arr.sort()
for i in range(0, len(arr)):
for j in range(0, len(arr)):
if i != j and arr[i] == (2 * arr[j]):
return True
return False
SECOND APPROACH
286. Walls And Gates - Explanation
class Solution:
"""
Use a hash table to keep track of all the numbers visited
If for the current number, the half or the double of it exxists in the
hash, then return True
Time: O(n)
Space: O(n)
"""
def checkIfExist(self, arr: List[int]) -> bool:
seen = set()
for n in arr:
if (n * 2) in seen or n / 2 in seen:
return True
seen.add(n)
return False
207. Course Schedule
from collections import deque
class Solution:
"""
Run a bfs from each tresure chest and update the neighbouring land cells
Time: O(m * n)
Space: O(m * n)
"""
def islandsAndTreasure(self, grid: List[List[int]]) -> None:
ROWS = len(grid)
COLS = len(grid[0])
q = deque()
for i in range(ROWS):
for j in range(COLS):
if grid[i][j] == 0:
q.append((i,j))
di = [-1, 0, 1, 0]
dj = [0, 1, 0, -1]
while q:
i,j = q.popleft()
for k in range(4):
iv = i + di[k]
jv = j + dj[k]
if iv < 0 or jv < 0 or iv == ROWS or jv == COLS \
or grid[iv][jv] == -1 or grid[iv][jv] <= grid[i][j] + 1:
continue
grid[iv][jv] = grid[i][j] + 1
q.append((iv,jv))
210. Course Schedule II
from collections import defaultdict
class Solution:
"""
Run through all the prerequisites courses and construct a directed graph
If a cycle exists in that graph, that means we can't take all the courses,
otherwise we can
Time: O(V + E)
Space: O(V + E)
"""
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
seen = set()
st = []
gr = defaultdict(list)
for a, b in prerequisites:
gr[b].append(a)
def dfs(v):
st.append(v)
seen.add(v)
for n in gr[v]:
if n in seen and n in st:
return False
if n not in seen:
if not dfs(n):
return False
st.pop()
return True
for v in range(numCourses):
if v not in seen:
if not dfs(v):
return False
return True
261. Graph Valid Tree
from collections import deque, defaultdict
class Solution:
"""
Create a driected graph from the prerequisites,
Run Khan's Algorithm for finding the topological sort
If we have all the vertices in the result that means we have a solution,
otherwise not.
Time: O(V + E)
Space: O(V + E)
"""
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
result = []
q = deque()
indegree = defaultdict(int)
gr = defaultdict(list)
for a, b in prerequisites:
gr[b].append(a)
indegree[a] += 1
for v in range(numCourses):
if indegree[v] == 0:
q.append(v)
while q:
v = q.popleft()
result.append(v)
for n in gr[v]:
indegree[n] -= 1
if indegree[n] == 0:
q.append(n)
if len(result) != numCourses:
return []
return result
323. Number of Connected Components In An
Undirected Graph
from collections import defaultdict
class Solution:
"""
Check if all vertices are part of the same connected component
and all vertices are visited during DFS and we don't have any cycles
Time: O(V + E)
Space: O(V + E)
"""
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) == 0:
return True
gr = defaultdict(list)
for a, b in edges:
gr[a].append(b)
gr[b].append(a)
seen = set()
st = []
def dfs(v, p):
seen.add(v)
st.append(v)
for n in gr[v]:
if n not in seen:
if not dfs(n, v):
return False
elif n in seen and n in st and n != p:
return False
st.pop()
return True
cycle = dfs(0, -1)
for v in range(n):
if v not in seen:
return False
return cycle
684. Redundant Connection
FIRST APPROACH NAIVE DFS
from collections import defaultdict
class Solution:
"""
Run a dfs for each unvisited vertex and increment the
number of connected components
Time: O(V + E)
Space: O(V + E)
"""
def countComponents(self, n: int, edges: List[List[int]]) -> int:
gr = defaultdict(list)
for a, b in edges:
gr[a].append(b)
gr[b].append(a)
seen = set()
cnt = 0
def dfs(v):
seen.add(v)
for n in gr[v]:
if n not in seen:
dfs(n)
for v in range(n):
if v not in seen:
cnt += 1
dfs(v)
return cnt
SECOND APPROACH OPTIMAL DFS
from collections import defaultdict
class Solution:
"""
Naive approach: remove every single edge from the end to the beggining
of edges and check if the graph is still connected in that case return
the removed edge
Time: O(E * (V + E))
Space: O(V + E)
"""
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
gr = defaultdict(list)
n = len(edges)
seen = set()
for a, b in edges:
gr[a].append(b)
gr[b].append(a)
def dfs(v):
seen.add(v)
for n in gr[v]:
if n not in seen:
dfs(n)
for i in range(n - 1, -1, -1):
seen.clear()
a, b = edges[i]
gr[a].remove(b)
gr[b].remove(a)
dfs(1)
if len(seen) == n:
return [a,b]
gr[a].append(b)
gr[b].append(a)
127. Word Ladder
FIRST APPROACH NAIVE BFS
from collections import defaultdict
class Solution:
"""
Optimal Approach: Run a DFS from the first node
If the node is visited, then it represents the start of a cycle
Otherwise run through all the neightbours and keep a hash with
all the vertices which are part of a cycle.
Traverse edges in reversed order, if the nodes of the current
edge are both part of a cycle then return the current edge
Time: O(V + E)
Space: O(V + E)
"""
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
n = len(edges)
gr = defaultdict(list)
for a, b in edges:
gr[a].append(b)
gr[b].append(a)
seen = set()
cycle = set()
cycle_start = -1
def dfs(v, p):
nonlocal cycle_start
if v in seen:
cycle_start = v
return True
seen.add(v)
for n in gr[v]:
if n == p:
continue
if dfs(n, v):
if cycle_start != -1:
cycle.add(v)
if cycle_start == v:
cycle_start = -1
return True
return False
dfs(1, -1)
for a, b in reversed(edges):
print(a, b, a in cycle, b in cycle)
if a in cycle and b in cycle:
return [a,b]
return []
from collections import defaultdict, deque
class Solution:
"""
BFS
"""
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
gr = defaultdict(list)
for i in range(len(wordList)):
cnt_diff = 0
for j in range(len(beginWord)):
if beginWord[j] != wordList[i][j]:
cnt_diff += 1
if cnt_diff == 1:
gr[0].append(i + 1)
gr[i + 1].append(0)
source = 0
dest = -1
for i in range(len(wordList)):
if wordList[i] == endWord:
dest = i + 1
for j in range(len(wordList)):
if i != j:
cnt_diff = 0
for z in range(len(wordList[i])):
if wordList[i][z] != wordList[j][z]:
cnt_diff += 1
if cnt_diff == 1:
gr[i + 1].append(j + 1)
gr[j + 1].append(i + 1)
if dest == -1:
return 0
q = deque()
q.append(source)
n = len(gr.keys())
if dest == -1 or n == 0:
return 0
seen = [0] * 5005
seen[source] = 1
while q:
v = q.popleft()
for ng in gr[v]:
if seen[ng] == 0:
seen[ng] = seen[v] + 1
q.append(ng)
if dest < len(seen):
return seen[dest]
return 0