Solutions to Leetcode
Here lie my implementations and notes for various leetcode problems.
1. Two Sum
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
table = dict()
for i, num in enumerate(nums):
if target - num in table.keys():
return [i, table[target-num]]
table[num] = i
return []
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]:
# get numbers out:
head = l1
l1_nums = [] # [2,4,3]
while head:
l1_nums.append(head.val)
head = head.next
print("l1_nums:", l1_nums)
head = l2
l2_nums = [] # [5,6,4]
while head:
l2_nums.append(head.val)
head = head.next
print("l2_nums:", l2_nums)
# reverse the lists and turn them into ints:
if l1_nums is not None:
l1_nums = list(reversed(l1_nums))
if l2_nums is not None:
l2_nums = list(reversed(l2_nums))
l1_num = int(''.join(map(str, l1_nums))) #342
l2_num = int(''.join(map(str, l2_nums))) #465
sum = l1_num + l2_num
sum_list = list(map(int, str(sum))) # [8, 0, 7]
#if sum_list is not None:
# sum_list = list(reversed(sum_list)) # [7, 0, 8]
print(sum_list)
# LN(7) <- LN(0) <- LN(8)
tail = None
for i in range(len(sum_list)):
next = ListNode(sum_list[i], tail)
i = i + 1
tail = next
return tail
3. Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = r = 0
longest_length = r - l
counts = collections.defaultdict(int)
while r < len(s):
if counts[s[r]] == 0:
counts[s[r]] += 1
r += 1
else:
counts[s[l]] = 0
l += 1
longest_length = max(r - l, longest_length)
return longest_length
4. Median of Two Sorted Arrays
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
int totalSize = nums1Size + nums2Size;
int merged[totalSize];
int i = 0, j = 0, k = 0;
while (i < nums1Size && j < nums2Size) {
if (nums1[i] < nums2[j]) {
merged[k++] = nums1[i++];
} else {
merged[k++] = nums2[j++];
}
}
while (i < nums1Size) {
merged[k++] = nums1[i++];
}
while (j < nums2Size) {
merged[k++] = nums2[j++];
}
if (totalSize % 2 == 0) {
return (double)(merged[totalSize/2] + merged[totalSize/2 - 1])/2;
} else {
return (double)merged[totalSize/2];
}
}
11. Container With Most Water
class Solution:
def maxArea(self, height: List[int]) -> int:
"""
sorted_indices = sorted(range(len(height)),
key=lambda index: height[index], reverse=True)
maxArea = 0
print(sorted_indices)
for i, s in enumerate(sorted_indices):
for j, t in enumerate(sorted_indices):
if j >= i:
container_height = min(height[s],height[t])
area = abs(s-t) * container_height
if area > maxArea:
maxArea = area
return maxArea
# Time Limit Exceeded | 54/65 testcases passed
"""
# two pointer approach
maxArea = 0
leftPointer = 0
rightPointer = len(height)-1
while leftPointer != rightPointer:
area = min(height[leftPointer],height[rightPointer]) * abs(leftPointer - rightPointer)
if area > maxArea:
maxArea = area
if height[leftPointer] < height[rightPointer]:
leftPointer += 1
else:
rightPointer -= 1
return maxArea
12. Integer to Roman
class Solution:
def intToRoman(self, num: int) -> str:
values = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000][::-1]
symbols = ["I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M"][::-1]
romans = list(zip(values, symbols))
num_as_str = str(num)
digits = len(num_as_str)
result = ""
for val, sym in romans:
multiplier = num // val
if multiplier:
result += sym * multiplier
num %= val
return result
15. 3Sum
#from itertools import combinations
"""
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
def twoSum(numbers: List[int], target: int) -> List[List[int]]:
res = []
if not numbers:
return []
leftPointer, rightPointer = 0, len(numbers) - 1
while leftPointer < rightPointer:
status = numbers[leftPointer] + numbers[rightPointer]
if status < target:
leftPointer += 1
elif status > target:
rightPointer -= 1
else:
res.append([leftPointer + 1, rightPointer + 1])
# skip duplicates on BOTH sides
lv, rv = numbers[leftPointer], numbers[rightPointer]
while leftPointer < rightPointer and numbers[leftPointer] == lv:
leftPointer += 1
while leftPointer < rightPointer and numbers[rightPointer] == rv:
rightPointer -= 1
return res
#combinations_of_3 = list(combinations(nums,3))
#print(len(combinations_of_3))
#out = []
#for c in combinations_of_3:
# if sum(c) == 0:
# if sorted(c) not in out:
# out.append(sorted(c))
#
#return out
nums.sort()
out = []
for i,n in enumerate(nums):
if n>0:
break # sorted, so a positive number means we can never get to 0
if i>0 and n == nums[i-1]: # skip if same as previous
continue
print(nums[i+1:])
idxs = twoSum(nums[i+1:], 0-n)
if idxs:
for idx in idxs:
out.append([n, nums[i+idx[0]], nums[i+idx[1]]])
return out
"""
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
def twoSum(numbers: List[int], target: int) -> List[List[int]]:
res: List[List[int]] = []
if not numbers:
return res
leftPointer, rightPointer = 0, len(numbers) - 1
while leftPointer < rightPointer:
status = numbers[leftPointer] + numbers[rightPointer]
if status < target:
leftPointer += 1
elif status > target:
rightPointer -= 1
else:
# record (keeping your 1-based indexing)
res.append([leftPointer + 1, rightPointer + 1])
# skip duplicates on BOTH sides
lv, rv = numbers[leftPointer], numbers[rightPointer]
while leftPointer < rightPointer and numbers[leftPointer] == lv:
leftPointer += 1
while leftPointer < rightPointer and numbers[rightPointer] == rv:
rightPointer -= 1
return res
nums.sort()
out: List[List[int]] = []
for i, n in enumerate(nums):
if n > 0:
break # remaining numbers are positive → no more triplets
if i > 0 and n == nums[i - 1]:
continue # skip duplicate anchors
idxs = twoSum(nums[i + 1:], -n) # search suffix
for l1, r1 in idxs: # l1/r1 are 1-based within the suffix
out.append([n, nums[i + l1], nums[i + r1]])
return out
16. 3Sum Closest
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums = sorted(nums)
n = len(nums)
closest_sum = 9999999
for i in range(n):
if i > 0 and nums[i] == nums[i-1]:
continue
lo, hi = i + 1, n - 1
while lo < hi:
cur_sum = nums[i] + nums[lo] + nums[hi]
if abs(cur_sum - target) < abs(closest_sum - target):
closest_sum = cur_sum
if cur_sum == target:
return cur_sum
elif cur_sum < target:
lo += 1
else:
hi -= 1
return closest_sum
17. Letter Combinations of a Phone Number
20. Valid Parentheses
class Solution:
def isValid(self, s: str) -> bool:
stack = []
hashMap = {
')': '(',
'}': '{',
']': '['
}
for element in s:
if stack and (element in hashMap and stack[-1] == hashMap[element]):
stack.pop()
else:
stack.append(element)
return not stack
21. Merge Two Sorted Lists
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
if list2.val < list1.val:
start, other = list2, list1
else:
start, other = list1, list2
curr = start
while curr and other:
if curr.next is None or curr.next.val > other.val:
other_next = other.next
other.next = curr.next
curr.next = other
other = other_next
curr = curr.next
else:
curr = curr.next
return start
36. Valid Sudoku
def checkGroup(group: List[str]) -> bool:
print(group)
uniques = list(set(group))
counts = {s: group.count(s) for s in uniques}
del counts['.']
print(counts.values())
if any(value > 1 for value in counts.values()):
print("tripped")
return False
if any(int(key) > 9 or int(key) < 1 for key in counts.keys()):
return False
return True
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
# check rows:
n = len(board)
for row in board:
if not checkGroup(row):
return False
# check columns:
for i in range(n):
col = [row[i] for row in board]
if not checkGroup(col):
return False
# check grids:
for row_offset in range(0,n,3):
for col_offset in range(0,n,3):
subgrid = []
for r in range(row_offset, row_offset + 3):
for c in range(col_offset, col_offset + 3):
subgrid.append(board[r][c])
if not checkGroup(subgrid):
return False
return True
37. Sudoku Solver
from typing import List
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
N = len(board)
empties = []
rows = [set() for _ in range(N)]
cols = [set() for _ in range(N)]
boxes = [set() for _ in range(N)]
def find_empties():
for i, row in enumerate(board):
for j, val in enumerate(row):
if val == '.':
empties.append((i, j))
else:
rows[i].add(val)
cols[j].add(val)
boxes[(i // 3) * 3 + (j // 3)].add(val)
def validMove(pos):
r, c = pos
b = (r // 3) * 3 + (c // 3)
valid_moves = []
for d in "123456789":
if d not in rows[r] and d not in cols[c] and d not in boxes[b]:
valid_moves.append(d)
return valid_moves
def dfs_rec(idx):
if idx == len(empties):
return True
r, c = empties[idx]
b = (r // 3) * 3 + (c // 3)
for move in validMove((r, c)):
board[r][c] = move
rows[r].add(move)
cols[c].add(move)
boxes[b].add(move)
if dfs_rec(idx + 1):
return True
board[r][c] = '.'
rows[r].remove(move)
cols[c].remove(move)
boxes[b].remove(move)
return False
find_empties()
dfs_rec(0)
41. First Missing Positive
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
"""shockingly this code is accepted despite the O(nlogn) tc and O(n) sc
# will remove this assumption later:
nums = sorted(list(set(nums)))
one = False
location = 0
for i, num in enumerate(nums):
if num == 1:
one = True
location = i
if one == False:
return 1
# check subsequent:
j = location
spi = 1
while j < len(nums):
if nums[j] == spi:
spi += 1
j += 1
continue
return spi
return spi
"""
# cyclic sort:
n = len(nums)
# place each positive integer at the respective index within nums
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] -1], nums[i] = nums[i], nums[nums[i] -1] # swap
# linear search for first discrepancy
for i in range(n):
if nums[i] != i + 1:
return i + 1 # returns discrep
# or returns n + 1
return n + 1
42. Trapping Rain Water
class Solution:
def trap(self, height: List[int]) -> int:
l_wall = r_wall = 0
n = len(height)
max_left = [0] * n
max_right = [0] * n
for i in range(n):
j = -i - 1
max_left[i] = l_wall
max_right[j] = r_wall
l_wall = max(l_wall, height[i])
r_wall = max(r_wall, height[j])
summ = 0
for i in range(n):
pot = min(max_left[i], max_right[i])
summ += max(0, pot - height[i])
return summ
45. Jump Game II
46. Permutations
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(start, end):
if start == end:
result.append(nums[:])
return
for i in range(start, end):
nums[start], nums[i] = nums[i], nums[start]
backtrack(start + 1, end)
nums[start], nums[i] = nums[i], nums[start]
result = []
backtrack(0, len(nums))
return result
49. Group Anagrams
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
"""
#O(mnlogn) sorting bruteforce
print(strs)
base = []
for string in strs:
base.append("".join((sorted(string))))
print(base)
# find indices that are all the same
idxs = []
marked = []
for i, word1 in enumerate(base):
i_likes = []
for j, word2 in enumerate(base):
if word1 == word2 and i <= j and j not in marked:
marked.append(j)
i_likes.append(j)
if i_likes:
idxs.append(i_likes)
print(idxs)
# replace indices with words:
ans = []
for tup in idxs:
sublist = []
for idx in tup:
sublist.append(strs[idx])
ans.append(sublist)
return ans
"""
# hashmap: O(m*n)
hash = {}
for s in strs:
count = [0] * 26
for c in s:
count[ord(c)-ord("a")] += 1
key = tuple(count)
if key in hash:
hash[key].append(s)
else:
hash[key] = [s]
return list(hash.values())
53. Maximum Subarray
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
for i, n in enumerate(nums):
dp[i] = max(n, dp[i-1] + n)
return max(dp)
54. Spiral Matrix
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
ret = []
while matrix:
ret += (matrix.pop(0))
if matrix and matrix[0]:
for row in matrix:
ret.append(row.pop())
if matrix:
ret += (matrix.pop()[::-1])
if matrix and matrix[0]:
for row in matrix[::-1]:
ret.append(row.pop(0))
return ret
56. Merge Intervals
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort()
merged = []
for start, end in intervals:
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return merged
70. Climbing Stairs
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
77. Combinations
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start, path):
if len(path) == k:
result.append(path[:])
return
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
result = []
backtrack(1, [])
return result
78. Subsets
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(start, path):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
result = []
backtrack(0, [])
return result
88. Merge Sorted Array
// function to insert value m at position n in array a by shifting the array
void insert(int *a, int m, int n, int l) {
printf("debug %d %d %d\n", m, n, l);
int temp = a[l-1];
for(int i=l-1; i>n; i--) {
a[i] = a[i-1];
}
a[0] = temp;
a[n] = m;
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int p1 = m - 1;
int p2 = n - 1;
for (int p = m + n - 1; p >= 0; p--) {
if (p2 < 0) {break;}
else {
nums1[p] = (p1 >= 0 && nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
}
}
}
/*
int offset = 0;
for (int i = 0; i < m; i++) {
for (int j = 0 + offset; j < n; j++) {
// if less than first element
if (i == 0 && nums1[i] >= nums2[j]) {
printf("insert start\n");
insert(nums1, nums2[j], i, m + n);
offset++;
break;
}
// if greater than last element
else if (i == m - 1 && nums1[i] <= nums2[j]) {
printf("insert end\n");
insert(nums1, nums2[j], i, m + n);
offset++;
break;
}
else if (nums1[i] <= nums2[j] && (i + 1 < m && nums1[i+1] >= nums2[j])){ // belongs in middle
printf("insert middle\n");
insert(nums1, nums2[j], i+1, m + n);
offset++;
break;
}
}
}
}
*/
92. Reverse Linked List II
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
if not head or left == right:
return head
dummy = ListNode(0, head)
leftprev = dummy
curr = head
for _ in range(left - 1):
leftprev = curr
curr = curr.next
prev = None
tail = curr
for _ in range(right - left + 1):
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
leftprev.next = prev
tail.next = curr
return dummy.next
100. Same Tree
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
stack = [(p, q)]
while stack:
node1, node2 = stack.pop()
if not node1 and not node2:
continue
elif None in [node1, node2] or node1.val != node2.val:
return False
stack.append((node1.left, node2.left))
stack.append((node1.right, node2.right))
return True
102. Binary Tree Level Order Traversal
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
queue = deque([root])
result = []
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
104. Maximum Depth of Binary Tree
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
108. Convert Sorted Array to Binary Search Tree
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def convert(left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = convert(left, mid - 1)
node.right = convert(mid + 1, right)
return node
return convert(0, len(nums) - 1)
111. Minimum Depth of Binary Tree
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, level = queue.popleft()
if not node.left and not node.right:
return level
if node.left:
queue.append((node.left, level + 1))
if node.right:
queue.append((node.right, level + 1))
return 0
112. Path Sum
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if not root:
return False
stack = [(root, root.val)]
while stack:
node, val = stack.pop()
if not node.left and not node.right and val == targetSum:
return True
if node.right:
stack.append((node.right, val + node.right.val))
if node.left:
stack.append((node.left, val + node.left.val))
return False
121. Best Time to Buy and Sell Stock
class Solution:
def maxProfit(self, prices: List[int]) -> int:
l, r = 0, 1
maxP = 0
while r != len(prices):
if prices[l] < prices[r]:
prof = prices[r] - prices[l]
maxP = max(maxP, prof)
else:
l = r
r += 1
return maxP
128. Longest Consecutive Sequence
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums) # O(n) average time, O(n) space
longest = 0
for n in numSet: # ← iterate uniques to avoid duplicate re-walks
# check if it is the start of the sequence
if (n - 1) not in numSet:
length = 0
while (n + length) in numSet:
length += 1
longest = max(length, longest)
return longest
133. Clone Graph
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return node
queue = deque([node])
clones = {node.val: Node(node.val)}
while queue:
curr = queue.popleft()
curr_clone = clones[curr.val]
for neighbor in curr.neighbors:
if neighbor.val not in clones:
clones[neighbor.val] = Node(neighbor.val)
queue.append(neighbor)
curr_clone.neighbors.append(clones[neighbor.val])
return clones[node.val]
136. Single Number
class Solution:
def singleNumber(self, nums: List[int]) -> int:
xor = 0
for num in nums:
xor ^= num
return xor
141. Linked List Cycle
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
curr = head
visited = set()
while curr:
if curr not in visited:
visited.add(curr)
else:
return True
curr = curr.next
return False
150. Evaluate Reverse Polish Notation
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token not in {'+', '-', '*', '/'}:
stack.append(int(token))
else:
op1 = stack.pop()
op2 = stack.pop()
if token == '+':
stack.append(op2 + op1)
elif token == '*':
stack.append(op2 * op1)
elif token == '/':
stack.append(int(op2 / op1))
elif token == '-':
stack.append(op2 - op1)
return stack.pop()
151. Reverse Words in a String
import re
class Solution:
def reverseWords(self, s: str) -> str:
splt = re.split('\\s+',s)
splt.reverse()
return " ".join(splt).strip()
152. Maximum Product Subarray
153. Find Minimum in Rotated Sorted Array
155. Min Stack
class MinStack:
def __init__(self):
self.data = []
def push(self, val: int) -> None:
self.data.append(val)
def pop(self) -> None:
self.data.pop()
def top(self) -> int:
return self.data[-1]
def getMin(self) -> int:
return min(self.data)
167. Two Sum II - Input Array Is Sorted
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
leftPointer, rightPointer = 0, len(numbers) - 1
while leftPointer != rightPointer:
status = numbers[leftPointer] + numbers[rightPointer]
if status < target:
leftPointer += 1
elif status > target:
rightPointer -= 1
else:
return [leftPointer+1, rightPointer+1]
return []
169. Majority Element
class Solution:
def majorityElement(self, nums: List[int]) -> int:
"""my naive soln
d = {x:nums.count(x) for x in nums}
a, b = d.keys(), d.values()
max_value = max(b)
max_index = list(b).index(max_value)
return (list(a)[max_index])
# o(n^2) because we run o(n) count on each x
"""
"""
candidate = 0
count = 0
# phase 1: find candidate
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
"""
count = {} # dictionary.
res, maxCount = 0, 0
for n in nums:
count[n] = 1 + count.get(n, 0)
res = n if count[n] > maxCount else res
maxCount = max(count[n], maxCount)
return res
200. Number of Islands
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
visited = set()
count = 0
m = len(grid)
n = len(grid[0])
def bfs(r, c):
q = deque()
visited.add((r, c))
q.append((r, c))
while q:
row, col = q.popleft()
directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for dr, dc in directions:
r, c = row + dr, col + dc
if (r in range(m) and c in range(n) and grid[r][c] == "1" and (r, c) not in visited):
q.append((r, c))
visited.add((r, c))
for i in range(m):
for j in range(n):
if grid[i][j] == '1' and (i, j) not in visited:
count += 1
bfs(i, j)
return count
202. Happy Number
class Solution:
def isHappy(self, n: int) -> bool:
"""
# N is input size, n is number of digits of N
visited = set() # O(log n)
while n != 1:
m = 0
if n in visited: # O(1)
return False
digits = [int(digit) for digit in str(n)] # O(log n)
for digit in digits: # O(log n)
m += digit*digit
visited.add(n)
n = m
return True
"""
# Time Complexity: O(log n) - number of digits in n
# Space Complexity: O(log n) - size of visited set
visited: set[int] = set() # Track numbers we've seen to detect cycles
while n not in visited:
visited.add(n)
if n == 1:
return True
# Calculate sum of squared digits
current_sum: int = 0
while n > 0:
digit: int = n % 10
current_sum += digit * digit
n //= 10
n = current_sum
return False # We found a cycle, number is not happy
203. Remove Linked List Elements
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
curr = head
dummy = ListNode(-1, head)
prev = dummy
while curr:
if curr.val == val:
prev.next = curr.next
curr = curr.next
else:
prev = curr
curr = curr.next
return dummy.next
206. Reverse Linked List
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode *new = NULL;
struct ListNode *curr = head;
while (curr != NULL) {
struct ListNode *tmp = curr->next;
curr->next = new;
new = curr;
curr = tmp;
}
return new;
}
207. Course Schedule
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = {course: [] for course in range(numCourses)}
for course, pre in prerequisites:
adj[course].append(pre)
for course in range(numCourses):
stack = [(course, set())]
while stack:
cur_course, visited = stack.pop()
if cur_course in visited:
return False
visited.add(cur_course)
for pre in adj[cur_course]:
stack.append((pre, visited.copy()))
adj[course] = []
return True
209. Minimum Size Subarray Sum
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l = 0
total = 0
res = float('inf')
for r in range(len(nums)):
total += nums[r]
while total >= target:
res = min(res, r - l + 1)
total -= nums[l]
l += 1
if res == float('inf'):
return 0
else:
return res
215. Kth Largest Element in an Array
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
heap = nums[:k]
heapq.heapify(heap)
for num in nums[k:]:
if num > heap[0]:
heapq.heapreplace(heap, num)
return heap[0]
217. Contains Duplicate
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
#return True if len(set(nums)) != len(nums) else False
return len(set(nums)) != len(nums)
219. Contains Duplicate II
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
seen = set()
for i, num in enumerate(nums):
if num in seen:
return True
seen.add(num)
if len(seen) > k:
seen.remove(nums[i - k])
return False
225. Implement Stack using Queues
class MyStack:
def __init__(self):
self.stack = deque()
def push(self, x: int) -> None:
self.stack.append(x)
def pop(self) -> int:
return self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def empty(self) -> bool:
return True if len(self.stack) == 0 else False
226. Invert Binary Tree
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
stack = [root]
while stack:
curr = stack.pop()
if curr:
curr.left, curr.right = curr.right, curr.left
stack.extend([curr.right, curr.left])
return root
230. Kth Smallest Element in a BST
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while root or stack:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
234. Palindrome Linked List
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
vals = []
curr = head
while curr:
vals.append(curr.val)
curr = curr.next
return vals == vals[::-1]
235. Lowest Common Ancestor of a Binary Search Tree
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
small = min(p.val, q.val)
large = max(p.val, q.val)
while root:
if root.val > large:
root = root.left
elif root.val < small:
root = root.right
else:
return root
return None
236. Lowest Common Ancestor of a Binary Tree
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == None or root == p or root == q:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left != None and right != None:
return root
if left != None:
return left
return right
238. Product of Array Except Self
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
"""o(n^2)
res = [1] * len(nums)
for i,num in enumerate(nums):
for j in range(len(nums)):
res[j] *= (num if i !=j else 1)
return res
"""
"""better code, but still not fast enough
# calculate prefix
prefix = [0] * (len(nums) + 2)
prefix[0], prefix[len(nums)+1] = 1,1
for i in range(len(nums)):
prefix[i+1] = (nums[i] * prefix[i])
print(prefix)
# calculate postfix
postfix = [0] * (len(nums) + 2)
postfix[0], postfix[len(nums)+1] = 1,1
print(postfix)
for i in reversed(range(len(nums))):
postfix[i+1] = (nums[i] * postfix[i+2])
print(postfix)
# multiply prefix with postfix for each n
res = [0] * len(nums)
for i in range(len((nums))):
print(res)
res[i] = prefix[i] * postfix[i+2]
return res
"""
# the issue above was space complexity.
# we are going to update the result array for both prefix and postfix
res = [1] * len(nums)
# prefix loop:
for i in range(1, len(nums)):
res[i] = nums[i-1] * res[i-1]
postfix = 1
for j in reversed(range(len(nums)-1)):
postfix *= nums[j+1]
res[j] *= postfix
return res
239. Sliding Window Maximum
from collections import deque
#from typing import List
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
"""anki
q = deque()
left = right = 0
def slide_right():
nonlocal right
while q and nums[q[-1]] < nums[right]:
q.pop()
q.append(right)
right += 1
def slide_left():
nonlocal left
left += 1
if q and left > q[0]:
q.popleft()
result = []
while right < k:
slide_right()
result.append(nums[q[0]])
while right < len(nums):
slide_right()
slide_left()
result.append(nums[q[0]])
return result
"""
output = []
l = r = 0
q = deque()
while r < len(nums):
while q and nums[q[-1]] < nums[r]:
q.pop()
q.append(r)
# remove left val from window
if l > q[0]:
q.popleft()
if (r+1) >= k:
output.append(nums[q[0]])
l += 1
r+= 1
return output
"""naive
left = 0
right = k
result = []
N = len(nums)
while right <= N:
result.append(max(nums[left:right]))
left += 1
right += 1
return result
"""
260. Single Number III
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
nums_str = str(nums)
nums_set = set(nums)
ans = []
for i in nums_set:
if nums_str.count(str(i)) == 1:
ans.append(i)
return ans
268. Missing Number
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return sum(range(len(nums)+1))-sum(nums)
303. Range Sum Query - Immutable
class NumArray:
def __init__(self, nums: List[int]):
self.acc_nums = [0]
for num in nums:
self.acc_nums.append(self.acc_nums[-1] + num)
def sumRange(self, left: int, right: int) -> int:
return self.acc_nums[right + 1] - self.acc_nums[left]
322. Coin Change
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for c in coins:
if (i - c) >= 0:
dp[i] = min(dp[i], 1 + dp[i - c])
return dp[amount] if (dp[amount] != amount + 1) else -1
338. Counting Bits
class Solution:
def countBits(self, n: int) -> List[int]:
ans = []
for i in range(n+1):
temp = bin(i)
ans.append(str(temp)[2:].count('1'))
return ans
347. Top K Frequent Elements
def topKFrequent(nums: List[int], k:int) -> List[int]:
"""
d = DefaultDict(int)
for item in nums:
d[item] += 1
l = list(sorted(d.items(), key = lambda x: x[1],reverse=True))
return [x[0] for x in l[:k]]
"""
# O(nlogn), dominated by the sorting
# O(n)
################################### ###################################
# O(n) solution via bucket sort:
# 1. count frequencies O(n)
frequencies = DefaultDict(int) # lookup failures will be populated with a default int of 0
for item in nums:
frequencies[item] += 1
n = len(nums)
# 2. create buckets (index = frequency) O(n)
buckets = [[] for _ in range(n+1)]
for num, frequency in frequencies.items():
buckets[frequency].append(num)
# 3. collect k most frequent items O(n)
result = []
while n > -1 and k > 0:
if buckets[n]:
result.append(buckets[n].pop())
k -= 1
else:
n -= 1
return result
392. Is Subsequence
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
"""reasonably good, but not duplicate resistant code
matched = 0
str_idx = -1
for s_char in s:
for curr_idx, t_char in enumerate(t):
if s_char == t_char:
if curr_idx > str_idx:
str_idx = curr_idx
matched += 1
else:
return False
if matched == len(s):
return True
return False
"""
matched = 0
match_idx = 0
for s_char in s:
for curr_idx, t_char in enumerate(t[match_idx:]):
if s_char == t_char:
matched += 1
match_idx += curr_idx + 1
break
if matched == len(s):
return True
return False
424. Longest Repeating Character Replacement
from collections import defaultdict
def maxRep(s: str, k: int) -> int:
count = defaultdict(int)
max_count = 0
left = right = 0
while right < len(s):
count[s[right]] += 1
max_count = max(max_count, count[s[right]])
right += 1
if right - left - max_count > k:
count[s[left]] -= 1
left += 1
return right - left
438. Find All Anagrams in a String
import itertools
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
"""
positions = set()
perms = [''.join(q) for q in itertools.permutations(p)]
for perm in perms:
for i in range(len(s)):
index = s.find(perm, i)
if index == -1:
continue
if index not in positions:
positions.add(index)
i = index + 1
return list(positions)
"""
if len(p) > len(s): return []
pCount, sCount = {}, {}
for i in range(len(p)):
pCount[p[i]] = 1 + pCount.get(p[i],0)
sCount[s[i]] = 1 + sCount.get(s[i],0)
res = [0] if sCount == pCount else []
l = 0
for r in range(len(p), len(s)):
sCount[s[r]] = 1 + sCount.get(s[r],0)
sCount[s[l]] -= 1
if sCount[s[l]] == 0:
sCount.pop(s[l])
l+=1
if sCount == pCount:
res.append(l)
return res
448. Find All Numbers Disappeared in an Array
class Solution:
def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
missing = []
"""
hashmap = {}
for num in nums:
hashmap[num] = 1
for i in range(1, len(nums)+1):
if i not in hashmap:
missing.append(i)
return missing
"""
uniques = set(nums)
for i in range(1,len(nums)+1):
if i not in uniques:
missing.append(i)
return missing
450. Delete Node in a BST
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root:
return None
if key < root.val:
root.left = self.deleteNode(root.left, key)
elif key > root.val:
root.right = self.deleteNode(root.right, key)
else:
if not root.left:
return root.right
if not root.right:
return root.left
successor = root.right
while successor.left:
successor = successor.left
root.val = successor.val
root.right = self.deleteNode(root.right, successor.val)
return root
530. Minimum Absolute Difference in BST
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
min_diff = float('inf')
prev_val = float('-inf')
stack = []
while root or stack:
if root:
stack.append(root)
root = root.left
else:
root = stack.pop()
min_diff = min(min_diff, root.val - prev_val)
prev_val = root.val
root = root.right
return min_diff
543. Diameter of Binary Tree
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
def depth(root):
if not root:
return 0
left_depth = depth(root.left)
right_depth = depth(root.right)
self.diameter = max(self.diameter, left_depth + right_depth)
return 1 + max(left_depth, right_depth)
depth(root)
return self.diameter
567. Permutation in String
import itertools
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
"""
if len(s1) == len(s2) and set(s1) != set(s2): return False
perms = [''.join(q) for q in itertools.permutations(s1)]
res = False
for perm in perms:
print(perm)
index = s2.find(perm, 0)
if index != -1:
res = True
return res
"""
n1 = len(s1)
n2 = len(s2)
if n1 > n2:
return False
s1_counts = [0] * 26
s2_counts = [0] * 26
for i in range(n1):
s1_counts[ord(s1[i])-ord('a')] += 1
s2_counts[ord(s2[i])-ord('a')] += 1
if s1_counts == s2_counts:
return True
for i in range(n1, n2):
s2_counts[ord(s2[i]) - ord('a')] += 1
s2_counts[ord(s2[i - n1]) - ord('a')] -= 1
if s1_counts == s2_counts:
return True
return False
621. Task Scheduler
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
task_counts = Counter(tasks)
max_heap = []
for count in task_counts.values():
max_heap.append(-count)
heapq.heapify(max_heap)
time = 0
wait_queue = deque()
while max_heap or wait_queue:
time += 1
if max_heap:
current_task = heapq.heappop(max_heap)
current_task += 1
if current_task != 0:
wait_queue.append((current_task, time + n))
if wait_queue and wait_queue[0][1] == time:
heapq.heappush(max_heap, wait_queue.popleft()[0])
return time
637. Average of Levels in Binary Tree
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
queue = deque([root])
result = []
while queue:
level = []
for i in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(sum(level) / len(level))
return result
647. Palindromic Substrings
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0
for i in range(len(s)):
res += self.countPali(s, i, i)
res += self.countPali(s, i, i+1)
return res
def countPali(self, s, l, r):
res = 0
while l >= 0 and r < len(s) and s[l] == s[r]:
res += 1
l -= 1
r += 1
return res
653. Two Sum IV - Input is a BST
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
queue = deque([root])
num_set = set()
while queue:
node = queue.popleft()
if (k - node.val) in num_set:
return True
else:
num_set.add(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return False
700. Search in a Binary Search Tree
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
while root:
if root.val == val:
return root
elif root.val < val:
root = root.right
else:
root = root.left
return None
701. Insert into a Binary Search Tree
class Solution:
def insertIntoBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
new_node = TreeNode(val)
if not root:
return new_node
current = root
while True:
if val < current.val:
if current.left:
current = current.left
else:
current.left = new_node
break
else:
if current.right:
current = current.right
else:
current.right = new_node
break
return root
784. Letter Case Permutation
class Solution:
def letterCasePermutation(self, s: str) -> List[str]:
output = [""]
for c in s:
tmp = []
if c.isalpha():
for o in output:
tmp.append(o + c.lower())
tmp.append(o + c.upper())
else:
for o in output:
tmp.append(o + c)
output = tmp
return output
787. Cheapest Flights Within K Stops
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
prices = [float('inf')] * n
prices[src] = 0
for i in range(k + 1):
tmpPrices = prices.copy()
for from_node, to_node, cost in flights:
if prices[from_node] == float('inf'):
continue
if prices[from_node] + cost < tmpPrices[to_node]:
tmpPrices[to_node] = prices[from_node] + cost
prices = tmpPrices
return -1 if prices[dst] == float('inf') else prices[dst]
845. Longest Mountain in Array
class Solution:
def longestMountain(self, arr: List[int]) -> int:
max_length = 0
for i in range(1, len(arr) - 1):
if arr[i-1] < arr[i] > arr[i+1]:
l = r = i
while l > 0 and arr[l] > arr[l-1]:
l -= 1
while r < len(arr) - 1 and arr[r] > arr[r+1]:
r += 1
max_length = max(max_length, r - l + 1)
return max_length
876. Middle of the Linked List
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
N = 0
counter = 0
curr = head
while curr:
N += 1
curr = curr.next
curr = head
stopAt = floor(N / 2)
while counter < stopAt:
curr = curr.next
counter += 1
return curr
973. K Closest Points to Origin
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
heap = []
for (x, y) in points:
dist = -(x * x + y * y)
if len(heap) == k:
heapq.heappushpop(heap, (dist, x, y))
else:
heapq.heappush(heap, (dist, x, y))
return [(x, y) for (dist, x, y) in heap]
977. Squares of a Sorted Array
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
answer = collections.deque()
l, r = 0, len(nums) - 1
while l <= r:
left, right = abs(nums[l]), abs(nums[r])
if left > right:
answer.appendleft(left * left)
l += 1
else:
answer.appendleft(right * right)
r -= 1
return list(answer)
1200. Minimum Absolute Difference
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
mins = []
arr.sort()
l, r = 0, 1
dif = max(arr) - min(arr)
while r < len(arr):
a, b = arr[l], arr[r]
cur_dif = b - a
if cur_dif < dif:
mins = []
mins.append([a, b])
elif cur_dif == dif:
mins.append([a, b])
dif = min(dif, cur_dif)
r += 1
l += 1
return mins
1266. Minimum Time Visiting All Points
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
res = 0
x1, y1 = points.pop()
while points:
x2, y2 = points.pop()
x_dist = abs(x1 - x2)
y_dist = abs(y1 - y2)
res += max(x_dist, y_dist)
x1, y1 = x2, y2
return res
1365. How Many Numbers Are Smaller Than the Current Number
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
"""
counts = []
for a in nums:
count = 0
for b in nums:
if a != b and b < a:
count += 1
counts.append(count)
return counts
"""
mynums = sorted(nums)
iteration = -1
hashMap = {}
for item in mynums:
iteration += 1
if item in hashMap:
continue
hashMap[item] = iteration
return [hashMap[item] for item in nums]
1366. Rank Teams by Voters
:CUSTOM_ID: p1365
class Solution:
def rankTeams(self, votes: List[str]) -> str:
n = len(votes[0])
score = {team: [0] * n for team in votes[0]}
for vote in votes:
for i, team in enumerate(vote):
score[team][i] -= 1
return "".join(sorted(votes[0], key=lambda x: (score[x], x)))
1382. Balance a Binary Search Tree
class Solution:
def balanceBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
nodes = self.inorder(root)
return self.build(nodes, 0, len(nodes) - 1)
def inorder(self, root):
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.val)
current = current.right
return result
def build(self, nums, left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = self.build(nums, left, mid - 1)
node.right = self.build(nums, mid + 1, right)
return node
2034. Stock Price Fluctuation
:CUSTOM_ID: p2034
class StockPrice:
def __init__(self):
self.timestamps = {}
self.max_time = 0
self.min_heap = []
self.max_heap = []
def update(self, timestamp: int, price: int) -> None:
self.timestamps[timestamp] = price
self.max_time = max(self.max_time, timestamp)
heapq.heappush(self.min_heap, (price, timestamp))
heapq.heappush(self.max_heap, (-price, timestamp))
def current(self) -> int:
return self.timestamps[self.max_time]
def maximum(self) -> int:
cur_price, timestamp = heapq.heappop(self.max_heap)
while -cur_price != self.timestamps[timestamp]:
cur_price, timestamp = heapq.heappop(self.max_heap)
heapq.heappush(self.max_heap, (cur_price, timestamp))
return -cur_price
def minimum(self) -> int:
cur_price, timestamp = heapq.heappop(self.min_heap)
while cur_price != self.timestamps[timestamp]:
cur_price, timestamp = heapq.heappop(self.min_heap)
heapq.heappush(self.min_heap, (cur_price, timestamp))
return cur_price
# Time
# Update: pushing onto a heap is log(k), where k is the number of items we have in the heap
# Current: O(1)
# Maximum: rejig the heap takes log(k), and we might need to do this n times, hence: O(nlogk)
# Minimum: rejig the heap takes log(k), and we might need to do this n times, hence: O(nlogk)
# Space: O(n)
2073. Time Needed to Buy Tickets
class Solution:
def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
result = 0
for i in range(len(tickets)):
if i <= k:
result += min(tickets[i], tickets[k])
else:
result += min(tickets[i], tickets[k] - 1)
return result
2933. High-Access Employee
:CUSTOM_ID: p2933
class Solution:
def findHighAccessEmployees(self, access_times: List[List[str]]) -> List[str]:
n = len(access_times)
names = set(access_times[i][0] for i in range(n))
employees = defaultdict(list)
for i, access in enumerate(access_times):
employee, time = access[0], access[1]
employees[employee].append(time)
for k, v in employees.items():
new_v = [0] * len(v)
for i, hhmm in enumerate(v):
minutes = 60 * int(hhmm[:2]) + int(hhmm[2::])
new_v[i] = minutes
print(new_v)
employees[k] = sorted(new_v)
return [
name
for name, times in employees.items()
if any(times[i+2] - times[i] < 60 for i in range(len(times) - 2))
]
3026. Maximum Good Subarray Sum
:CUSTOM_ID: p3026
class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
"""bruteforce:
n = len(nums)
list_of_lists = []
curr_max = float("-inf")
for i in range(n):
for j in range(n):
if i < j:
list_of_lists.append(nums[i:j+1])
#print(nums[i:j], i, j)
print(list_of_lists)
for subarray in list_of_lists:
print(f"subarray: {subarray}")
if abs(subarray[0] - subarray[-1]) == k:
print(f"good array: {subarray}")
curr_max = max(curr_max, sum(subarray))
return 0 if curr_max == float("-inf") else curr_max
"""
prefix = 0
best = float("-inf")
seen = {}
for x in nums:
if x - k in seen:
best = max(best, prefix + x - seen[x-k])
if x + k in seen:
best = max(best, prefix + x - seen[x+k])
if x not in seen:
seen[x] = prefix
else:
seen[x] = min(seen[x], prefix)
prefix += x
return 0 if best == float("-inf") else best
Backlinks (3)
1. Classical Algorithms /wiki/ccs/dsa/classical/
Try to not to use Machine Learning —Rule #1 in Google’s Machine Learning Handbook
“We all die. The goal isn’t to live forever, the goal is to create something that will.” — Chuck Palahniuk
Originally the AI suffix stood for archived intellect, however these days it has concretised to becoming an Augmenting Infrastructure — a place from which to branch out in many directions.
Within this site you will find self-contained material in the form of project posts and blog posts, but also external links 1 to other work – my own as well as not.