Leetcode Stoney Tute
setting the stage
- Mental Focus
- Learn a programming language
- Learn Data structures and algorithms
- Complete Leetcode / programming practice
- Software Engineering Concepts
- Behavioural Practice
- Best Methods of Applying
- Interview Process & Internal Guidelines.
process for problem solving
-
always read the problem statement twice.
- ask clarifying questions
- try think of different ways to solve the problem
- think end-to-end of the best solutions based on complexity
- write the algorithm from patterns in drawing
- code it out
- try and improve it once you think you're finished.
- go through other solutions (even if you answered correctly)
problems
arrays
217. duplicate values | easy
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
return len(set(nums)) != len(nums)268. missing number | easy
Array nums, containing n distinct numbers from [0,n], return the only number in the range missing from the array.
input [3,0,1]
output 2
note that there is room for arbitrage here. the instinctive solution is a nested for loop $O(n^2)$, but using a sum() call, we can complete this in $O(n)$.
the trick is to realise the structure of the problem only asking for the single missing number.
nums = [3,1,0]
return sum(range(len(nums)+1)) - sum(nums)2
profiling: 0ms runtime, 18.5MB
but I think a hashmap solution might be equally possible too.
from collections import defaultdict
hashmap = defaultdict(int)
nums = [3,1,0]
for item in nums:
hashmap[item] += 1
for i in range(len(nums) + 1):
if i not in hashmap:
return i2
profiling: 11ms runtime, 18.8MB
448. find all numbers disappeared in an array | easy
seems like a continuation of the previous question
nums = [4,3,2,7,8,2,3,1]
missing = []
uniques = set(nums)
for i in range(1,len(nums)+1):
if i not in uniques:
missing.append(i)
missing| 5 | 6 |
profiling: 27ms runtime, 31.2MB space.
from collections import defaultdict
missing = []
hashmap = defaultdict(int)
for item in nums:
hashmap[item] += 1
for i in range(1,len(nums) + 1):
if i not in hashmap:
missing.append(i)
missing| 5 | 6 |
profiling: 53ms, 31.5MB
a constant space solution:
for i in range(len(nums)):
temp = abs(nums[i]) - 1
if nums[temp] > 0:
nums[temp] *= -1
res = []
for i, n in enumerate(nums):
if n > 0:
res.append(i+1)
return res1. two sum | easy
from collections import defaultdict
def myfunc(nums, target):
hashmap = defaultdict(int)
for item in nums:
if target - item in hashmap:
return (item, target - item)
hashmap[item] += 1
myfunc([2,7,11,15], 9)| 7 | 2 |
1365. how many numbers are smaller than the current number | easy
def myfunc():
nums = [8,1,2,2,3]
counts = []
for a in nums:
count = 0
for b in nums:
if a != b and b<a:
count += 1
counts.append(count)
return counts
myfunc()| 4 | 0 | 1 | 1 | 3 |
this problem took a reasonable amount of time to solve, but I did manage to do it with a runtime of 1ms eventually.
the above solution I could produce within 5 minutes: $O(n^2)$; 111ms runtime with 17.7MB space.
eventually I eeked out this:
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]1266. Minimum Time Visiting All Points | easy
I gave myself a 10 minute hard cap on this problem and managed to come up with the following solution:
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
N = len(points)
total = 0
for i in range(N-1):
a = points[i]
b = points[i+1]
x_dist = abs(a[0] - b[0])
y_dist = abs(a[1] - b[1])
total += (x_dist % 2)
total += (y_dist % 2)
total += (y_dist // 2)
total += (x_dist // 2)
return totalbut then I failed the second test which made me refactor the logic slightly into
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
N = len(points)
total = 0
for i in range(N-1):
a = points[i]
b = points[i+1]
x_dist = abs(a[0] - b[0])
y_dist = abs(a[1] - b[1])
if x_dist == 0 or y_dist == 0:
total += x_dist + y_dist
else:
total += (x_dist % 2)
total += (y_dist % 2)
total += (y_dist // 2)
total += (x_dist // 2)
return totalbut even this logic was wrong.
it turns out that the correct approach is to realise the minumum number of moves is thresholded by the maximum difference along the axis:
max(x_dist, y_dist)
whilst we could just replace my modulo logic with this:
for i in range(N-1):
a = points[i]
b = points[i+1]
x_dist = abs(a[0] - b[0])
y_dist = abs(a[1] - b[1])
total += max(x_dist, y_dist)
return totalbut cleverly, we can also use a for loop to the same effect:
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
res = 0
x1, y1 = points.pop() # tuple unpacking
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
profiling: the above solution was 1ms, compared to the for loop version which was 0ms.
54. Spiral Matrix | medium
to begin, I gave myself 25 minutes to at least solve the first couple of cases
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
M = len(matrix)
first_row = matrix[0]
last_row = matrix[M-1]
N = len(first_row)
output = []
layer = 1
for item in first_row:
output.append(item)
# first right layer
for i in range(1,M):
output.append(matrix[i][N-1])
# bottom layer
for i in reversed(last_row):
if i == output[-1]:
continue
output.append(i)
curr_row = matrix[M-1-layer]
for i in range(len(curr_row)):
if i <= N - 1 - layer:
output.append(curr_row[i])
return output
after this, I looked at a solution and noticed that they popped off the first row.
I think my own approach with layer subtraction might also work.
after a couple more hours I have produced this:
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m = len(matrix)
first_row = matrix[0]
last_row = matrix[m-1]
n = len(first_row)
output = []
while len(output) != m*n:
print(output)
#print(matrix)
M = len(matrix)
first_row = matrix[0]
last_row = matrix[M-1]
N = len(first_row)
# top layer
for i in range(N):
output.append(first_row[i])
print("top done")
print(output)
# right layer
for row in matrix[1:]:
output.append(row[-1])
print("right done")
print(output)
# bottom layer
for i in reversed(last_row[:-1]):
if last_row != first_row:
output.append(i)
print("bottom done")
print(output)
# left side
for row in reversed(matrix[1:-1]):
if M != 1 and N != 1:
output.append(row[0])
print("left done")
print(output)
matrix = [i[1:-1] for i in matrix[1:-1]]
print("matrix: ", matrix)
return outputwhich removes the layer logic and strips down the matrix after each layer into a smaller matrix.
this way the top, right, bottom and left logical layers are very easy to implement.
notably I learned about slicing during this question.
def spiralOrder(matrix):
ret = []
while matrix:
# 1. add first row / list of matrix
ret += (matrix.pop(0))
# 2. append last element of all lists in order
if matrix and matrix[0]:
for row in matrix:
ret.append(row.pop())
# 3. add reverse of last row / list
if matrix:
ret+=(matrix.pop()[::-1])
# 4. append first element of all rows / lists in reverse
if matrix and matrix[0]:
for row in matrix[::-1]:
ret.append(row.pop(0))
return rettime complexity: $O(mn)$
200. Number of Islands | medium
def NumIslands(grid):
if not grid:
return 0
def bfs(r, c):
q = deque()
visit.add((r,c))
q.append((r,c))
while q:
row, col = q.popleft()
directions = [[1,0],[-1,0],[0,1],[0,-1]]
for dr, dc in directions:
r,c = row+dr, col+dc
if (r in range(rows) and c in range(cols) and grid[r][c]=='1' and (r,c) not in visit):
q.append((r,c))
visit.add((r,c))
count = 0
rows = len(grid)
cols = len(grid[0])
visit = set()
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r,c) not in visit:
bfs(r,c)
count += 1
return count def countIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
islands = 0
def bfs(r,c):
q = collections.deque()
visit.add((r,c))
q.append((r,c))
while q:
row, col = q.popleft()
directions = [[1,0],[-1,0],[0,1],[0,-1]]
for dr, dc in directions:
r, c = row + dr, col + dc
if (r in range(rows) and
c in range(cols) and
grid[r][c] == '1' and
(r, c) not in visited:
q.append((r, c))
visited.add((r,c))
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1' and (r,c) not in visited:
bfs(r,c)
islands += 1
return islandsmy leetcode submission:
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))
# manipulate the visited set
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 countarrays - two pointers
121. Best time to buy and sell stock | easy
class Solution:
def maxProfit(self, prices: List[int]) -> int:
total_max = 0
N = len(prices)
for i in range(N):
loop_max = 0
for j in range(N):
if i < j:
if prices[j] - prices[i] > loop_max:
loop_max = prices[j] - prices[i]
if loop_max > total_max:
print(i,j)
total_max = loop_max
return total_maxmanaged to pass 198/212 test cases with this O(n^2) bruteforce solution.
I gave myself 10 minutes to solve this (on account of it being an easy problem). but I couldn't figure out how to leverage the two pointers.
should we sort the array? but then we lose dates..
def maxProfit(prices):
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
I also understood from previous pointer questions and the one above, that we can condense some of my if/else logic into leveraging the max function
class Solution:
def maxProfit(self, prices: List[int]) -> int:
total_max = 0
N = len(prices)
for i in range(N):
loop_max = 0
for j in range(N):
if i < j:
loop_max = max(loop_max, prices[j]-prices[i])
total_max = max(loop_max, total_max)
return total_maxunfortunately, I still only pass 198/212 tests with this approach.
977. Squares of a sorted array | easy
Naturally, my solution looked like:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
return sorted([x**2 for x in nums])
but stoney codes provided this cool solution, though it does not work :(; it fails on [-5,-4,-3,-2,-1] producing [25,9,4,1] where it should instead make [1,4,9,25].
def sortedSquares(nums):
if not nums:
return nums
if nums[0] > 0:
return [num**2 for num in nums]
# this is good arbitrage; we know the input array is sorted, and squaring is monotonic
# so the non-decreasing structure will be preserved.
# also, if the first element is positive, then the rest will be too.
# find index first positive
m = 0
for i, n in enumerate(nums):
if n>= 0:
m = i
break
#A = positive nums
#B = reversed negatives
A, B = nums[m:], [-1*n for n in reversed(nums[:m])]
def merge(A,B):
a = b = 0
ret = []
while a < len(A) and b < len(B):
if A[a] < B[b]:
ret.append(A[a])
a+=1
else:
ret.append(B[b])
b+= 1
if a < len(A):
ret.extend(A[a:])
else:
ret.extend(B[b:])
return [n**2 for n in ret]
return merge(A,B)we also fashioned a while solution:
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
answer = collections.deque()
l, r = 0, len(nums) - 1
while l <= r:#O(n)
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)the absolute squared value of a negative and positive number are the same!
15. 3Sum | medium
"medium questions tend to merge concepts from 2 easy questions"
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
"""since the array is sorted, we're better off using two pointers which has a better space complexity
def twoSum(target: int,nums: List[int]) -> List[List[int]]:
hashMap = defaultdict(int)
combos = []
for num in nums:
if target - num not in hashMap:
hashMap[num] += 1
else:
candidate = [num, target -num]
if candidate not in combos:
combos.append(candidate)
return combos
"""
combo3 = []
uniques = set()
nums.sort()
visited = defaultdict(int)
for i in range(len(nums)):
if visited[nums[i]] > 0:
continue
visited[nums[i]] +=1
# we will never make 0
if nums[i] > 0:
break
nums2 = nums[:i] + nums[i+1:]
target = -nums[i]
# recall the array is sorted
l = 0
r = len(nums2) -1
combos = []
while l < r:
sum2 = nums2[l] + nums2[r]
if sum2 > target:
# reduce right pointer
r -= 1
elif sum2 < target:
# accrue larger sum
l += 1
else: #when equal
candidate = [nums2[l], nums2[r]]
#if candidate not in combos:
# i don't think it's possible to find repeats!
r -= 1
l += 1
combos.append(candidate)
twoS = combos
if len(twoS) > 0:
# success
for lst in twoS:
triplet = sorted([nums[i], lst[0], lst[1]])
trip_val = "".join(str(n) for n in sorted([nums[i],lst[0],lst[1]]))
if trip_val not in uniques:
combo3.append(triplet)
uniques.add(trip_val)
return combo3this took me multiple hours to big brain through.
167. 2Sum Part II | medium
this was piss:
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
l = 0
r = len(numbers) - 1
while l <= r:
left = numbers[l]
right = numbers[r]
if left + right > target:
# reduce sum
r -= 1
elif left + right < target:
# increase sum (contigent on increasing sort)
l += 1
else:
return [l+1, r+1]
return [0,0]845. Longest Mountain in Array | medium
damn, their solution was much better than whatever junk was floating around in my brain.
I was thinking of starting from the left and iterating towards the right, but wasn't sure how to reset the counter or deal with the overlapping tectonic plates :(
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 # keep climbing up
max_length = max(max_length, r - l + 1)
return max_lengtharrays - sliding window
219. Contains Duplicate II | easy
gosh it is nice to be back in emacs haha src_emacs-lsip{(+ 2 2)}
length*widthyikes, that was kind of embarassing. I couldn't solve it fast enough.
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
"""
# O(n^2)
N = len(nums)
for i in range(N):
for j in range(i+1, N):
if abs(i - j) <= k and nums[i] == nums[j]:
return True
return False
"""
"""
l, r = 0, 1
if k == 0:
return False
while l < len(nums):
while r < len(nums) and abs(l - r) <= k:
if nums[l] == nums[r]:
return True
r += 1
l += 1
r = l + 1
return False
"""apparently we can solve it using sets and dictionaries. I'll spend another 5 minutes thinking about this:
class Solution:
def containsNearbyDuplicate(self, nums: 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 False35 ms with 30.72MB memory
def containsNearbyDuplicate(self, nums, k):
dic = {}
for i, v in enumerate(nums):
if v in dic and i - dic[v] <= k:
return True
dic[v] = i
return False30ms but with more memory; 36.59MB
1200. Minimum absolute difference | easy
class Solution:
def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
mins = []
arr.sort() # O(n log n)
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[4,2,1,3]
sort: [1,2,3,4] #O(n log n)
[(1,2), (2,3), (3,4)]
209. Minimum Size Subarray Sum | medium
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
l, r = 0, 0
N = len(nums)
minimal_subarray_length = N + 1
while r <= len(nums):
sub_arr = nums[l:r]
if len(sub_arr) >= minimal_subarray_length:
l += 1
r = l
break
sub_sum = sum(sub_arr)
if sub_sum >= target:
minimal_subarray_length = min(minimal_subarray_length, len(sub_arr))
l += 1
r = l
r += 1
print(sub_arr)
return minimal_subarray_length if minimal_subarray_length <= N else 0wrong!
def mindiff(arr, t):
l = 0
total = 0
res = float('inf')
for r in range(len(nums)):
total += nums[r]
while total >= t:
res = min(res, r-l+1)
total -= nums[l]
l+=1
if res == float('inf'):
return 0
else:
return resbit manipulation
136. Single Number | easy
naturally this can be done in $O(n)$ time in a number of ways:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
hashMap = defaultdict(int)
for num in nums:
hashMap[num] += 1
return [key for key, value in hashMap.items() if value == 1][0]still $O(n)$ space complexity.
we can do it with XOR:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
xor = 0
for num in nums:
xor^=num
return xorlowkey bonkers, but it does work. down from 11ms to 3ms.
dynamic programming
322. Coin Change | medium
it is a dynamic programming problem. I do not know how to immediately solve it:
def coinChange(coins, amount):
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 -1time: O(amount * len(coins)) space: O(amount)
70. Climbing Stairs | easy
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]this one was actually quite doable. it is even moreso doable in that the array can be shortened down to just maintaining 2 constants
time: O(n) space: O(n)
53. Maximum Subarray | medium
you should understand the design of this algorithm. especially for an input such as [-2,1,-3,4,-1,2,1,-5,4].
we consider the problem of keeping n if and only if dp[i-1] added to this n is larger than just n. if it is, then it means this previous item is worth keeping, but if not, then we can just take n.
this pattern continues to produce [-2,1,-2,4,3,5,6,1,5] of which whose max is just 6.
def msub(arr):
dp = [0] * len(arr)
for i, n in enumerate(arr):
dp[i] = max(n,dp[i-1]+n)
return max(dp)time: O(n) space: O(n)
but once again there is not much reason why we need to keep the n length array. we can just keep 2 variables:
def maxSubArr(arr):
maxSum = arr[0]
currentSum = 0
for n in arr:
if currentSum = 0:
currentSum = 0
currentSum += n
maxSum = max(maxSum, currentSum)
return maxSum338. Counting Bits | easy
I did this naïvely with a string manipulation:
def countBits(self, n: int) -> List[int]:
ans = []
for i in range(n+1):
temp = bin(i)
ans.append(temp[2:].count('1'))
return answhich ran in 15ms with 18.5MB of memory
there is also this dp solution:
def countBits(self, n: int) -> List[int]:
dp = [0] * (n + 1)
offset = 1
for i in range(1, n+1):
if offset * 2 == i:
offset = i
dp[i] = 1 + dp[i-offset]
return dp^5ms runtime; 18.55MB memory. not bad at all
303. Range Sum Query - Immutable | easy
this question was cute
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
return sum(self.nums[left:right+1])I choked on the initialisation, but beyond that, we can also use prefix-sums to pay a cost once and then have quick summing thereafter:
class NumArray:
def __init__(self, nums: List[int]):
"""
prefix_sum = [0] * (len(nums) + 1)
prefix_sum[0] = 0
for i, num in enumerate(nums):
prefix_sum[i+1] += prefix_sum[i] + num
self.prefix_sum = prefix_sum
"""
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]and then 7ms thereafter.
technically some leetcode solutions mark this as "dp" on account of the sub-problem repetition.
backtracking
at least this way, I can add some notes at the top of the sections!
permutations and combinations both refer to selecting items from some set of data: permutation refers to the ordering or arranging the data in a different type of way combinations is referring to the different selections of data from that dataset.
order of items is important for permutations but not for combinations
784. Letter Case Permutation | medium
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 outputtime: O(2^n) space: O(2^n)
78. Subsets | medium
def subsets(nums):
def backtrack(start, path):
result.append(path[:]) # append copy of path snapshot
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i+1, path)
path.pop()
result = []
backtrack(0,[])
return resultwe use shallow copies in backtracking because they efficiently capture the current state of the path when dealing with simple immutable elements like ints could have used deep copy, but that would make this solution less efficient. deep copies are only necessary when dealing with nested or mutable data
time: O(N*2^n) space: O(N*2^n)
77. Combinations | medium
def combine(n, k):
def backtrack(start, path):
if len(path) == k:
result.append(path[:]) # shallow copy
return
for i in range(start, n+1):
path.append(i)
backtrack(i+1,path)
path.pop()
result = []
backtrack(1, [])
return resulttime: $O(k \cdot {n\choose k})$ space: $O(k)$
46. Permutations | medium
def permute(nums):
def backtrack(start, end):
if start == end:
result.append(nums[:]) # shallow copy
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 result37. Sudoku Solver | Hard
inspired by lazily copying the above (somewhat) boring backtrackings, I decided to apply what I learned to solve Sudokus:
from typing import List
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
N = len(board)
visited = set()
empties = []
def hashBoard():
"""
total = 0
for row in range(N):
for col in range(N):
total += board[row][col]
visited.add(total)
"""
# again, a garbage hash.
hashed_board = "".join("".join(i for i in row) for row in board)
print("hashed board:", hashed_board)
return hashed_board
def fullGroup(group: List[str]) -> bool:
uniques = list(set(group))
if len(uniques) != N:
return False
return True
def checkGroup(group: List[str]) -> bool:
uniques = list(set(group))
counts = {s: group.count(s) for s in uniques}
#del counts['.'] # we don't care about how many empties
counts.pop('.', None)
if any(value > 1 for value in counts.values()):
return False
if any(int(key) > 9 or int(key) < 1 for key in counts.keys()):
return False
return True
def isSolved():
"""
rowSum = 0
for row in board:
if sum(row) != WIN_SUM:
return False
"""
# this is a stupid way to check! you can literally do 9 5's
###########################################################
# check rows:
for row in board:
if not (checkGroup(row) and fullGroup(row)):
return False
# check columns:
for i in range(N):
col = [row[i] for row in board]
if not (checkGroup(col) and fullGroup(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) and fullGroup(subgrid)):
return False
return True
def validMove(board_state: List[List[str]], pos: tuple) -> List[int]:
curr_num = board_state[pos[0]][pos[1]]
valid_moves = []
for i in range(1, N+1): # checking candidates
board_state[pos[0]][pos[1]] = str(i) # set the candidate in board
row = board_state[pos[0]] # save row as var, with new candidate
col = [r[pos[1]] for r in board_state] # set col with candidate
subgrid = []
row_offset = (pos[0] // 3) * 3
col_offset = (pos[1] // 3) * 3
for r in range(row_offset, row_offset + 3):
for c in range(col_offset, col_offset + 3):
subgrid.append(board_state[r][c])
if not checkGroup(row):
board_state[pos[0]][pos[1]] = curr_num # reset the board_state
continue # the i value does not work.
# check col
if not checkGroup(col):
board_state[pos[0]][pos[1]] = curr_num # reset the board_state
continue # the i value does not work.
# check containing subgrid
if not checkGroup(subgrid):
board_state[pos[0]][pos[1]] = curr_num # reset the board_state
continue # the i value does not work.
# position is valid
board_state[pos[0]][pos[1]] = curr_num # reset the board_state
valid_moves.append(str(i))
return valid_moves
def find_empties():
for i, row in enumerate(board):
for j, col in enumerate(row):
if col == '.':
empties.append((i, j))
def dfs():
dfs_rec(board, empties.pop(0))
def dfs_rec(board_state: List[List[str]], pos: tuple):
print(board)
if isSolved():
return True
hashed_board = hashBoard()
if hashed_board in visited:
return False
visited.add(hashed_board)
valid_moves = validMove(board_state, pos) # list of strings
for move in valid_moves:
original = board_state[pos[0]][pos[1]]
board_state[pos[0]][pos[1]] = move
dot = empties.pop(0)
if dfs_rec(board_state, dot):
return True
else:
# undo move
empties.append(dot)
board_state[pos[0]][pos[1]] = original
#return True
find_empties()
while not isSolved():
dfs()
break
if __name__ == "__main__":
S = Solution()
board = [["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]]
print(board)
S.solveSudoku(board)it took me about 4 hours to come up with this, and still the solution is highly unoptimised.
it turns out that my isSolved() calls are very expensive and poor design. also, the empties.pop(0) is a bottle-neck.
so is the checkGroup function.
instead a better solution looks like:
from typing import List
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
N = len(board)
empties = []
# ------------------------------------------------------------------
# (Kept from your code, but no longer used in the main DFS)
# ------------------------------------------------------------------
def fullGroup(group: List[str]) -> bool:
uniques = list(set(group))
if len(uniques) != N:
return False
return True
def checkGroup(group: List[str]) -> bool:
seen = set()
for ch in group:
if ch == '.':
continue
if ch in seen:
return False
seen.add(ch)
return True
def isSolved() -> bool:
# Full-board validator, not used inside DFS now
# check rows:
for row in board:
if not (checkGroup(row) and fullGroup(row)):
return False
# check columns:
for i in range(N):
col = [row[i] for row in board]
if not (checkGroup(col) and fullGroup(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) and fullGroup(subgrid)):
return False
return True
# ------------------------------------------------------------------
# NEW: O(1) constraint tracking with minimal changes to structure
# ------------------------------------------------------------------
rows = [set() for _ in range(N)]
cols = [set() for _ in range(N)]
boxes = [set() for _ in range(N)] # index = (r//3)*3 + c//3
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)
# reuse your validMove name/signature, but now use the row/col/box sets
def validMove(board_state: List[List[str]], pos: tuple) -> List[str]:
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
# ------------------------------------------------------------------
# DFS using index into `empties` (no pop/append, no full-board checks)
# ------------------------------------------------------------------
def dfs_rec(idx: int) -> bool:
if idx == len(empties):
return True # all empties filled legally
r, c = empties[idx]
if board[r][c] != '.':
return dfs_rec(idx + 1)
b = (r // 3) * 3 + (c // 3)
for move in validMove(board, (r, c)):
# place
board[r][c] = move
rows[r].add(move)
cols[c].add(move)
boxes[b].add(move)
if dfs_rec(idx + 1):
return True
# undo
board[r][c] = '.'
rows[r].remove(move)
cols[c].remove(move)
boxes[b].remove(move)
return False
find_empties()
dfs_rec(0)linked lists
876. Middle of a linked list | easy
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
pretty chill, took me a couple minutes to remember how to use linked lists, particularly my only bug was accidentally calling curr.next() as a function which blew up with:
-
Runtime Error
- and therein, TypeError:
'ListNode' object is not callable - which is fair.
- and therein, TypeError:
141. Linked List Cycle | easy
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
I hicked up for a second because I accidentally wrote the True and False returns in the wrong order; the question is about "finding cycles"!
206. Reverse Linked List | easy
for this one I had to consult the video; I was thinking of temporary variables.
it also turns out that I have previously attempted this problem in C:
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;
}and it turns out the solution of the video was also using temporary variables:
prev = None
curr = head
while curr:
next_p = curr.next
curr.next = prev
prev = curr
curr = next_p
return prevwhich looks like this in its entirety:
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None:
return head
new = None
curr = head
while curr:
tmp = curr.next
curr.next = new
new = curr
curr = tmp
return new203. Remove Linked List Elements | easy
this one was a huge bother for me. particularly the cases where head =[7,7,7,7] and I was being plagued with AttributeError=s when trying to access =.next on =None=types
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
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:
if curr.next == val:
curr = curr.next.next
continue
else:
prev.next = curr.next
curr = curr.next
continue
else:
prev = curr
curr = curr.next
return dummy.next92. Remove Linked List II | medium
I continue to struggle with the 'dummy' pointer pattern. here is my original attempt, which tried to make use of code from problem 206 (reverse linked list):
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
# code to reverse an entire list:
curr = head
leftp = head
leftprev = head
rightp = head
while curr.next:
if curr.next.val == left:
leftprev = curr
if curr.val == left:
leftp = curr
if curr.val == right:
rightp = curr
curr = curr.next
prev = rightp.next
print(leftp.val, rightp.val)
curr = leftprev
while curr != rightp:
nextp = curr.next
curr.next = prev
prev = curr
curr = nextp
return headthere were many logical mistakes in this code:
- we treat the positions as values! wrong as hell
- the
curr.nextscan loop will miss the final entry leftprevis finding the value of the leftprevious, not the index – related to the misunderstanding of the question- reversal should start at
leftpnotleftprev - we never reconnect the reversed segment back to the list
- we stop at
curr!=rightp, so the endpointrightpis never reversed / linked properly
more correctly, we should have done:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
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.next234. Palindrome Linked List | easy
this kind of thinking is really a tricky endeavour:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head.next == None:
return True
# find middle node
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
removal = curr.val
print("removal", removal)
print("N", N)
if N%2: # is odd
# remove middle node:
curr = head
dummy = ListNode(-1, head)
prev = dummy
while curr:
if curr.val == removal:
if curr.next == removal:
curr = curr.next.next
continue
else:
prev.next = curr.next
curr = curr.next
continue
else:
prev = curr
curr = curr.next
head = dummy.next
curr = head
hashMap = collections.defaultdict(int)
while curr:
hashMap[curr.val] += 1
curr = curr.next
print(hashMap)
return True if all(value == 2 for value in hashMap.values()) else False
obviously this is very wrong. it fails on [1,3,2,4,3,2,1]. as the hashmap solution does not encode the positions.
in some sense I am checking multiset symmetry, not mirror order. more correctly we should have:
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
arr = []
curr = head
while curr:
arr.append(curr.val)
curr = curr.next
return arr == arr[::-1]21. Merge Two Sorted Lists | easy
obviously, I can't do anything right:
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
headA = list1
headB = list2
currA = headA
currB = headB
# start on the smaller list:
start = None
other = None
if headB.val < headA.val:
start = headB
other = headA
else:
start = headA
other = headB
curr = start
while curr:
if curr.next.val < other.val:
curr = curr.next
else:
curr.next = other
other = curr.next
return startthe correct logic improves on my code by:
- handling empty lists
- checking
curr.nextbefore dereferencing it - advancing
currcorrectly in thewhileloop
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1:
return list2
if not list2:
return list1
# start on the smaller list:
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
stacks [4/4]
155. Min Stack | easy
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)20. Valid Parenthesis | easy
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 stack150. Evaluate Reverse Polish Notation
I've been stuck with this for some time now:
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = [] # the stack should never get too large
for token in tokens:
print("stack:", stack)
if token not in {'+','-','*','/'}:
stack.append(int(token))
else: # we don't really need to check this, but it will guard
op1 = stack.pop(-1)
op2 = stack.pop(-1)
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()
and I think the offender is the stack.pop(-1) line which might have a larger time complexity than stack.pop()
—
nope, it didn't matter. I was just printing to stdout like a dumbass.
bonus q: stack sorting
input = [34,3,31,98,92,23]
stack = []
while input:
num = input.pop()
while stack and (stack[-1] > num):
input.append(stack[-1])
stack.pop()
stack.append(num)
print(stack)[3, 23, 31, 34, 92, 98]
time complexity: $O(n^2)$ space: $O(n)$
queues
SCHEDULED:
binary trees
SCHEDULED:
binary search trees
SCHEDULED:
graphs
SCHEDULED:
Backlinks
1. Leetcode /wiki/ccs/dsa/leetcode/