These are some cool solutions to leetcode problems
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:
# 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
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]:
def recursive(ll, rl):
if not ll:
return rl
return recursive(ll.next, ListNode(ll.val, rl))
return recursive(head, None)
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 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
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 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
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 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
138. Copy List with Random Pointer
"""
# 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]
2. Add Two Numbers
# 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
141. Linked List Cycle
FIRST APPROACH O(n) memory
# 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
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 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
287. Find the Duplicate Number
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
146. LRU Cache
# 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
23. Merge k 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 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
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 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]
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 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
226. Invert 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
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 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
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 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
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 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
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 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
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 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
235. Lowest Common Ancestor of a Binary
Search Tree
# 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
102. Binary Tree Level Order 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 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
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 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
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 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
98. Validate Binary Search Tree
FIRST APPROACH O(n^2)
# 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
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 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"))
230. Kth Smallest Element in a BST
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 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
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:
""" 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
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 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
297. Serialize and Deserialize Binary 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))
208. Implement Trie (Prefix Tree)
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)
211. Design Add and Search Words Data
Structure
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)
212. Word Search II
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)
973. K Closest Points to Origin
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
1046. Last Stone Weight
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
215. Kth Largest Element in an Array
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]
621. Task Scheduler
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
355. Design Twitter
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)
295. Find Median from Data Stream
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)
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()
78. Subsets
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
39. Combination Sum
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
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
46. Permutations
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
90. Subsets II
FIRST APPROACH: Hash Set
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
40. Combination Sum II
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
79. Word Search
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
131. Palindrome Partitioning
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
17. Letter Combinations of a Phone Number
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
51. N-Queens
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
200. Number of Islands
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
695. Max Area of Island
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
133. Clone Graph
"""
# 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)
994. Rotting Oranges
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
417. Pacific Atlantic Water Flow
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
130. Surrounded Regions
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'
1346. Check If N and Its Double Exist
FIRST APPROACH
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
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
286. Walls And Gates - Explanation
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))
207. Course Schedule
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
210. Course Schedule II
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
261. Graph Valid Tree
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
323. Number of Connected Components In An
Undirected Graph
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
684. Redundant Connection
FIRST APPROACH NAIVE 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)
SECOND APPROACH OPTIMAL DFS
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 []
127. Word Ladder
FIRST APPROACH NAIVE BFS
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
261. Graph Valid Tree
from collections import defaultdict, deque
class Solution:
"""
Asign a number to each word
Create a graph representation where adjacent nodes are
words which differ by 1 letter
The run a BFS from Start node to the end word and that is the
shortest transformation sequence
Time: O(V ^ 2)
Space: O(V + E)
"""
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
gr = defaultdict(list)
dest = -1
for i in range(len(wordList)):
if wordList[i] == endWord:
dest = i + 1
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
if dest == -1:
return 0
for i in range(len(wordList) - 1):
for j in range(i + 1, len(wordList)):
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)
q = deque()
q.append(source)
seen = defaultdict(int)
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)
return seen[dest]
332. Reconstruct Itinerary
from collections import defaultdict
class Solution:
"""
Construct a graph with edges in lexicographicall order
Then Run a dfs and remove the edges to the neighbours for
each vertex
Time: O(V + E)
Space: O(V ^ 2)
"""
def findItinerary(self, tickets: List[List[str]]) -> List[str]:
gr = defaultdict(list)
for src, dest in sorted(tickets)[::-1]:
gr[src].append(dest)
res = []
def dfs(src):
while gr[src]:
dest = gr[src].pop()
dfs(dest)
res.append(src)
dfs("JFK")
return res[::-1]
1584. Min Cost to Connect All Points
FIRST APPROACH Prim's algorithm for MST
from collections import defaultdict
import heapq
class Solution:
"""
Create a complete undirected weighted graph of the points where
the weight of the edge between two points is the manhattan distance
Then run Prim's algorithm on the graph in order to
find the find the Minimum Spanning Tree ( MST )
which will tell us the min cost to connect all points
Time: O(LEN(points) ^ 2)
Space: O(V + E)
"""
def minCostConnectPoints(self, points: List[List[int]]) -> int:
gr = defaultdict(list)
for i in range(len(points)):
for j in range(i + 1, len(points)):
dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
gr[i].append((j, dist))
gr[j].append((i, dist))
pq = []
seen = set()
heapq.heappush(pq, (0, 0))
res = 0
while pq:
wt, v = heapq.heappop(pq)
if v in seen:
continue
res += wt
seen.add(v)
for u, wt in gr[v]:
if u not in seen:
heapq.heappush(pq, (wt, u))
return res
743. Network Delay Time
FIRST APPROACH Dijkstra's algorithm with deque
from collections import defaultdict
class Solution:
"""
Build a directed weighted graph from times array
Run Dijkstra's algorithm from source k
If not all the vertices were visited, then
we don;t have a solution so return -1
otherwise run through the distances and
take the maximum distance from k
Time: O(V * E)
Space: O(V + E)
"""
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
gr = defaultdict(list)
for u, v, w in times:
gr[u].append([v, w])
res = -1
q = deque()
q.append(k)
d = [float("inf")] * (n + 1)
d[k] = 0
while q:
v = q.popleft()
for ng, w in gr[v]:
if d[ng] > d[v] + w:
d[ng] = d[v] + w
q.append(ng)
for i in range(1, n + 1):
res = max(res, d[i])
if res == float("inf"):
return -1
return res
SECOND APPROACH Dijkstra's algorithm with Priority Queue
from collections import defaultdict
class Solution:
"""
Using a deque
Build a directed weighted graph from times array
Run Dijkstra's algorithm from source k
If not all the vertices were visited, then
we don;t have a solution so return -1
otherwise run through the distances and
take the maximum distance from k
Time: O(ElogV)
Space: O(V + E)
"""
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
gr = defaultdict(list)
for u, v, w in times:
gr[u].append([v, w])
res = -1
pq = []
heapq.heapify(pq)
heapq.heappush(pq, (0, k))
seen = set()
t = 0
while pq:
w, v = heapq.heappop(pq)
if v in seen:
continue
seen.add(v)
t = w
for ng, wn in gr[v]:
if ng not in seen:
heapq.heappush(pq, (w + wn, ng))
return t if len(seen) == n else -1
778. Swim in Rising Water
FIRST APPROACH DFS with binary search
class Solution:
"""
Run a DFS with binary search
Time: O(n ^ n log n)
Space: O(n ^ n)
"""
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
visit = set()
def dfs(node, t):
r, c = node
if min(r, c) < 0 or max(r, c) >= n or (r, c) in visit or grid[r][c] > t:
return False
if r == (n - 1) and c == (n - 1):
return True
visit.add((r,c))
return (dfs((r + 1, c), t) or
dfs((r - 1, c), t) or
dfs((r, c + 1), t) or
dfs((r, c - 1), t))
l = 0
r = n ** n - 1
sol = float("inf")
while l <= r:
m = (l + r) // 2
if dfs((0, 0), m):
sol = min(sol, m)
r = m - 1
else:
l = m + 1
visit.clear()
return sol
269. Alien Dictionary
class Solution:
"""
Build a directed graph from the words
Run a dfs and check if there is a cycle
in which case, there is no a valid order
Time: O(N + V + E)
Space: O(V + E)
"""
def foreignDictionary(self, words: List[str]) -> str:
adj = {c: set() for w in words for c in w}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i + 1]
minLen = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:minLen] == w2[:minLen]:
return ""
for j in range(minLen):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
break
visited = {}
res = []
def dfs(char):
if char in visited:
return visited[char]
visited[char] = True
for neighChar in adj[char]:
if dfs(neighChar):
return True
visited[char] = False
res.append(char)
for char in adj:
if dfs(char):
return ""
res.reverse()
return "".join(res)
787. Cheapest Flights Within K Stops
class Solution:
"""
Dijkstra's Algorithm with deque
Time: O(N * k)
Space: (V + E)
"""
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
prices = [float("inf")] * n
prices[src] = 0
adj = [[] for _ in range(n)]
for u, v, cst in flights:
adj[u].append([v, cst])
q = deque([(0, src, 0)])
while q:
cst, node, stops = q.popleft()
if stops > k:
continue
for nei, w in adj[node]:
nextCost = cst + w
if nextCost < prices[nei]:
prices[nei] = nextCost
q.append((nextCost, nei, stops + 1))
return prices[dst] if prices[dst] != float("inf") else -1
53. Maximum Subarray
class Solution:
"""
Using Kadane's Algorithm
Keeping a sum of the subarray ending at the current element
If the sum is negative, start the sum of a new subarray
Otherwise, expand the current subarray
Time: O(n)
Space: O(1)
"""
def maxSubArray(self, nums: List[int]) -> int:
sum , res = -float("inf"), -float("inf")
for x in nums:
if sum < 0:
sum = x
else:
sum += x
res = max(res, sum)
return res
55. Jump Game
class Solution:
"""
Traverse the list from right to left and keep a goal index
where I should jump
Check for each iteration if I could jump to the goal
in which case update the goal to the current index
Return if goal is equal with 0.
Time: O(n)
Space: O(1)
"""
def canJump(self, nums: List[int]) -> bool:
goal = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= goal:
goal = i
return goal == 0
45. Jump Game II
FIRST APPROACH O(n^2)
class Solution:
"""
Keep a goal index which os initally set at len(nums) - 1
while g != 0:
Search for the first index from which I can jump to goal,
increment the number of jumps and set the goal as that index
Time: O(n^2)
Space: O(1)
"""
def jump(self, nums: List[int]) -> int:
n = len(nums)
g = n - 1
steps = 0
while g != 0:
for i in range(0, g):
if i + nums[i] >= g:
g = i
steps += 1
break
return steps
SECOND APPROACH O(n)
class Solution:
"""
Keep track of a range left right which represents
the range of indices where I could jump
For each range, find the farthest distence where I could make the next jump
and update the range.
Time: O(n)
Space: O(1)
"""
def jump(self, nums: List[int]) -> int:
res = 0
l = r = 0
while r < len(nums) - 1:
farthest = 0
for i in range(l, r + 1):
farthest = max(farthest, i + nums[i])
l = r + 1
r = farthest
res += 1
return res
134. Gas Station
class Solution:
"""
If sum of gas is < sum of cost, then we don;t have a solution
Run through all stations and add to tank the diff between gas and cost
if the tank becomes negative, restart from the next station.
Time: O(n)
Space: O(1)
"""
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
tank = 0
res = 0
for i in range(len(gas)):
tank += (gas[i] - cost[i])
if tank < 0:
tank = 0
res = i + 1
return res
846. Hand of Straights
FIRST APPROACH BRUTE FORCE
class Solution:
"""
Build the res arr.
Time: O(n ^ 2)
space: O(n)
"""
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
n = len(hand)
if n % groupSize != 0:
return False
hand.sort()
res = []
seen = set()
while len(res) < n // groupSize:
gr = []
el = -1
while len(gr) < groupSize:
ok = False
for i in range(n):
if (el == -1 or el == hand[i]) and i not in seen:
gr.append(hand[i])
ok = True
el = hand[i] + 1
seen.add(i)
break
if ok == False:
return False
res.append(gr)
return True
SECOND APPROACH HASH TABLE
class Solution:
"""
Sort the hand
Keep a hash table with the frequencies of each number
Iterate through the numbers
Check if I can create a group with a number with frequency greater than 1
If not, return False
Time: O(n logn)
Space: O(n)
"""
def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:
if len(hand) % groupSize:
return False
count = Counter(hand)
hand.sort()
for num in hand:
if count[num]:
for i in range(num, num + groupSize):
if not count[i]:
return False
count[i] -= 1
return True
1899. Merge Triplets to Form Target Triplet
class Solution:
"""
Run trough all the triplets
If one of the values in the current triplet is
greater than the corresponding value n target, skip the triplet
Otherwise check if there are equal values between the current triplet
and the target, case in which retain the equal indices.
Time: O(n)
Space: O(1)
"""
def mergeTriplets(self, triplets: List[List[int]], target: List[int]) -> bool:
good = set()
for t in triplets:
if t[0] > target[0] or t[1] > target[1] or t[2] > target[2]:
continue
for i, v in enumerate(t):
if v == target[i]:
good.add(i)
return len(good) == 3
763. Partition Labels
from collections import defaultdict
class Solution:
"""
Retain the first and last occurences of each letter
in s and append then in a pq
The intersection of the intervals are the partitions
Add the number of elemnts in those partitions to the res.
Time: O(n)
Space: O(n)
"""
def partitionLabels(self, s: str) -> List[int]:
f = defaultdict(list)
pq = []
res = []
heapq.heapify(pq)
for i in range(len(s)):
c = s[i]
if c not in f:
f[c] = [i,i]
else:
f[c][1] = i
for k, v in f.items():
heapq.heappush(pq, v)
a,b = heapq.heappop(pq)
if not pq:
return [b - a + 1]
while pq:
c, d = heapq.heappop(pq)
if c <= b:
b = max(b, d)
else:
res.append(b - a + 1)
a = c
b = d
res.append(b - a + 1)
return res
678. Valid Parenthesis String
class Solution:
"""
Keep track of the indices of open pharantheses and indices
of asterisks.
Time: O(n)
Space: O(1)
"""
def checkValidString(self, s: str) -> bool:
st = []
ast = []
for i in range(len(s)):
c = s[i]
if c == "(":
st.append(i)
if c == "*":
ast.append(i)
if c == ")":
if len(st) > 0:
st.pop()
elif len(ast) > 0:
ast.pop()
else:
return False
while st and ast:
lp = st.pop()
last = ast.pop()
if lp > last:
return False
return len(st) <= len(ast)
57. Insert Interval
class Solution:
"""
Iterate through the entire list and merge the intervals if necessary.
Time: O(n)
Space: O(n)
"""
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]:
res.append(intervals[i])
else:
newInterval = [
min(newInterval[0], intervals[i][0]),
max(newInterval[1], intervals[i][1]),
]
res.append(newInterval)
return res
56. Merge Intervals
class Solution:
"""
Sort the intervals arr, then iterate through it and
merge the intervals if necessary.
Time: O(nlog)
Space: O(n)
"""
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
res = []
intervals.sort()
jump = -1
n = len(intervals)
for i in range(n):
if i <= jump:
continue
a,b = intervals[i]
while i + 1 < n and intervals[i + 1][0] <= b:
i += 1
a = min(a, intervals[i][0])
b = max(b, intervals[i][1])
jump = i
res.append([a,b])
return res
435. Non-overlapping Intervals
class Solution:
"""
Sort the intervals, then iterate trough it and
merge the intervals if necessary.
At each merge, increment the res.
Time: O(nlogn)
Space: O(1)
"""
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
res = 0
prev_end = intervals[0][1]
for start, end in intervals[1:]:
if start >= prev_end:
prev_end = end
else:
res += 1
prev_end = min(end, prev_end)
return res
252. Meeting Rooms
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
Sort the intervals based on the start value,
then check if two adjecent intervals overlap.
Time: O(nlogn)
Space: O(n)
"""
def canAttendMeetings(self, intervals: List[Interval]) -> bool:
intervals.sort(key=lambda x: x.start)
n = len(intervals)
for i in range(n - 1):
b = intervals[i].end
if intervals[i + 1].start < b:
return False
return True
253. Meeting Rooms II
"""
Definition of Interval:
class Interval(object):
def __init__(self, start, end):
self.start = start
self.end = end
"""
class Solution:
"""
Sort the intervals based on the starting time.
Iterate trough the intervals and check if they overlap,
in which case we need another day.
Keep track aff the ending times for the meetings of each day
in a priority queue, and get the lowest one
as the prev end time for each iteration.
Time: O(nlogn)
Space: O(n)
"""
def minMeetingRooms(self, intervals: List[Interval]) -> int:
n = len(intervals)
if n == 0:
return 0
intervals.sort(key=lambda x: x.start)
prev_end = -1
pq = []
heapq.heapify(pq)
heapq.heappush(pq,prev_end)
days = 1
for i in range(n):
st, end = intervals[i].start, intervals[i].end
prev_end = heapq.heappop(pq)
if st < prev_end:
days += 1
heapq.heappush(pq, prev_end)
heapq.heappush(pq, end)
else:
heapq.heappush(pq, end)
return days
1851. Minimum Interval to Include Each Query
class Solution:
"""
Sorting Intervals and queries.
Time: O(nlogn + qlogq)
Space: O(n)
"""
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
intervals.sort()
minHeap = []
res = {}
i = 0
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
l, r = intervals[i]
heapq.heappush(minHeap, (r - l + 1, r))
i += 1
while minHeap and minHeap[0][1] < q:
heapq.heappop(minHeap)
res[q] = minHeap[0][0] if minHeap else -1
return [res[q] for q in queries]
70. Climbing Stairs
class Solution:
"""
A staircase with 1 step can be climbed in 1 way
A staircase with 2 steps cand be climbed in 2 ways
A staircase with 3 steps can be climbed in 1 + 2 ways = 3
...
A staircase with n steps can be climbed with s(n - 1) + s(n - 2) where
s(n) represents the number of ways in which I can climb a staircase with
n steps.
Time: O(n)
Space: O(1)
"""
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
a = 1
b = 2
for i in range(3, n + 1):
c = a + b
a = b
b = c
return c