Python
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
This front matter follows the pattern of other files in the blog directory, includes math support for the calculations, and reflects the content about birthday prize money analysis with mathematical calculations.
| Years | Prize | Recipient |
|---|---|---|
| 21 | 50,20 | Aarav, Jisu |
| 22 | 50,100 | Erick, Sarro |
| 23 | 100,150 | Unclaimed, Aarav |
| 24 | 300 | Unclaimed |
rule: take the most expensive offering and then double it: 21: 50,20 | 50 22: 50, 100 | 100 23: 100, 150 |