“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.
Starting position
A foundational statement accepted without proof. All other results are built ontop.
A proved statement that is less central than a theorem, but still of interest.
A “helper” proposition proved to assist in establishing a more important result.
A statement following from a theorem or proposition, requiring little to no extra proof.
A precise specification of an object, concept or notation.
The power the differential is raised to.
The dependent variable and its derivatives are all not non-linear. \[\begin{aligned} \underbrace{\frac{d^2 y}{d t}} &\quad \underbrace{\cos(x) \frac{dy}{dx}} &\quad \underbrace{\frac{dy}{dt} \frac{d^3 y}{dt^3}} &\quad \underbrace{y’ = e^y} &\quad \underbrace{y \frac{dy}{dx}} \\ \text{linear} &\quad \text{linear} &\quad \text{non-linear} &\quad \text{non-linear} &\quad \text{non-linear} \end{aligned}\]
Independent variable does not appear in the equation.
Independent variable does appear in the equation.
This document contains the code to create an RNN chatbot that emulates Kanye West’s speech style.
it is good to keep notes about version controlling things.
I mostly use git.
| prefix | use-case |
|---|---|
| BUG | bug fix |
| DEV | development tool or utility |
| DOC | documentation |
| ENH | enhancement, a new feature |
| MAINT | maintainence task |
| REL | release |
| STY | stylistic change |
| TST | addition or modification of tests |
“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.
Here lie my implementations and notes for various leetcode problems.
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 []
# 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
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
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];
}
}
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
#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
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
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
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
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
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)
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
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
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
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())
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)
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
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
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]
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
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
// 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;
}
}
}
}
*/
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
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
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
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
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)
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
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
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
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
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]
class Solution:
def singleNumber(self, nums: List[int]) -> int:
xor = 0
for num in nums:
xor ^= num
return xor
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
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()
import re
class Solution:
def reverseWords(self, s: str) -> str:
splt = re.split('\\s+',s)
splt.reverse()
return " ".join(splt).strip()
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)
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 []
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
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
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
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
/**
* 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;
}
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
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
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]
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)
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
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
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
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
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]
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
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
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
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
"""
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
class Solution:
def missingNumber(self, nums: List[int]) -> int:
return sum(range(len(nums)+1))-sum(nums)
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]
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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]
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
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
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]
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)
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
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
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]
:CUSTOM_ID: p1365
/author/