In this blog, I will share Amazon-tagged Leetcode questions and my solutions to them. These questions should be a practical guide to understanding what you need to know for an Amazon interview.
Most importantly, we should never memorize the code, but, rather, we should be able to identify patterns that can help us solve all similar problems.
Below are some Amazon-Tagged Leetcode questions for you to familiarize yourself with. Happy coding!😄
• Array & Map
https://leetcode.com/problems/reorder-data-in-log-files/
class Solution:
def reorderLogFiles(self, logs: List[str]) -> List[str]:
letter = []
digit = []
for log in logs:
idf, content = log.split(" ", 1)
if content[0].isdigit():
digit.append(log)
else:
letter.append(log)
letter.sort(key = lambda x: (x.split(" ", 1)[1], x.split(" ", 1)[0]))
return letter + digit
https://leetcode.com/problems/longest-palindrome/
class Solution:
def longestPalindrome(self, s: str) -> int:
lookup = {}
ans = 0
for ele in s:
lookup[ele] = lookup.get(ele, 0) + 1
for k, v in lookup.items():
ans += (v - v % 2)
return ans + 1 if ans < len(s) else ans
https://leetcode.com/problems/distribute-candies/
class Solution:
def distributeCandies(self, candyType: List[int]) -> int:
s = set()
for x in candyType:
s.add(x)
return min(len(s), len(candyType) // 2)
https://leetcode.com/problems/minimum-subsequence-in-non-increasing-order/
class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
ans = []
t = sum(nums)
curSum = 0
nums.sort()
for i in range(len(nums) - 1, -1, -1):
curSum += nums[i]
if curSum > t - curSum:
for j in range(len(nums) - 1, i - 1, -1):
ans.append(nums[j])
return ans
return ans
https://leetcode.com/problems/number-of-equivalent-domino-pairs/
class Solution:
def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
ans = 0
d = {}
for x in dominoes:
if (x[0], x[1]) in d:
ans += d[(x[0], x[1])]
if x[0] != x[1] and (x[1], x[0]) in d:
ans += d[(x[1], x[0])]
d[(x[0], x[1])] = d.get((x[0], x[1]), 0) + 1
return ans
https://leetcode.com/problems/longest-harmonious-subsequence/
class Solution:
def findLHS(self, nums: List[int]) -> int:
d = {}
for num in nums:
d[num] = d.get(num, 0) + 1
maxN = 0
for k in d.keys():
if k + 1 in d:
maxN = max(maxN, d[k] + d[k + 1])
return maxN
https://leetcode.com/problems/count-good-triplets/
class Solution:
def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
ans = 0
n = len(arr)
for i in range(n):
for j in range(i + 1, n):
if abs(arr[i] - arr[j]) > a:
continue
for k in range(j + 1, n):
if abs(arr[j] - arr[k]) > b or abs(arr[i] - arr[k]) > c:
continue
ans += 1
return ans
https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/
class Solution:
def maxProduct(self, nums: List[int]) -> int:
max1 = 0
max2 = 0
for num in nums:
if num >= max1:
max2 = max1
max1 = num
elif num < max1 and num > max2:
max2 = num
return (max1 - 1) * (max2 - 1)
https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/
class Solution:
def sumZero(self, n: int) -> List[int]:
ans = [0] * n
for i in range(n // 2):
ans[i] = i + 1
ans[n - i - 1] = - (i + 1)
return ans
https://leetcode.com/problems/verifying-an-alien-dictionary/
class Solution:
def isAlienSorted(self, words: List[str], order: str) -> bool:
d = {}
for i in range(26):
d[order[i]] = i
l = []
for word in words:
t = list(word)
for i in range(len(t)):
t[i] = d[t[i]]
l.append(t)
for i in range(1, len(l)):
if l[i - 1] > l[i]:
return False
return True
https://leetcode.com/problems/path-crossing/
class Solution:
def isPathCrossing(self, path: str) -> bool:
x = 0
y = 0
vis = {(x, y): 1}
for c in path:
if c == 'N':
x -= 1
elif c == 'S':
x += 1
elif c == 'W':
y -= 1
else:
y += 1
if (x, y) in vis:
return True
else:
vis[(x, y)] = 1
return False
https://leetcode.com/problems/maximum-average-subarray-i/
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
avg = float("-inf")
total = 0
l = 0
for r in range(len(nums)):
total += nums[r]
if (r - l + 1) > k:
total -= nums[l]
l += 1
if (r - l + 1) == k:
avg = max(avg, total / k)
return avg
https://leetcode.com/problems/partition-array-into-three-parts-with-equal-sum/
class Solution:
def canThreePartsEqualSum(self, arr: List[int]) -> bool:
target = sum(arr) // 3
sum1 = 0
for i in range(len(arr)):
sum1 += arr[i]
if sum1 == target:
sum2 = 0
for j in range(len(arr) - 1, i + 1, -1):
sum2 += arr[j]
if sum2 == target:
if sum(arr) - sum1 - sum2 == target:
return True
return False
https://leetcode.com/problems/assign-cookies/
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
ans = 0
i = 0
j = 0
while i < len(g) and j < len(s):
if s[j] >= g[i]:
ans += 1
i += 1
j += 1
else:
j += 1
return ans
https://leetcode.com/problems/sort-array-by-parity-ii/
class Solution:
def sortArrayByParityII(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [0] * n
t = 0
for num in nums:
if num % 2 == 0:
ans[t] = num
t += 2
t = 1
for num in nums:
if num % 2 != 0:
ans[t] = num
t += 2
return ans
https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
ans = 0
for word in words:
d = {}
for c in chars:
d[c] = d.get(c, 0) + 1
t = 0
for w in word:
if w in d and d[w] > 0:
d[w] -= 1
t += 1
else:
t = 0
break
ans += t
return ans
https://leetcode.com/problems/repeated-substring-pattern/
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
l = s[1:] + s[:-1]
return s in l
https://leetcode.com/problems/kth-missing-positive-number/
class Solution:
def findKthPositive(self, arr: List[int], k: int) -> int:
for i in range(len(arr)):
if arr[i] <= k:
k += 1
return k
https://leetcode.com/problems/replace-elements-with-greatest-element-on-right-side/
class Solution:
def replaceElements(self, arr: List[int]) -> List[int]:
maxN = -1
for i in range(len(arr) - 1, -1, -1):
t = maxN
maxN = max(t, arr[i])
arr[i] = t
return arr
https://leetcode.com/problems/valid-mountain-array/
class Solution:
def validMountainArray(self, arr: List[int]) -> bool:
l = 0
r = len(arr) - 1
while l < r and arr[l] < arr[l + 1]:
l += 1
while l < r and arr[r - 1] > arr[r]:
r -= 1
return l == r and l != 0 and l != len(arr) - 1
https://leetcode.com/problems/can-place-flowers/
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
m = len(flowerbed)
for i in range(m):
if n > 0 and flowerbed[i] == 0 and (i - 1 < 0 or flowerbed[i - 1] == 0) and (i + 1 >= m or flowerbed[i + 1] == 0):
flowerbed[i] = 1
n -= 1
return n == 0
https://leetcode.com/problems/array-partition/
class Solution:
def arrayPairSum(self, nums: List[int]) -> int:
ans = 0
arr = sorted(nums)
for i in range(0, len(arr), 2):
ans += arr[i]
return ans
https://leetcode.com/problems/build-array-from-permutation/
class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
n = len(nums)
for i in range(n):
nums[i] += 1000 * (nums[nums[i]] % 1000)
for i in range(n):
nums[i] //= 1000
return nums
https://leetcode.com/problems/pascals-triangle-ii/
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
ans = []
for i in range(rowIndex + 1):
ans.append(1)
for j in range(i - 1, 0, -1):
ans[j] = ans[j] + ans[j - 1]
return ans
https://leetcode.com/problems/find-pivot-index/
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
curSum = 0
total = sum(nums)
for i in range(len(nums)):
if curSum == total - nums[i] - curSum:
return i
curSum += nums[i]
return -1
https://leetcode.com/problems/longest-word-in-dictionary/
class Solution:
def longestWord(self, words: List[str]) -> str:
lookup = set()
ans = ""
words.sort()
for word in words:
if len(word) == 1 or word[:-1] in lookup:
ans = word if len(word) > len(ans) else ans
lookup.add(word)
return ans
https://leetcode.com/problems/summary-ranges/
class Solution:
def summaryRanges(self, nums: List[int]) -> List[str]:
ans = []
t = ""
for i in range(len(nums)):
if i < len(nums) - 1 and nums[i + 1] == nums[i] + 1:
if t == "":
t = str(nums[i]) + "->"
else:
ans.append(t + str(nums[i]))
t = ""
return ans
https://leetcode.com/problems/missing-ranges/
class Solution:
def findMissingRanges(self, nums: List[int], lower: int, upper: int) -> List[str]:
def stringify(a, b):
if a == b:
return str(a)
else:
return str(a) + "->" + str(b)
nums = [lower - 1] + nums + [upper + 1]
ans = []
for i in range(1, len(nums)):
if nums[i] - nums[i - 1] > 1:
ans.append(stringify(nums[i - 1] + 1, nums[i] - 1))
return ans
https://leetcode.com/problems/third-maximum-number/
class Solution:
def thirdMax(self, nums: List[int]) -> int:
Max1, Max2, Max3 = float("-inf"), float("-inf"), float("-inf")
for num in nums:
if num > Max1:
Max3 = Max2
Max2 = Max1
Max1 = num
elif num < Max1 and num > Max2:
Max3 = Max2
Max2 = num
elif num < Max2 and num > Max3:
Max3 = num
return Max3 if Max3 != float("-inf") else Max1
https://leetcode.com/problems/shortest-word-distance/
class Solution:
def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
p1 = -1
p2 = -1
ans = float("inf")
for i in range(len(wordsDict)):
if wordsDict[i] == word1:
p1 = i
elif wordsDict[i] == word2:
p2 = i
if p1 != -1 and p2 != -1:
ans = min(ans, abs(p2 - p1))
return ans
https://leetcode.com/problems/running-sum-of-1d-array/
class Solution:
def runningSum(self, nums: List[int]) -> List[int]:
for i in range(1, len(nums)):
nums[i] += nums[i - 1]
return nums
https://leetcode.com/problems/find-common-characters/
class Solution:
def commonChars(self, words: List[str]) -> List[str]:
lookup = {}
ans = []
for c in words[0]:
lookup[c] = lookup.get(c, 0) + 1
for k in lookup:
for word in words[1:]:
if k not in word:
lookup[k] = 0
else:
lookup[k] = min(word.count(k), lookup[k])
for k, v in lookup.items():
if v > 0:
for i in range(v):
ans.append(k)
return ans
https://leetcode.com/problems/squares-of-a-sorted-array/
class Solution:
def sortedSquares(self, nums: List[int]) -> List[int]:
p = len(nums) - 1
ans = [0] * len(nums)
for i in range(len(nums)):
if nums[i] >= 0:
p = i
break
i = p - 1
j = p
k = 0
while i >= 0 and j < len(nums):
if nums[i] * nums[i] <= nums[j] * nums[j]:
ans[k] = nums[i] * nums[i]
i -= 1
else:
ans[k] = nums[j] * nums[j]
j += 1
k += 1
while i >= 0:
ans[k] = nums[i] * nums[i]
i -= 1
k += 1
while j < len(nums):
ans[k] = nums[j] * nums[j]
j += 1
k += 1
return ans
https://leetcode.com/problems/meeting-rooms/
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
if len(intervals) <= 1:
return True
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i - 1][1]:
return False
return True
https://leetcode.com/problems/isomorphic-strings/
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
lookup = {}
tSet = set()
for i in range(len(s)):
if (s[i] in lookup and lookup[s[i]] != t[i]) or (s[i] not in lookup and t[i] in tSet):
return False
lookup[s[i]] = t[i]
tSet.add(t[i])
return True
https://leetcode.com/problems/valid-anagram/
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
tracker = defaultdict(int)
for c in s:
tracker[c] += 1
for c in t:
tracker[c] -= 1
for x in tracker.values():
if x != 0:
return False
return True
https://leetcode.com/problems/merge-sorted-array/
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
k = m + n - 1
while m > 0 and n > 0:
if nums1[m - 1] >= nums2[n - 1]:
nums1[k] = nums1[m - 1]
m -= 1
else:
nums1[k] = nums2[n - 1]
n -= 1
k -= 1
if n > 0:
nums1[: n] = nums2[: n]
https://leetcode.com/problems/longest-common-prefix/
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
def helper(str1, str2):
i = 0
j = 0
res = ""
while i < len(str1) and j < len(str2):
if str1[i] != str2[j]:
break
else:
res += str1[i]
i += 1
j += 1
return res
prefix = strs[0]
for i in range(1, len(strs)):
prefix = helper(prefix, strs[i])
return prefix
https://leetcode.com/problems/maximum-units-on-a-truck/
class Solution:
def maximumUnits(self, boxTypes: List[List[int]], truckSize: int) -> int:
boxTypes.sort(key = lambda x: x[1], reverse = True)
ans = 0
for x in boxTypes:
if truckSize > 0 and truckSize > x[0]:
truckSize -= x[0]
ans += x[0] * x[1]
elif truckSize > 0 and truckSize <= x[0]:
ans += truckSize * x[1]
return ans
return ans
https://leetcode.com/problems/pascals-triangle/
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [[1]]
for i in range(1, numRows):
t = []
t.append(1)
for j in range(1, i):
t.append(ans[i - 1][j - 1] + ans[i - 1][j])
t.append(1)
ans.append(t)
return ans
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
buy = prices[0]
for price in prices:
buy = min(buy, price)
profit = max(profit, price - buy)
return profit
https://leetcode.com/problems/roman-to-integer/
class Solution:
def romanToInt(self, s: str) -> int:
lookup = {
"I": 1,
"V": 5,
"X": 10,
"L": 50,
"C": 100,
"D": 500,
"M": 1000
}
ans = 0
n = len(s)
maxN = 0
for i in range(n - 1, -1, -1):
if lookup[s[i]] >= maxN:
ans += lookup[s[i]]
maxN = lookup[s[i]]
else:
ans -= lookup[s[i]]
return ans
https://leetcode.com/problems/maximum-subarray/
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
curSum = 0
ans = float("-inf")
for num in nums:
if curSum < 0:
curSum = num
else:
curSum += num
ans = max(ans, curSum)
return ans
https://leetcode.com/problems/remove-duplicates-from-sorted-array/
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
l = 1
for r in range(1, len(nums)):
if nums[r] != nums[l - 1]:
nums[l] = nums[r]
l += 1
return l
https://leetcode.com/problems/count-binary-substrings/
class Solution:
def countBinarySubstrings(self, s: str) -> int:
last = 0
cnt = 1
ans = 0
for i in range(1, len(s)):
if s[i] == s[i - 1]:
cnt += 1
else:
last = cnt
cnt = 1
if last >= cnt:
ans += 1
return ans
• Binary Search
https://leetcode.com/problems/sqrtx/
class Solution:
def mySqrt(self, x: int) -> int:
ans = 0
l = 1
r = x
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
ans = mid
l = mid + 1
else:
r = mid - 1
return ans
https://leetcode.com/problems/find-smallest-letter-greater-than-target/
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
l = 0
r = len(letters)
while l < r:
mid = (l + r)//2
if letters[mid] <= target:
l = mid + 1
else:
r = mid
return letters[0 if l == len(letters) else l]
https://leetcode.com/problems/arranging-coins/
class Solution:
def arrangeCoins(self, n: int) -> int:
l = 0
r = n
while l <= r:
mid = (l + r) // 2
if mid * (mid + 1) / 2 == n:
return mid
if mid * (mid + 1) / 2 > n:
r = mid - 1
else:
l = mid + 1
return 1 if l == 1 else l - 1
https://leetcode.com/problems/valid-perfect-square/
class Solution:
def isPerfectSquare(self, num: int) -> bool:
l = 1
r = num
while l < r:
mid = (l + r) // 2
if mid * mid <= num:
l = mid + 1
else:
r = mid
return True if l == 1 else (l - 1) * (l - 1) == num
https://leetcode.com/problems/search-insert-position/
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return l
https://leetcode.com/problems/peak-index-in-a-mountain-array/
class Solution:
def peakIndexInMountainArray(self, arr: List[int]) -> int:
l = 0
r = len(arr) - 1
while l < r:
mid = (l + r) // 2
if arr[mid] > arr[mid + 1]:
r = mid
else:
l = mid + 1
return l
https://leetcode.com/problems/binary-search/
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
while l < r:
mid = (l + r) // 2
if nums[mid] >= target:
r = mid
else:
l = mid + 1
return -1 if l == len(nums) or nums[l] != target else l
• Two Pointers
https://leetcode.com/problems/valid-palindrome-ii/
class Solution:
def validPalindrome(self, s: str) -> bool:
def helper(s, i, j):
while i < j:
if s[i] != s[j]:
return False
i += 1
j -= 1
return True
i = 0
j = len(s) - 1
while i < j:
if s[i] != s[j]:
return helper(s, i + 1, j) or helper(s, i, j - 1)
i += 1
j -= 1
return True
https://leetcode.com/problems/long-pressed-name/
class Solution:
def isLongPressedName(self, name: str, typed: str) -> bool:
i = 0
j = 0
n = len(name)
m = len(typed)
prei = 0
prej = 0
while i < n and j < m:
if name[prei] != typed[prej]:
return False
while i < n and name[i] == name[prei]:
i += 1
while j < m and typed[j] == typed[prej]:
j += 1
if j - prej < i - prei:
return False
prei = i
prej = j
return i == n and j == m
https://leetcode.com/problems/di-string-match/
class Solution:
def diStringMatch(self, s: str) -> List[int]:
n = len(s)
l = 0
r = n
ans = [0] * (n + 1)
for i in range(n):
if s[i] == 'I':
ans[i] = l
l += 1
else:
ans[i] = r
r -= 1
ans[n] = l
return ans
https://leetcode.com/problems/duplicate-zeros/
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
n = len(arr)
l = 0
r = 0
while l < n and r < n:
arr[l] += 10 * (arr[r] % 10)
if arr[r] % 10 == 0:
l += 1
l += 1
r += 1
for i in range(n):
arr[i] //= 10
return arr
https://leetcode.com/problems/remove-element/
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
l = 0
for r in range(0, len(nums)):
if nums[r] != val:
nums[l] = nums[r]
l += 1
return l
https://leetcode.com/problems/sort-array-by-parity/
class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
l = 0
for r in range(len(nums)):
if nums[r] % 2 == 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
return nums
https://leetcode.com/problems/two-sum-less-than-k/
class Solution:
def twoSumLessThanK(self, nums: List[int], k: int) -> int:
nums.sort()
answer = -1
l = 0
r = len(nums)-1
while l < r:
sumNums = nums[l] + nums[r]
if sumNums < k:
answer = max(answer, sumNums)
l += 1
else:
r -= 1
return answer
https://leetcode.com/problems/move-zeroes/
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
l = 0
for r in range(len(nums)):
if nums[r] != 0:
nums[l], nums[r] = nums[r], nums[l]
l += 1
• String
https://leetcode.com/problems/robot-return-to-origin/
class Solution:
def judgeCircle(self, moves: str) -> bool:
R = 0
L = 0
U = 0
D = 0
for m in moves:
if m == "R":
R += 1
if m == "L":
L += 1
if m == "U":
U += 1
if m == "D":
D += 1
return R == L and U == D
https://leetcode.com/problems/increasing-decreasing-string/
class Solution:
def sortString(self, s: str) -> str:
arr = [0] * 26
ans = ''
for c in s:
arr[ord(c) - 97] += 1
while len(ans) < len(s):
for i in range(0, 26):
if arr[i] > 0:
ans += chr(i + 97)
arr[i] -= 1
for i in range(25, -1, -1):
if arr[i] > 0:
ans += chr(i + 97)
arr[i] -= 1
return ans
https://leetcode.com/problems/to-lower-case/
class Solution:
def toLowerCase(self, s: str) -> str:
ans = ""
for c in s:
if c >= 'A' and c <= 'Z':
ans += chr(ord(c) - ord('A') + ord('a'))
else:
ans += c
return ans
• Sliding Window
https://leetcode.com/problems/contains-duplicate-ii/
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
seen = set()
for i in range(len(nums)):
if i - k - 1 >= 0:
seen.remove(nums[i - k - 1])
if nums[i] in seen:
return True
seen.add(nums[i])
return False
https://leetcode.com/problems/diet-plan-performance/
class Solution:
def dietPlanPerformance(self, calories: List[int], k: int, lower: int, upper: int) -> int:
points = 0
running_calories = 0
for i in range(len(calories)):
running_calories += calories[i]
if i >= k - 1:
if running_calories < lower:
points -= 1
elif running_calories > upper:
points += 1
running_calories -= calories[i - k + 1]
return points
• Math
https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/
class Solution:
def hasGroupsSizeX(self, deck: List[int]) -> bool:
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
d = {}
pre = -1
for x in deck:
d[x] = d.get(x, 0) + 1
for k in d:
if d[k] < 2:
return False
if pre != -1 and gcd(d[k], pre) == 1:
return False
pre = d[k]
return True
https://leetcode.com/problems/range-addition-ii/
class Solution:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
r, c = m, n
for op in ops:
r = min(r, op[0])
c = min(c, op[1])
return r * c
https://leetcode.com/problems/water-bottles/
class Solution:
def numWaterBottles(self, numBottles: int, numExchange: int) -> int:
ans = 0
carry = 0
while numBottles > 0:
ans += numBottles
t = numBottles + carry
numBottles = t // numExchange
carry = t % numExchange
return ans
https://leetcode.com/problems/count-substrings-with-only-one-distinct-letter/
class Solution:
def countLetters(self, s: str) -> int:
cnt = 1
curSum = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
cnt += 1
else:
cnt = 1
curSum += cnt
return curSum
https://leetcode.com/problems/count-square-sum-triples/
class Solution:
def countTriples(self, n: int) -> int:
cnt = 0
for a in range(1, n + 1):
for b in range(1, n + 1):
x = (a * a) + (b * b)
if (sqrt(x) % 1 == 0) and x <= (n * n):
cnt += 1
return cnt
https://leetcode.com/problems/divisor-game/
class Solution:
def divisorGame(self, n: int) -> bool:
return n % 2 == 0
https://leetcode.com/problems/nim-game/
class Solution:
def canWinNim(self, n: int) -> bool:
return n % 4 != 0
https://leetcode.com/problems/self-dividing-numbers/
class Solution:
def selfDividingNumbers(self, left: int, right: int) -> List[int]:
def helper(num):
i = num
while i:
rem = i % 10
if not rem:
return False
if num % rem != 0:
return False
i = i // 10
return True
return [i for i in range(left, right + 1) if helper(i)]
https://leetcode.com/problems/sum-of-all-odd-length-subarrays/
class Solution:
def sumOddLengthSubarrays(self, arr: List[int]) -> int:
n = len(arr)
ans = 0
for i in range(n):
lcnt = i
rcnt = n - i - 1
lOdd = (lcnt + 1) // 2
rOdd = (rcnt + 1) // 2
lEven = lcnt // 2 + 1
rEven = rcnt // 2 + 1
ans += arr[i] * (lOdd * rOdd + lEven * rEven)
return ans
https://leetcode.com/problems/fair-candy-swap/
class Solution:
def fairCandySwap(self, aliceSizes: List[int], bobSizes: List[int]) -> List[int]:
a = 0
b = 0
s = set()
for x in aliceSizes:
a += x
for x in bobSizes:
b += x
s.add(x)
for x in aliceSizes:
if (b - a)/2 + x in s:
return [x, (b - a) // 2 + x]
https://leetcode.com/problems/ugly-number/
class Solution:
def isUgly(self, n: int) -> bool:
if n <= 0:
return False
while n % 5 == 0:
n /= 5
while n % 3 == 0:
n /= 3
while n % 2 == 0:
n /= 2
return n == 1
https://leetcode.com/problems/power-of-three/
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n == 1:
return True
if n % 3 == 0 and n != 0:
return self.isPowerOfThree(n / 3)
return False
https://leetcode.com/problems/power-of-four/
class Solution:
def isPowerOfFour(self, n: int) -> bool:
if n == 1:
return True
if n % 4 == 0 and n != 0:
return self.isPowerOfFour(n / 4)
return False
https://leetcode.com/problems/perfect-number/
class Solution:
def checkPerfectNumber(self, num: int) -> bool:
curSum = 1
if num <= 1:
return False
for i in range(2, int(sqrt(num)) + 1):
if num % i == 0:
if i == num // i:
curSum += i
else:
curSum += i + num // i
return curSum == num
https://leetcode.com/problems/minimum-moves-to-equal-array-elements/
class Solution:
def minMoves(self, nums: List[int]) -> int:
m = min(nums)
ans = 0
for num in nums:
ans += num - m
return ans
https://leetcode.com/problems/count-odd-numbers-in-an-interval-range/
class Solution:
def countOdds(self, low: int, high: int) -> int:
ans = (high - low + 1) // 2
if high % 2 == 1 and low % 2 == 1:
ans += 1
return ans
https://leetcode.com/problems/minimum-time-visiting-all-points/
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
ans = 0
for i in range(1, len(points)):
ans += max(abs(points[i][0] - points[i - 1][0]), abs(points[i][1] - points[i - 1][1]))
return ans
https://leetcode.com/problems/palindrome-number/
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
y = 0
t = x
while t > 0:
y = y * 10 + t % 10
t = t // 10
return x == y
https://leetcode.com/problems/greatest-common-divisor-of-strings/
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if str1 + str2 != str2 + str1:
return ""
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
return str1[0: gcd(len(str1), len(str2))]
https://leetcode.com/problems/add-digits/
class Solution:
def addDigits(self, num: int) -> int:
while num > 9:
s = 0
while num > 0:
s += num % 10
num //= 10
num = s
return num
https://leetcode.com/problems/excel-sheet-column-title/
class Solution:
def convertToTitle(self, columnNumber: int) -> str:
ans = ''
while columnNumber > 0:
columnNumber -= 1
ans += chr(columnNumber % 26 + 65)
columnNumber = columnNumber // 26
return ans[::-1]
https://leetcode.com/problems/number-of-days-between-two-dates/
class Solution:
def daysBetweenDates(self, date1: str, date2: str) -> int:
def cal(s):
total = 0
y = int(s[:4])
m = int(s[5:7])
d = int(s[8:10])
for i in range(1971, y):
if i % 400 == 0 or (i % 4 == 0 and i % 100 != 0):
total += 366
else:
total += 365
month = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
for j in range(1, m):
total += month[j]
if j == 2 and (y % 400 == 0 or (y % 4 == 0 and y % 100 != 0)):
total += 1
return total + d
return abs(cal(date1) - cal(date2))
https://leetcode.com/problems/excel-sheet-column-number/
class Solution:
def titleToNumber(self, columnTitle: str) -> int:
ans = 0
for i in range(len(columnTitle)):
ans = ans * 26 + ord(columnTitle[i]) - ord('A') + 1
return ans
https://leetcode.com/problems/rectangle-overlap/
class Solution:
def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
a1, b1, a2, b2 = rec1[0], rec1[1], rec1[2], rec1[3]
x1, y1, x2, y2 = rec2[0], rec2[1], rec2[2], rec2[3]
return not (a2 <= x1 or x2 <= a1 or b2 <= y1 or y2 <= b1)
https://leetcode.com/problems/maximum-product-of-three-numbers/
class Solution:
def maximumProduct(self, nums: List[int]) -> int:
ans = 0
nums.sort()
n = len(nums) - 1
ans = max((nums[n - 2] * nums[n - 1] * nums[n]), (nums[0] * nums[1] * nums[-1]))
return ans
https://leetcode.com/problems/plus-one/
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
n = len(digits)
ans = []
carry = 0
for i in range(n - 1, -1, -1):
cur = carry + digits[i] + (1 if i == n - 1 else 0)
ans.append(cur % 10)
carry = cur // 10
if carry > 0:
ans.append(1)
return ans[::-1]
https://leetcode.com/problems/add-strings/
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
n = len(num1) - 1
m = len(num2) - 1
carry = 0
val = 0
ans = ""
while n >= 0 or m >= 0:
val = carry
if n >= 0:
val += int(num1[n])
n -= 1
if m >= 0:
val += int(num2[m])
m -= 1
ans += str(val % 10)
carry = val // 10
if carry > 0:
ans += str(carry)
return ans[::-1]
https://leetcode.com/problems/happy-number/
class Solution:
def isHappy(self, n: int) -> bool:
def cal(n):
ans = 0
while n > 0:
ans += (n % 10) * (n % 10)
n = n // 10
return ans
s = n
f = n
while f != 1 and cal(f) != 1:
s = cal(s)
f = cal(cal(f))
if s == f:
return False
return True
return cal(n)
• Bit Manipulation
https://leetcode.com/problems/missing-number/
class Solution:
def missingNumber(self, nums: List[int]) -> int:
n = len(nums)
t = 0
for i in range(1, n + 1):
t ^= i
t ^= nums[i - 1]
return t
https://leetcode.com/problems/complement-of-base-10-integer/
class Solution:
def bitwiseComplement(self, n: int) -> int:
if n == 0:
return 1
x = 1
while x <= n:
x <<= 1
return (x - 1) ^ n
https://leetcode.com/problems/binary-watch/
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
ans = []
for i in range(12):
for j in range(60):
if (bin(i) + bin(j)).count('1') == turnedOn:
ans.append(str(i) + ':' + ('0' if j < 10 else '') + str(j))
return ans
https://leetcode.com/problems/number-complement/
class Solution:
def findComplement(self, num: int) -> int:
p = 0
ans = 0
while num > 0:
ans += (1 - (num & 1)) * (2 ** p)
p += 1
num >>= 1
return ans
https://leetcode.com/problems/prime-number-of-set-bits-in-binary-representation/
class Solution:
def countPrimeSetBits(self, left: int, right: int) -> int:
prime = [0] * 35
prime[1] = 1
for i in range(2, 32):
if prime[i] == 0:
for j in range(i + i, 33, i):
prime[j] = 1
cnt = 0
for i in range(left, right + 1):
if prime[bin(i).count('1')] == 0:
cnt += 1
return cnt
https://leetcode.com/problems/sort-integers-by-the-number-of-1-bits/
class Solution:
def sortByBits(self, arr: List[int]) -> List[int]:
return sorted(arr, key = lambda x: (bin(x).count('1'), x))
https://leetcode.com/problems/find-the-difference/
class Solution:
def findTheDifference(self, s: str, t: str) -> str:
ans = 0
for c in s:
ans ^= ord(c)
for c in t:
ans ^= ord(c)
return chr(ans)
https://leetcode.com/problems/hamming-distance/
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
cnt = 0
while x > 0 or y > 0:
if (x & 1) != (y & 1):
cnt += 1
x >>= 1
y >>= 1
return cnt
https://leetcode.com/problems/number-of-1-bits/
class Solution:
def hammingWeight(self, n: int) -> int:
cnt = 0
while n:
if n & 1 > 0:
cnt += 1
n = n >> 1
return cnt
https://leetcode.com/problems/counting-bits/
class Solution:
def countBits(self, n: int) -> List[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ans
https://leetcode.com/problems/reverse-bits/
class Solution:
def reverseBits(self, n: int) -> int:
ans = 0
for _ in range(32):
ans <<= 1
ans |= n & 1
n >>= 1
return ans
https://leetcode.com/problems/convert-a-number-to-hexadecimal/
class Solution:
def toHex(self, num: int) -> str:
s = "0123456789abcdef"
ans = ""
if num == 0:
return "0"
elif num < 0:
num += 2**32
while num > 0:
ans += s[num % 16]
num >>= 4
return ans[::-1]
https://leetcode.com/problems/power-of-two/
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and n & (n-1) == 0
https://leetcode.com/problems/1-bit-and-2-bit-characters/
class Solution:
def isOneBitCharacter(self, bits: List[int]) -> bool:
i = 0
while i < len(bits) - 1:
i += bits[i] + 1
return i == len(bits) - 1
https://leetcode.com/problems/add-binary/
class Solution:
def addBinary(self, a: str, b: str) -> str:
m = len(a) - 1
n = len(b) - 1
ans = ""
val = 0
carry = 0
while m >= 0 or n >= 0:
val = carry
if m >= 0:
val += int(a[m])
m -= 1
if n >= 0:
val += int(b[n])
n -= 1
ans += str(val % 2)
carry = val // 2
if carry != 0:
ans += str(carry)
return ans[::-1]
https://leetcode.com/problems/single-number/
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for num in nums:
ans ^= num
return ans
• Queue
https://leetcode.com/problems/moving-average-from-data-stream/
class MovingAverage:
def __init__(self, size: int):
self.q = deque()
self.size = size
def next(self, val: int) -> float:
if len(self.q) < self.size:
self.q.append(val)
else:
self.q.popleft()
self.q.append(val)
return sum(self.q)/len(self.q)
• Stack
https://leetcode.com/problems/valid-parentheses/
class Solution:
def isValid(self, s: str) -> bool:
stack = []
lookup = {
")": "(",
"}": "{",
"]": "["
}
for c in s:
if c in lookup:
if len(stack) > 0 and stack[-1] == lookup[c]:
stack.pop()
else:
return False
else:
stack.append(c)
return len(stack) == 0
https://leetcode.com/problems/final-prices-with-a-special-discount-in-a-shop/
class Solution:
def finalPrices(self, prices: List[int]) -> List[int]:
stack = []
for i in range(len(prices)):
while len(stack) > 0 and prices[stack[-1]] >= prices[i]:
k = stack.pop()
prices[k] = prices[k] - prices[i]
stack.append(i)
return prices
https://leetcode.com/problems/backspace-string-compare/
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
stack_s = []
stack_t = []
for i in range(len(s)):
if s[i] == "#":
if len(stack_s) > 0:
stack_s.pop()
else:
stack_s.append(s[i])
for i in range(len(t)):
if t[i] == "#":
if len(stack_t) > 0:
stack_t.pop()
else:
stack_t.append(t[i])
return stack_s == stack_t
https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for i in range(len(s)):
if len(stack) > 0 and stack[-1] == s[i]:
stack.pop()
else:
stack.append(s[i])
return "".join(stack)
https://leetcode.com/problems/baseball-game/
class Solution:
def calPoints(self, ops: List[str]) -> int:
stack = []
ans = 0
for i in range(len(ops)):
if ops[i] == "C":
stack.pop()
elif ops[i] == "D":
stack.append(stack[-1] * 2)
elif ops[i] == "+":
stack.append(stack[-1] + stack[-2])
else:
stack.append(int(ops[i]))
for num in stack:
ans += num
return ans
https://leetcode.com/problems/next-greater-element-i/
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
lookup = {}
stack = []
ans = []
for i in range(len(nums2)):
while len(stack) > 0 and stack[-1] < nums2[i]:
lookup[stack.pop()] = nums2[i]
stack.append(nums2[i])
for num in nums1:
if num in lookup:
ans.append(lookup[num])
else:
ans.append(-1)
return ans
https://leetcode.com/problems/min-stack/
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
if len(self.minStack) == 0 or val <= self.minStack[-1]:
self.minStack.append(val)
def pop(self) -> None:
k = self.stack.pop()
if self.minStack[-1] == k:
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
• Greedy
https://leetcode.com/problems/minimum-cost-to-move-chips-to-the-same-position/
class Solution:
def minCostToMoveChips(self, position: List[int]) -> int:
odd = 0
even = 0
for x in position:
if x % 2 == 0:
even += 1
else:
odd += 1
return min(even, odd)
https://leetcode.com/problems/largest-perimeter-triangle/
class Solution:
def largestPerimeter(self, nums: List[int]) -> int:
nums.sort()
for i in range(len(nums) - 1, 1, -1):
a = nums[i]
b = nums[i - 1]
c = nums[i - 2]
if b + c > a:
return a + b + c
return 0
• Linked List
https://leetcode.com/problems/reverse-linked-list/
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre
https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/
class Solution:
def getDecimalValue(self, head: ListNode) -> int:
ans = 0
cur = head
while cur:
ans = ans * 2 + cur.val
cur = cur.next
return ans
https://leetcode.com/problems/middle-of-the-linked-list/
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = head
fast = head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
return slow
https://leetcode.com/problems/delete-node-in-a-linked-list/
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
https://leetcode.com/problems/remove-linked-list-elements/
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
dummy = ListNode(-1)
dummy.next = head
cur = dummy
while cur.next != None:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy.next
https://leetcode.com/problems/remove-duplicates-from-sorted-list/
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
cur = head
while cur.next:
if cur.val == cur.next.val:
cur.next = cur.next.next
else:
cur = cur.next
return head
https://leetcode.com/problems/intersection-of-two-linked-lists/
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
a = headA
b = headB
while a != b:
a = headB if a == None else a.next
b = headA if b == None else b.next
return a
https://leetcode.com/problems/linked-list-cycle/
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
if head == None or head.next == None:
return False
fast, slow = head, head
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
https://leetcode.com/problems/merge-two-sorted-lists/
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
prehead = ListNode(-1)
prev = prehead
while list1 and list2:
if list1.val <= list2.val:
prev.next = list1
list1 = list1.next
else:
prev.next = list2
list2 = list2.next
prev = prev.next
if list1:
prev.next = list1
if list2:
prev.next = list2
return prehead.next
https://leetcode.com/problems/palindrome-linked-list/
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
if head == None or head.next == None:
return True
prev = None
slow = head
fast = head
while fast != None and fast.next != None:
fast = fast.next.next
prev = slow
slow = slow.next
prev.next = None
pre = None
cur = slow
while cur:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
while head != None and pre != None:
if head.val != pre.val:
return False
head = head.next
pre = pre.next
return True
• Tree
https://leetcode.com/problems/same-tree/
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None and q is None:
return True
if p is None or q is None:
return False
return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
https://leetcode.com/problems/construct-string-from-binary-tree/
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
ans = ""
if root == None:
return ans
ans += str(root.val)
if root.left == None and root.right == None:
return ans
ans += '(' + self.tree2str(root.left) + ')'
if root.right != None:
ans += '(' + self.tree2str(root.right) + ')'
return ans
https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers/
class Solution:
def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
self.curSum = 0
def dfs(node, x):
if node == None:
return
x = x << 1 | node.val
if node.left == None and node.right == None:
self.curSum += x
dfs(node.left, x)
dfs(node.right, x)
dfs(root, 0)
return self.curSum
https://leetcode.com/problems/find-mode-in-binary-search-tree/
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.pre = root.val
self.cur, self.max = 0, 0
self.ans = []
def dfs(node):
if node == None:
return
dfs(node.left)
if node.val != self.pre:
self.cur = 1
self.pre = node.val
else:
self.cur += 1
if self.cur > self.max:
self.max = self.cur
self.ans.clear()
self.ans.append(node.val)
elif self.cur == self.max:
self.ans.append(node.val)
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/binary-tree-tilt/
class Solution:
def findTilt(self, root: Optional[TreeNode]) -> int:
self.tilt = 0
def dfs(node):
if node == None:
return 0
l = dfs(node.left)
r = dfs(node.right)
self.tilt += abs(l - r)
return l + r + node.val
dfs(root)
return self.tilt
https://leetcode.com/problems/minimum-absolute-difference-in-bst/
class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
self.global_min = float("inf")
self.prev = None
def helper(root):
if root is None:
return
helper(root.left)
if self.prev:
self.global_min = min(abs(root.val - self.prev.val), self.global_min)
self.prev = root
helper(root.right)
helper(root)
return self.global_min
https://leetcode.com/problems/n-ary-tree-postorder-traversal/
class Solution:
def postorder(self, root: 'Node') -> List[int]:
self.ans = []
def dfs(node):
if node == None:
return
for child in node.children:
dfs(child)
self.ans.append(node.val)
dfs(root)
return self.ans
https://leetcode.com/problems/n-ary-tree-preorder-traversal/
class Solution:
def preorder(self, root: 'Node') -> List[int]:
self.ans = []
def dfs(node):
if node == None:
return
self.ans.append(node.val)
for child in node.children:
dfs(child)
dfs(root)
return self.ans
https://leetcode.com/problems/leaf-similar-trees/
class Solution:
def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
root1arr = []
root2arr = []
def helper(root, arr):
if root is None:
return 0
if root.left is None and root.right is None:
arr.append(root.val)
helper(root.left, arr)
helper(root.right, arr)
helper(root1, root1arr)
helper(root2, root2arr)
return root1arr == root2arr
https://leetcode.com/problems/increasing-order-search-tree/
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
dummy = TreeNode(-1)
self.cur = dummy
def dfs(node):
if node == None:
return
dfs(node.left)
self.cur.right = node
node.left = None
self.cur = self.cur.right
dfs(node.right)
dfs(root)
return dummy.right
https://leetcode.com/problems/maximum-depth-of-n-ary-tree/
class Solution:
def maxDepth(self, root: 'Node') -> int:
if root is None:
return 0
ans = 1
for child in root.children:
ans = max(self.maxDepth(child) + 1, ans)
return ans
https://leetcode.com/problems/sum-of-left-leaves/
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(node):
if node == None:
return 0
if node.left != None and node.left.left == None and node.left.right == None:
self.ans += node.left.val
dfs(node.left)
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/average-of-levels-in-binary-tree/
class Solution:
def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
ans = []
q = collections.deque()
q.append(root)
while q:
levelSum = 0
k = len(q)
for _ in range(k):
node = q.popleft()
levelSum += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(levelSum / k)
return ans
https://leetcode.com/problems/minimum-depth-of-binary-tree/
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
self.ans = float("inf")
if root == None:
return 0
def dfs(node, dep):
if node == None:
return 0
if node.left == None and node.right == None:
self.ans = min(self.ans, dep)
dfs(node.left, dep + 1)
dfs(node.right, dep + 1)
dfs(root, 1)
return self.ans
https://leetcode.com/problems/binary-tree-inorder-traversal/
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
if root is None:
return ans
while stack:
cur = stack.pop()
if cur != None:
if cur.right != None:
stack.append(cur.right)
stack.append(cur)
stack.append(None)
if cur.left != None:
stack.append(cur.left)
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/binary-tree-postorder-traversal/
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
if root is None:
return ans
while stack:
cur = stack.pop()
if cur != None:
stack.append(cur)
stack.append(None)
if (cur.right != None):
stack.append(cur.right)
if (cur.left != None):
stack.append(cur.left)
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/binary-tree-preorder-traversal/
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = [root]
if root is None:
return ans
while stack:
cur = stack.pop()
if cur != None:
if (cur.right != None):
stack.append(cur.right)
if (cur.left != None):
stack.append(cur.left)
stack.append(cur)
stack.append(None)
else:
ans.append(stack.pop().val)
return ans
https://leetcode.com/problems/two-sum-iv-input-is-a-bst/
class Solution:
def __init__(self):
self.seen = set()
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
if root == None:
return False
if k - root.val in self.seen:
return True
self.seen.add(root.val)
return self.findTarget(root.left, k) or self.findTarget(root.right, k)
https://leetcode.com/problems/binary-tree-paths/
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
ans = []
def dfs(node, t):
if node is None:
return []
if node.left == None and node.right == None:
return ans.append(t + str(node.val))
t += str(node.val) + "->"
dfs(node.left, t)
dfs(node.right, t)
dfs(root, "")
return ans
https://leetcode.com/problems/closest-binary-search-tree-value/
class Solution:
def closestValue(self, root: Optional[TreeNode], target: float) -> int:
self.ans = root.val
while root != None:
if abs(root.val - target) < abs(self.ans - target):
self.ans = root.val
root = root.left if root.val > target else root.right
return self.ans
https://leetcode.com/problems/balanced-binary-tree/
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(node):
if node == None:
return 0
l, r = dfs(node.left), dfs(node.right)
if l == -1:
return -1
if r == -1:
return -1
if abs(l - r) > 1:
return -1
return max(l, r) + 1
return dfs(root) != -1
https://leetcode.com/problems/range-sum-of-bst/
class Solution:
def rangeSumBST(self, root: Optional[TreeNode], low: int, high: int) -> int:
if not root:
return 0
if root.val > high:
return self.rangeSumBST(root.left, low, high)
if root.val < low:
return self.rangeSumBST(root.right, low, high)
return root.val + self.rangeSumBST(root.left, low, high) + self.rangeSumBST(root.right, low, high)
https://leetcode.com/problems/merge-two-binary-trees/
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if root1 is None and root2 is None:
return None
if root1 is None and root2 is not None:
return root2
if root1 is not None and root2 is None:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
https://leetcode.com/problems/cousins-in-binary-tree/
class Solution:
def isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
self.parx = None
self.pary = None
self.depx = 0
self.depy = 0
if root.val == x or root.val == y:
return False
def dfs(root, par, target, dep):
if root is None:
return
if root.val == target:
if target == x:
self.parx = par
self.depx = dep
else:
self.pary = par
self.depy = dep
return
dfs(root.left, root, target, dep + 1)
dfs(root.right, root, target, dep + 1)
dfs(root, -1, x, 0)
dfs(root, -1, y, 0)
return self.parx != self.pary and self.depx == self.depy
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(left, right):
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = dfs(left, mid - 1)
root.right = dfs(mid + 1, right)
return root
return dfs(0, len(nums) - 1)
https://leetcode.com/problems/invert-binary-tree/
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
t = root.right
root.right = self.invertTree(root.left)
root.left = self.invertTree(t)
return root
https://leetcode.com/problems/path-sum/
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None and root.val == targetSum:
return True
return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)
https://leetcode.com/problems/maximum-depth-of-binary-tree/
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root is None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
https://leetcode.com/problems/subtree-of-another-tree/
class Solution:
def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
def sameTree(t1, t2):
if t1 is None and t2 is None:
return True
if t1 is None or t2 is None:
return False
return t1.val == t2.val and sameTree(t1.left, t2.left) and sameTree(t1.right, t2.right)
if sameTree(root, subRoot):
return True
return (root.left != None and self.isSubtree(root.left, subRoot)) or (root.right != None and self.isSubtree(root.right, subRoot))
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
if root.val > p.val and root.val > q.val:
return self.lowestCommonAncestor(root.left, p, q)
return root
https://leetcode.com/problems/diameter-of-binary-tree/
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(node):
if node == None:
return 0
l = dfs(node.left)
r = dfs(node.right)
self.ans = max(l + r, self.ans)
return max(l, r) + 1
dfs(root)
return self.ans
https://leetcode.com/problems/symmetric-tree/
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
if root is None:
return True
def symmetric(a, b):
return (a is None and b is None) or (a != None and b != None and a.val == b.val and symmetric(a.left, b.right) and symmetric(a.right, b.left))
return symmetric(root.left, root.right)
• Heap
https://leetcode.com/problems/kth-largest-element-in-a-stream/
class KthLargest:
def __init__(self, k: int, nums: List[int]):
self.pq = []
self.k = k
for num in nums:
self.add(num)
def add(self, val: int) -> int:
heapq.heappush(self.pq, val)
if len(self.pq) > self.k:
heapq.heappop(self.pq)
return self.pq[0]
https://leetcode.com/problems/maximize-sum-of-array-after-k-negations/
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
pq = []
ans = 0
for x in nums:
heapq.heappush(pq, x)
while k > 0:
heapq.heappush(pq, -heapq.heappop(pq))
k -= 1
while len(pq) > 0:
ans += heapq.heappop(pq)
return ans
https://leetcode.com/problems/last-stone-weight/
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
stones = [-x for x in stones]
heapq.heapify(stones)
while len(stones) > 1:
first = -1 * heapq.heappop(stones)
second = -1 * heapq.heappop(stones)
if first != second:
heapq.heappush(stones, -1 *(first - second))
return 0 if len(stones) == 0 else -1 * stones[0]
• Matrix
https://leetcode.com/problems/transpose-matrix/
class Solution:
def transpose(self, matrix: List[List[int]]) -> List[List[int]]:
m = len(matrix)
n = len(matrix[0])
ans = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
for j in range(m):
ans[i][j] = matrix[j][i]
return ans
https://leetcode.com/problems/surface-area-of-3d-shapes/
class Solution:
def surfaceArea(self, grid: List[List[int]]) -> int:
curSum = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
curSum += max(grid[i][j] - (grid[i - 1][j] if i > 0 else 0), 0)
curSum += max(grid[i][j] - (grid[i][j - 1] if j > 0 else 0), 0)
curSum += max(grid[i][j] - (grid[i + 1][j] if i < m - 1 else 0), 0)
curSum += max(grid[i][j] - (grid[i][j + 1] if j < n - 1 else 0), 0)
if grid[i][j] == 0:
curSum -= 2
return m * n * 2 + curSum
https://leetcode.com/problems/image-smoother/
class Solution:
def imageSmoother(self, img: List[List[int]]) -> List[List[int]]:
m, n = len(img), len(img[0])
ans = [[0 for j in range(n)] for i in range(m)]
for i in range(m):
for j in range(n):
cnt = 0
curSum = 0
for a in range(i - 1, i + 2):
for b in range(j - 1, j + 2):
if 0 <= a < m and 0 <= b < n:
cnt += 1
curSum += img[a][b]
ans[i][j] = curSum // cnt
return ans
https://leetcode.com/problems/projection-area-of-3d-shapes/
class Solution:
def projectionArea(self, grid: List[List[int]]) -> int:
curSum = 0
m = len(grid)
n = len(grid[0])
for i in range(m):
maxN = 0
for j in range(n):
maxN = max(maxN, grid[i][j])
if grid[i][j] == 0:
curSum -= 1
curSum += maxN
for i in range(n):
maxN = 0
for j in range(m):
maxN = max(maxN, grid[j][i])
curSum += maxN
return m * n + curSum
https://leetcode.com/problems/reshape-the-matrix/
class Solution:
def matrixReshape(self, mat: List[List[int]], r: int, c: int) -> List[List[int]]:
if r * c != len(mat) * len(mat[0]):
return mat
ans = [[0 for j in range(c)] for i in range(r)]
i = 0
j = 0
for x in mat:
for e in x:
ans[i][j] = e
j += 1
if j == c:
j = 0
i += 1
return ans
https://leetcode.com/problems/cells-with-odd-values-in-a-matrix/
class Solution:
def oddCells(self, m: int, n: int, indices: List[List[int]]) -> int:
a = [0] * m
b = [0] * n
for i in indices:
a[i[0]] += 1
b[i[1]] += 1
aOdd = 0
aEven = 0
for x in a:
if x % 2 == 0:
aEven += 1
else:
aOdd += 1
ans = 0
for x in b:
ans += aOdd if x % 2 == 0 else aEven
return ans
https://leetcode.com/problems/toeplitz-matrix/
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if i > 0 and j > 0 and matrix[i][j] != matrix[i - 1][j - 1]:
return False
return True
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
m = len(matrix)
n = len(matrix[0])
'''
the indicies of top-left bottom-right diagonals are r-c
top-right bottom-left diagonals are r+c
'''
lookup = {}
for r in range(m):
for c in range(n):
diag_idx = r - c
if diag_idx in lookup:
if lookup[diag_idx] != matrix[r][c]:
return False
else:
lookup[diag_idx] = matrix[r][c]
return True
https://leetcode.com/problems/flipping-an-image/
class Solution:
def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
m = len(image)
n = len(image[0])
for i in range(m):
l = 0
r = n - 1
while l <= r:
t = image[i][l]
image[i][l] = image[i][r]
image[i][r] = t
image[i][l] = 1 - image[i][l]
if l != r:
image[i][r] = 1 - image[i][r]
l += 1
r -= 1
return image
https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
m = len(mat)
n = len(mat[0])
ans = []
l = []
for i in range(m):
cnt = 0
for j in range(n):
if mat[i][j] == 1:
cnt += 1
l.append([cnt, i])
l = sorted(sorted(l, key = lambda x: x[1]), key = lambda x: x[0])
for i in range(k):
ans.append(l[i][1])
return ans
https://leetcode.com/problems/count-negative-numbers-in-a-sorted-matrix/
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
ans = 0
m = len(grid)
n = len(grid[0])
i = m - 1
j = 0
while i >=0 and j < n:
if grid[i][j] >= 0:
ans += i + 1
j += 1
else:
i -= 1
return m * n - ans
https://leetcode.com/problems/flood-fill/
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
self.directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
def dfs(image, i, j, newColor, oldColor):
image[i][j] = newColor
for d in self.directions:
ni = i + d[0]
nj = j + d[1]
if ni >= 0 and nj >= 0 and ni < len(image) and nj < len(image[0]) and image[ni][nj] == oldColor:
dfs(image, ni, nj, newColor, oldColor)
if image[sr][sc] != newColor:
dfs(image, sr, sc, newColor, image[sr][sc])
return image
https://leetcode.com/problems/island-perimeter/
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
ans = 0
m = len(grid)
n = len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
ans += 4
if i + 1 < m and grid[i + 1][j] == 1:
ans -= 1
if j + 1 < n and grid[i][j + 1] == 1:
ans -= 1
if i - 1 >= 0 and grid[i - 1][j] == 1:
ans -= 1
if j - 1 >= 0 and grid[i][j - 1] == 1:
ans -= 1
return ans
• Graph
https://leetcode.com/problems/find-the-town-judge/
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
ind = [0] * (n + 1)
outd = [0] * (n + 1)
for x in trust:
ind[x[1]] += 1
outd[x[0]] += 1
for i in range(1, n + 1):
if ind[i] == n - 1 and outd[i] == 0:
return i
return -1
https://leetcode.com/problems/find-if-path-exists-in-graph/
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
g = {}
vis = set()
for e in edges:
if e[0] in g:
g[e[0]].append(e[1])
else:
g[e[0]] = [e[1]]
if e[1] in g:
g[e[1]].append(e[0])
else:
g[e[1]] = [e[0]]
def dfs(u, d):
if u == d:
return True
vis.add(u)
for v in g[u]:
if v in vis:
continue
if dfs(v, d):
return True
return False
return dfs(source, destination)
• Dynamic Programming
https://leetcode.com/problems/climbing-stairs/
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
https://leetcode.com/problems/n-th-tribonacci-number/
class Solution:
def tribonacci(self, n: int) -> int:
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
dp[2] = 1
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
https://leetcode.com/problems/min-cost-climbing-stairs/
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
n = len(cost)
dp = [0] * (n + 1)
if n == 2:
return min(cost[0], cost[1])
for i in range(2, n + 1):
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
return dp[n]
https://leetcode.com/problems/fibonacci-number/
class Solution:
def fib(self, n: int) -> int:
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
• Design
https://leetcode.com/problems/design-parking-system/
class ParkingSystem:
def __init__(self, big: int, medium: int, small: int):
self.slots = [0] * 3
self.slots[0] = big
self.slots[1] = medium
self.slots[2] = small
def addCar(self, carType: int) -> bool:
if self.slots[carType - 1] > 0:
self.slots[carType - 1] -= 1
return True
return False
https://leetcode.com/problems/design-an-ordered-stream/
class OrderedStream:
def __init__(self, n: int):
self.i = 0
self.s = [None] * n
def insert(self, idKey: int, value: str) -> List[str]:
self.s[idKey - 1] = value
ans = []
while self.i < len(self.s) and self.s[self.i]:
ans.append(self.s[self.i])
self.i += 1
return ans
https://leetcode.com/problems/two-sum-iii-data-structure-design/
class TwoSum:
def __init__(self):
self.map = {}
def add(self, number: int) -> None:
self.map[number] = self.map.get(number, 0) + 1
def find(self, value: int) -> bool:
for k in self.map:
if k == value - k and self.map[k] >= 2:
return True
elif k != value - k and value - k in self.map:
return True
return False
https://leetcode.com/problems/logger-rate-limiter/
class Logger:
def __init__(self):
self.lookup = {}
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
if message not in self.lookup or timestamp - self.lookup[message] >= 10:
self.lookup[message] = timestamp
return True
return False
https://leetcode.com/problems/implement-stack-using-queues/
class MyStack:
def __init__(self):
self.q = deque([])
def push(self, x: int) -> None:
self.q.append(x)
def pop(self) -> int:
for i in range(len(self.q) - 1):
self.q.append(self.q.popleft())
return self.q.popleft()
def top(self) -> int:
return self.q[-1]
def empty(self) -> bool:
return len(self.q) == 0
https://leetcode.com/problems/max-stack/
class MaxStack:
def __init__(self):
self.maxStack = []
def push(self, x: int) -> None:
self.maxStack.append(x)
def pop(self) -> int:
return self.maxStack.pop()
def top(self) -> int:
return self.maxStack[-1]
def peekMax(self) -> int:
return max(self.maxStack)
def popMax(self) -> int:
max_val = self.peekMax()
t = float("-inf")
for i in range(len(self.maxStack) - 1, -1, -1):
if self.maxStack[i] == max_val:
t = self.maxStack.pop(i)
return t
https://leetcode.com/problems/implement-queue-using-stacks/
class MyQueue:
def __init__(self):
self.a_stack = []
self.b_stack = []
def push(self, x: int) -> None:
self.a_stack.append(x)
def pop(self) -> int:
if len(self.b_stack) == 0:
while len(self.a_stack) > 0:
self.b_stack.append(self.a_stack.pop())
return self.b_stack.pop()
def peek(self) -> int:
if len(self.b_stack) == 0:
while len(self.a_stack) > 0:
self.b_stack.append(self.a_stack.pop())
return self.b_stack[-1]
def empty(self) -> bool:
return len(self.a_stack) == 0 and len(self.b_stack) == 0