# Algo-Prep
{% tabs %}
{% tab title="LeetCode" %}
````python
```py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
c = 0
res = []
while(l1 or l2):
s = 0 + c
if l1:
s += int(l1.val)
l1 = l1.next
if l2:
s += int(l2.val)
l2 = l2.next
print(s)
resa = s % 10
res.append(resa)
c = s // 10
if(c!=0):
res.append(c)
l3 = ListNode(0)
head = l3
for i in range(0, len(res)):
lt = res[i]
l3.next = ListNode(lt)
l3 = l3.next
return head.nextclass Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g = sorted(g)
s = sorted(s)
content = 0
while s and g:
if s[-1] >= g[-1]:
s.pop()
content += 1
g.pop()
return content# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def convertBST(self, root: TreeNode) -> TreeNode:
self.ans = 0
def add(node):
if not node:
return
add(node.right)
self.ans += node.val
node.val = self.ans
add(node.left)
add(root)
return root## Recursive Solution
# ------------------------------------------
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
io = []
if(root==None):
return []
def inorder(x):
if(x.left!=None):
inorder(x.left)
io.append(int(x.val))
if(x.right!=None):
inorder(x.right)
inorder(root)
return io
# ------------------------------------------
## Iterative Solution using Stack
# ------------------------------------------
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if(root==None):
return []
stack = []
io = []
c = root
while(c!=None or len(stack)!=0):
while(c!=None):
stack.append(c)
c = c.left
c = stack.pop()
io.append(c.val)
c = c.right
return io
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# ------------------------------------------
## Recursive Solution
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
if (root==None):
return []
po = []
def postorder(x):
if not x:
return
postorder(x.left)
postorder(x.right)
po.append(x.val)
postorder(root)
return po
# ------------------------------------------
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# ------------------------------------------
## Recursive Solution
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if(root==None):
return []
po = []
def preorder(x):
if x:
po.append(x.val)
preorder(x.left)
preorder(x.right)
preorder(root)
return po
# ------------------------------------------
## Iterative Solution
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
if(root==None):
return []
stack = []
po = []
c = root
while(c!=None or len(stack)!=0):
while(c!=None):
stack.append(c)
po.append(c.val)
c = c.left
c = stack.pop()
c = c.right
return po
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
def deleteBackSpace(X):
stack = []
for i in X:
if not i=='#':
stack.append(i)
elif(len(stack)==0):
continue
else:
stack.pop()
return stack
return deleteBackSpace(S)==deleteBackSpace(T)# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def balanceBST(self, root: TreeNode) -> TreeNode:
result = []
def inorder(node):
if node:
if node.left!=None:
inorder(node.left)
result.append(int(node.val))
if node.right!=None:
inorder(node.right)
def constructBalancedTree(arr):
if not arr:
return None
mid = len(arr)//2
root = TreeNode(arr[mid])
root.left = constructBalancedTree(arr[:mid])
root.right = constructBalancedTree(arr[mid+1:])
return root
inorder(root)
# result = [int(x.val) for x in result]
return constructBalancedTree(result)class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(0, len(prices)-1):
if(prices[i+1] > prices[i]):
profit += prices[i+1] - prices[i]
return profitimport math
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
ans = m
if not m==0:
x = math.log2(m)
x = int(x)+1
x = 2**x
else:
return 0
if(n>=x):
return 0
for i in range(m+1, n+1):
ans = ans & i
return ansfrom collections import Counter
class Solution:
def count(self, d1, d2):
s = 0
for i in 'abcdefghijklmnopqrstuvwxyz':
s += d1[i] - d2[i]
if s < 0:
return False
return True
def checkIfCanBreak(self, s1: str, s2: str) -> bool:
d1 = Counter(s1)
d2 = Counter(s2)
return self.count(d1, d2) | self.count(d2, d1)class Solution:
def maxArea(self, height: List[int]) -> int:
i = 0
j = len(height)-1
maxarea = 0
while(i!=j):
a = (j-i)*(min(height[i], height[j]))
if(a>maxarea):
maxarea = a
if(height[i]>height[j]):
j -= 1
else:
i += 1
return maxareaclass Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return not len(nums) == len(set(nums))class Solution:
def findMaxLength(self, nums: List[int]) -> int:
dic = { 0:-1 }
ps = 0
max_length = 0
for idx, number in enumerate(nums):
if number:
ps += 1
else:
ps -= 1
if ps in dic:
max_length = max(max_length, idx-dic[ps])
else:
dic[ps] = idx
return max_length# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def countNodes(self, root: TreeNode) -> int:
if not root:
return 0
self.c = 0
def count(node):
if node:
if node.left:
count(node.left)
if node.right:
count(node.right)
self.c += 1
return self.c
count(root)
return self.cclass Solution:
def countBits(self, num: int) -> List[int]:
ans = [0]
offset = 1
for i in range(1, num+1):
if(offset*2 == i):
offset = i
ans.append(ans[i-offset]+1)
return ansclass Solution:
def countElements(self, arr: List[int]) -> int:
s = set()
s = set(arr)
c = 0
for i in range(len(arr)):
if(arr[i]+1 in s):
c += 1
return cfrom collections import deque
class Solution:
def canFinish(self, numCourses, prerequisites) -> bool:
adjList = [[] for _ in range(numCourses)]
inDegree = [0 for _ in range(numCourses)]
queue = deque()
visited = 0
for i in range(len(prerequisites)):
adjList[prerequisites[i][0]].append(prerequisites[i][1])
for i in range(numCourses):
for j in adjList[i]:
inDegree[j] += 1
for i in range(len(inDegree)):
if inDegree[i] == 0:
queue.append(i)
while queue:
el = queue.popleft()
for i in adjList[el]:
inDegree[i] -= 1
if inDegree[i] == 0:
queue.append(i)
visited += 1
if visited == numCourses:
return True
else:
return Falseclass Solution:
def minDeletionSize(self, A: List[str]) -> int:
s = 0
for col in zip(*A):
if any(col[i] > col[i+1] for i in range(len(col)-1)):
s += 1
return sclass Solution:
def deleteNode(self, root, key):
if not root:
return
if key > root.val:
root.right = self.deleteNode(root.right, key)
elif key < root.val:
root.left = self.deleteNode(root.left, key)
else:
if not root.left:
return root.right
else:
temp = root.left
while temp.right:
temp = temp.right
root.val = temp.val
root.left = self.deleteNode(root.left, temp.val)
return root# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.nextclass MyCircularDeque:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the deque to be k.
"""
self.maxsize = k
self.size = 0
self.decq = [0]*k
self.front = self.rear = -1
def insertFront(self, value: int) -> bool:
"""
Adds an item at the front of Deque. Return true if the operation is successful.
"""
if self.size == self.maxsize:
return False
else:
if self.front == -1:
self.front = self.rear = 0
else:
self.front = (self.front-1)%self.maxsize
self.decq[self.front] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
"""
Adds an item at the rear of Deque. Return true if the operation is successful.
"""
if self.size == self.maxsize:
return False
else:
if self.rear == -1:
self.front = self.rear = 0
else:
self.rear = (self.rear+1)%self.maxsize
self.decq[self.rear] = value
self.size += 1
return True
def deleteFront(self) -> bool:
"""
Deletes an item from the front of Deque. Return true if the operation is successful.
"""
if self.size == 0:
return False
else:
if self.front == self.rear:
self.front = self.rear = -1
else:
self.decq[self.front] = 0
self.front = (self.front+1)%self.maxsize
self.size -= 1
return True
def deleteLast(self) -> bool:
"""
Deletes an item from the rear of Deque. Return true if the operation is successful.
"""
if self.size == 0:
return False
else:
if self.front == self.rear:
self.front = self.rear = -1
else:
self.decq[self.rear] = 0
self.rear = (self.rear-1)%self.maxsize
self.size -= 1
return True
def getFront(self) -> int:
"""
Get the front item from the deque.
"""
return self.decq[self.front] if self.size != 0 else -1
def getRear(self) -> int:
"""
Get the last item from the deque.
"""
return self.decq[self.rear] if self.size != 0 else -1
def isEmpty(self) -> bool:
"""
Checks whether the circular deque is empty or not.
"""
return self.size == 0
def isFull(self) -> bool:
"""
Checks whether the circular deque is full or not.
"""
return self.size == self.maxsize
# ------------------------------------------
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()
# ------------------------------------------
# Another Optimized Solution
class MyCircularDeque:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the deque to be k.
"""
self.decq = []
self.maxsize = k
def insertFront(self, value: int) -> bool:
"""
Adds an item at the front of Deque. Return true if the operation is successful.
"""
if len(self.decq) < self.maxsize:
self.decq.append(value)
return True
def insertLast(self, value: int) -> bool:
"""
Adds an item at the rear of Deque. Return true if the operation is successful.
"""
if len(self.decq) < self.maxsize:
self.decq.insert(0, value)
return True
def deleteFront(self) -> bool:
"""
Deletes an item from the front of Deque. Return true if the operation is successful.
"""
if self.decq:
self.decq.pop()
return True
def deleteLast(self) -> bool:
"""
Deletes an item from the rear of Deque. Return true if the operation is successful.
"""
if self.decq:
del self.decq[0]
return True
def getFront(self) -> int:
"""
Get the front item from the deque.
"""
return self.decq[-1] if self.decq else -1
def getRear(self) -> int:
"""
Get the last item from the deque.
"""
return self.decq[0] if self.decq else -1
def isEmpty(self) -> bool:
"""
Checks whether the circular deque is empty or not.
"""
return len(self.decq)==0
def isFull(self) -> bool:
"""
Checks whether the circular deque is full or not.
"""
return len(self.decq)==self.maxsize
# ------------------------------------------
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()class MyCircularQueue:
def __init__(self, k: int):
self.size = 0
self.maxsize = k
self.cq = [0]*k
self.front = self.rear = -1
def enQueue(self, value: int) -> bool:
if self.size == self.maxsize:
return False
else:
if self.rear == -1:
self.rear = self.front = 0
else:
self.rear = (self.rear+1)%self.maxsize
self.cq[self.rear] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.size == 0:
return False
if self.front == self.rear:
self.front = self.rear = -1
else:
self.front = (self.front+1)%self.maxsize
self.size -= 1
return True
def Front(self) -> int:
return self.cq[self.front] if self.size!=0 else -1
def Rear(self) -> int:
return self.cq[self.rear] if self.size!=0 else -1
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.maxsize
# ------------------------------------------
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.depth = 1
def findDepth(first):
if not first:
return 0
ld = findDepth(first.left)
rd = findDepth(first.right)
self.depth = max(self.depth, ld+rd+1)
return max(ld,rd) + 1
findDepth(root)
return self.depth - 1class Solution:
def trailingZeroes(self, n: int) -> int:
count = 0
m = 5
while (n/m >= 1):
count += int(n/m)
m *= 5
return count # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findBottomLeftValue(self, root: TreeNode) -> int:
queue = deque([root])
visited = set()
while queue:
size = len(queue)
leftmost = math.inf
for i in range(size):
node = queue.popleft()
if leftmost == math.inf:
leftmost = node.val
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
if not queue:
return leftmost
return 0# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
tree = collections.defaultdict()
tree.default_factory = tree.__len__
c = collections.Counter()
anslist = []
def find(node):
if node:
tid = tree[node.val, find(node.left), find(node.right)]
c[tid] += 1
if c[tid] == 2:
anslist.append(node)
return tid
find(root)
return anslistfrom collections import Counter
class Solution:
def firstUniqChar(self, s: str) -> int:
c = Counter(s)
for i in range(len(s)):
if c[s[i]] == 1:
return i
return -1class Solution:
def fizzBuzz(self, n: int) -> List[str]:
res = []
for i in range(1, n+1):
if i % 3 == 0 and i % 5 == 0:
res.append("FizzBuzz")
elif i % 3 == 0:
res.append("Fizz")
elif i % 5 == 0:
res.append("Buzz")
else:
res.append(str(i))
return resimport collections
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
word = collections.defaultdict(list)
for s in strs:
word[tuple(sorted(s))].append(s)
return word.values()class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.s1 = []
self.s2 = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.s1.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
while len(self.s1) > 1:
self.s2.append(self.s1.pop())
temp = self.s1.pop()
while len(self.s2):
self.s1.append(self.s2.pop())
return temp
def peek(self) -> int:
"""
Get the front element.
"""
return self.s1[0]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
return False if len(self.s1) else True
# ------------------------------------------
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()## Implementation Using queue.Queue()
## Faster than 67%
from queue import Queue
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q1 = Queue(maxsize=0)
self.q2 = Queue(maxsize=0)
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q1.put(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
while(self.q1.qsize()>1):
self.q2.put(self.q1.get())
temp = self.q1.get()
while(self.q2.qsize()>0):
self.q1.put(self.q2.get())
return temp
def top(self) -> int:
"""
Get the top element.
"""
while(self.q1.qsize()>1):
self.q2.put(self.q1.get())
temp = self.q1.get()
while(self.q2.qsize()>0):
self.q1.put(self.q2.get())
self.q1.put(temp)
return temp
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return self.q1.empty()
# ------------------------------------------
## Implementation using Deque
## Faster than 100%
from collections import deque
class MyStack:
def __init__(self):
"""
Initialize your data structure here.
"""
self.q = deque()
def push(self, x: int) -> None:
"""
Push element x onto stack.
"""
self.q.append(x)
def pop(self) -> int:
"""
Removes the element on top of the stack and returns that element.
"""
return self.q.pop()
def top(self) -> int:
"""
Get the top element.
"""
temp = self.q.pop()
self.q.append(temp)
return temp
def empty(self) -> bool:
"""
Returns whether the stack is empty.
"""
return False if len(self.q) else True
# ------------------------------------------
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()class CustomStack:
def __init__(self, maxSize: int):
self.stack = []
self.maxSize = maxSize
def push(self, x: int) -> None:
if(len(self.stack) < self.maxSize):
self.stack.append(x)
def pop(self) -> int:
if(len(self.stack)!=0):
return self.stack.pop()
else:
return -1
def increment(self, k: int, val: int) -> None:
for i in range(min(k, len(self.stack))):
self.stack[i] += val
# ------------------------------------------
# Your CustomStack object will be instantiated and called as such:
# obj = CustomStack(maxSize)
# obj.push(x)
# param_2 = obj.pop()
# obj.increment(k,val)import math
class Solution:
def integerReplacement(self, n: int) -> int:
s = 0
while(n!=1):
if(n%2==0):
n //= 2
s += 1
continue
if(n==3):
return s+2
else:
if(math.ceil(math.log2(n-1))==math.floor(math.log2(n-1))):
n -= 1
elif((math.ceil(math.log2(n+1))==math.floor(math.log2(n+1))) or ((n+1)%4==0)):
n += 1
else:
n -= 1
s += 1
return sclass Solution:
def intToRoman(self, num: int) -> str:
dic = { 1000:'M', 900:'CM', 500:'D', 400:'CD', 100:'C', 90:'XC', 50:'L', 40:'XL', 10:'X', 9:'IX', 5:'V', 4:'IV', 1:'I' }
ans = ''
for i in dic:
while num>=i:
ans += dic[i]
num -= i
return ansclass Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
if len(nums1) > len(nums2):
i = 0
while i < len(nums2):
if nums2[i] in set(nums1):
nums1.remove(nums2[i])
i += 1
else:
nums2.remove(nums2[i])
return nums2
else:
i = 0
while i < len(nums1):
if nums1[i] in set(nums2):
nums2.remove(nums1[i])
i += 1
else:
nums1.remove(nums1[i])
return nums1
# ------------------------------------------
# Alternate Approach
from collections import Counter
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list((Counter(nums1)&Counter(nums2)).elements())# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
def invert(node):
if node.left:
invert(node.left)
if node.right:
invert(node.right)
temp = node.left
node.left = node.right
node.right = temp
if root:
invert(root)
return rootclass Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if len(s) == 0:
return True
if len(t) == 0:
return False
sp = 0
for tc in t:
if s[sp] == tc:
sp += 1
if sp == len(s):
return True
return Falseclass Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
while(len(stones)!=1 and len(stones)!=0):
stones = sorted(stones)
t = abs(stones[-1]-stones[-2])
if(t!=0):
stones.pop()
stones[-1] = t
else:
stones.pop()
stones.pop()
if(stones):
return stones[0]
return 0class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
denom = {
5: 0,
10: 0,
20: 0
}
for i in range(len(bills)):
denom[bills[i]] += 1
if bills[i] > 5:
bal = bills[i] - 5
if bal % 5 == 0 and bal % 10 != 0:
if denom[5] > 0:
denom[5] -= 1
bal -= 5
if bal == 0:
continue
if bal % 10 == 0 and bal % 20 != 0:
if denom[10] > 0:
denom[10] -= 1
bal -= 10
if bal == 0:
continue
if denom[5] > 1:
denom[5] -= 2
bal -= 10
if bal == 0:
continue
if bal > 0:
return False
return Trueclass Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
x = 0
for i in zip(*strs):
r = all(a == i[0] for a in i)
if r:
x += 1
else:
break
return strs[0][0:x] if x else ''class Solution:
def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
A = sorted(A)
for i in range(len(A)):
if A[i] < 0:
A[i] = -A[i]
K -= 1
elif A[i] >= 0:
if K % 2 == 0:
break
else:
A[A.index(min(A))] = -A[A.index(min(A))]
break
if K == 0:
break
return sum(A) # Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = l3 = ListNode(0)
while l1 and l2:
if l1.val > l2.val:
l3.next = ListNode(l2.val)
l3 = l3.next
l2 = l2.next
else:
l3.next = ListNode(l1.val)
l3 = l3.next
l1 = l1.next
while l1:
l3.next = ListNode(l1.val)
l3 = l3.next
l1 = l1.next
while l2:
l3.next = ListNode(l2.val)
l3 = l3.next
l2 = l2.next
return dummy.next
# ------------------------------------------
# Slightly More Optimized
# ------------------------------------------
# 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, l1: ListNode, l2: ListNode) -> ListNode:
head = l3 = ListNode()
while l1 and l2:
if l1.val < l2.val:
l3.next = ListNode(l1.val)
l1 = l1.next
l3 = l3.next
else:
l3.next = ListNode(l2.val)
l2 = l2.next
l3 = l3.next
l3.next = l1 or l2
return head.next# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
A = [head]
while A[-1].next:
A.append(A[-1].next)
return A[len(A)//2]
# ------------------------------------------
# Solution using Slow and Fast Pointers
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slowPointer = head
fastPointer = head
while(fastPointer and fastPointer.next):
slowPointer = slowPointer.next
fastPointer = fastPointer.next.next
return slowPointer import math
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.stack = []
self.min = math.inf
def push(self, x: int) -> None:
self.x = x
self.stack.append(x)
if(x < self.min):
self.min = x
def pop(self) -> None:
t = self.stack.pop()
if(t==self.min and len(self.stack)):
self.min = min(self.stack)
elif(t==self.min and not len(self.stack)):
self.min = math.inf
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min
# ------------------------------------------
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()class Solution:
def minSubsequence(self, nums: List[int]) -> List[int]:
nums = sorted(nums)[::-1]
x = sum(nums)
s = 0
if len(nums) == 1:
return nums
for i in range(len(nums)+1):
s += nums[i]
if s > x-s:
return nums[0:i+1]class Solution:
def isMonotonic(self, A: List[int]) -> bool:
inc = True
dec = True
for i in range(0, len(A)-1):
if(A[i] > A[i+1]):
inc = False
if(A[i] < A[i+1]):
dec = False
return inc or dec
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
t = nums.count(0)
nzpos = 0
if(t==0):
return nums
for i in range(0, len(nums)):
if(nums[i]!=0):
nums[nzpos] = nums[i]
nzpos = nzpos+1
for i in range(len(nums)-t, len(nums)):
nums[i] = 0 from collections import deque
class Solution:
def numIslands(self, grid) -> int:
if not grid:
return 0
r = len(grid)
c = len(grid[0])
queue = deque()
islands = 0
for i in range(r):
for j in range(c):
if grid[i][j] == '1':
islands += 1
grid[i][j] = '0'
queue.append([i, j])
while queue:
el = queue.popleft()
rs = el[0]
cs = el[1]
if rs - 1 >= 0 and grid[rs-1][cs] == '1':
queue.append([rs-1, cs])
grid[rs-1][cs] = '0'
if rs + 1 < r and grid[rs+1][cs] == '1':
queue.append([rs+1, cs])
grid[rs+1][cs] = '0'
if cs - 1 >= 0 and grid[rs][cs-1] == '1':
queue.append([rs, cs-1])
grid[rs][cs-1] = '0'
if cs + 1 < c and grid[rs][cs+1] == '1':
queue.append([rs, cs+1])
grid[rs][cs+1] = '0'
return islandsclass RecentCounter:
def __init__(self):
self.q = collections.deque()
def ping(self, t: int) -> int:
self.q.append(t)
while self.q[0] < t-3000:
self.q.popleft()
return len(self.q)class Solution:
def hammingWeight(self, n: int) -> int:
return (bin(n).count('1'))# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution1:
def isPalindrome(self, head: ListNode) -> bool:
temp = head
stack = []
l = 0
while temp:
l += 1
temp = temp.next
temp = head
for i in range(0, l//2):
stack.append(temp.val)
temp = temp.next
if l % 2 != 0:
temp = temp.next
for i in range(0, l//2):
if temp.val == stack.pop():
continue
return False
return True
# ------------------------------------------
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution2:
def isPalindrome(self, head: ListNode) -> bool:
el = []
while head:
el.append(head.val)
head = head.next
for i in range(0, len(el)//2):
if not el[i] == el[-i-1]:
return False
return Trueclass Solution:
def isPalindrome(self, x: int) -> bool:
a = []
x = str(x)
x = list(x)
a = x[::-1]
if (str(a)==str(x)):
return True
else:
return False"""
This first solution uses the interval splitting method
This is achieved by using a dp table.
Time Complexity: O(n^1.5)
"""
class Solution1:
def numSquares(self, n) -> int:
if n <= 3:
return n
dp = [0 for _ in range(n+1)]
dp[1], dp[2], dp[3] = 1, 2, 3
for i in range(4, len(dp)):
dp[i] = i
j = 1
while j*j <= i:
dp[i] = min(dp[i], 1 + dp[i - j*j])
j += 1
return dp[-1]
"""
Lagrange's 4 square and 3 square theorem
Theorem: Every natural number can be represented as the sum of 4 integer squares.
N = a^2 + b^2 + c^2 + d^2
Theorem: A natural number can be represented as sum of 3 squares of integers.
N = a^2 + b^2 + c^2
if and only if the N is not of the form,
N = 4^a (8b + 7) -- (1)
LOGIC:
- if N is a perfect square, return 1
- if N is of form (1),
- keep dividing by 4
- divide by 8
- if rem == 7:
return 4
- check if N can be split into two perfect squares. If yes, return 2
- if all fails, return 3
"""
class Solution:
def numSquares(self, n: int) -> int:
if ceil(sqrt(n)) == floor(sqrt(n)):
return 1
while n % 4 == 0:
n /= 4
if n % 8 == 7:
return 4
j = 1
while j*j <= n:
if ceil(sqrt(n - j*j)) == floor(sqrt(n - j*j)):
return 2
j += 1
else:
return 3class Solution:
def stringShift(self, s: str, shift: List[List[int]]) -> str:
amount = 0
for i in range(len(shift)):
if(shift[i][0]==0):
amount += (-1)*shift[i][1]
else:
amount += 1*shift[i][1]
print(amount)
if amount == 0:
return s
elif amount < 0:
return s[(abs(amount)%len(s)):] + s[0:(abs(amount)%len(s))]
else:
return s[len(s)-(amount%len(s)):] + s[0:len(s)-(amount%len(s))]class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
carry = 0
for i in range(len(digits)-1, -1, -1):
if digits[i] != 9:
digits[i] += 1
break
else:
digits[i] = 0
if i == 0:
digits.insert(0, 1)
return digitsclass Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1:
return False
if n == 1:
return True
if sum(list(map(int, str(n)))) % 3 != 0:
return False
else:
while n > 1:
if n % 3 == 0:
n /= 3
else:
return False
if n != 1:
return False
else:
return True
# ------------------------------------------
# Alternate Approach
class Solution:
def isPowerOfThree(self, n: int) -> bool:
if n < 1:
return False
else:
return 1162261467 % n == 0# Classic Solution
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
if n == 1:
return True
if n == 0:
return False
while n % 2 == 0:
n = n / 2
if n == 1:
return True
else:
return False
# ------------------------------------------
# Solution Using Bit Manipulation
class Solution:
def isPowerOfTwo(self, n: int) -> bool:
return n > 0 and bin(n).count('1') == 1class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
people.sort(key = lambda x: (-x[0], x[1]))
rec = []
for p in people:
rec.insert(p[1], p)
return recfrom random import choices
class Solution:
def __init__(self, w: List[int]):
self.w = w
def pickIndex(self) -> int:
return choices(range(len(self.w)), self.w)[0]
# ------------------------------------------
# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
p = 0
while p < len(nums)-1:
if nums[p] == nums[p+1]:
nums.pop(p+1)
continue
p += 1
return len(nums)# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
pointer = ListNode(0)
pointer.next = head
tempnode = pointer
while tempnode.next != None:
if tempnode.next.val == val:
tempnode.next = tempnode.next.next
else:
tempnode = tempnode.next
return pointer.next# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
tail = head
length = 1
while tail.next:
length += 1
tail = tail.next
if(length==1):
return None
if(length==n):
return head.next
tempnode = head
for _ in range(0, length-n-1):
tempnode = tempnode.next
tempnode.next = tempnode.next.next
return head
# ------------------------------------------
# One Pass
# ------------------------------------------
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
dummy = fast = slow = ListNode()
dummy.next = head
if not head.next:
return None
for _ in range(n+1):
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return dummy.nextclass Solution:
def reorganizeString(self, S: str) -> str:
l = len(S)
A = []
for k, v in sorted((S.count(x), x) for x in set(S)):
if k > (l+1) / 2 :
return ""
A.extend(k * v)
# print(A)
ans = [None] * l
ans[::2], ans[1::2] = A[(l//2) : ], A[: (l//2)]
return ''.join(ans)class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
dic = {}
ans = []
for i in range(0, len(s)-9):
if s[i:i+10] not in dic:
dic[s[i:i+10]] = 1
else:
dic[s[i:i+10]] += 1
for k, v in dic.items():
if v>1:
ans.append(k)
return ansclass Solution:
def reverseBits(self, n: int) -> int:
s = str(bin(n))
s = s[2:]
s = '0'*(32-len(s)) + s
s = int(s[::-1], 2)
return sclass Solution:
def reverse(self, x: int) -> int:
x = str(x)
if (x[0] == '-'):
a = x[1:2147483648:1]
a = a[::-1]
if (int(a)>2147483648):
return 0
return int("-"+a)
else:
a = x[::-1]
if (int(a)>2147483647):
return 0
return int(a)# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
temp = head
prev = None
while(temp!=None):
next = temp.next
temp.next = prev
prev = temp
temp = next
return prevclass Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
head = 0
temp = ''
tail = len(s) - 1
while head < tail:
temp = s[head]
s[head] = s[tail]
s[tail] = temp
head += 1
tail -= 1class Solution:
def reverseParentheses(self, s: str) -> str:
stack = []
s = list(s)
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
continue
if s[i] == ')':
idx = stack.pop()
s[idx+1 : i] = s[idx+1 : i][::-1]
ans = ""
for i in s:
if i=="(" or i==")":
continue
ans += i
return ansclass Solution:
def romanToInt(self, s: str) -> int:
ans = 0
prev = ''
for i in range(len(s)):
if(s[i]=='M'):
if(prev=='C'):
ans += 800
prev = 'M'
continue
ans += 1000
prev = 'M'
continue
if(s[i]=='D'):
if(prev=='C'):
ans += 300
prev = 'D'
continue
ans += 500
prev = 'D'
continue
if(s[i]=='C'):
if(prev=='X'):
ans += 80
prev = 'C'
continue
ans += 100
prev = 'C'
continue
if(s[i]=='L'):
if(prev=='X'):
ans += 30
prev = 'L'
continue
ans += 50
prev = 'L'
continue
if(s[i]=='X'):
if(prev=='I'):
ans += 8
prev = 'X'
continue
ans += 10
prev = 'X'
continue
if(s[i]=='V'):
if(prev=='I'):
ans += 3
prev = 'V'
continue
ans += 5
prev = 'V'
continue
if(s[i]=='I'):
ans += 1
prev = 'I'
return ansclass Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
x = len(nums)
A = [0]*x
for i in range(0, x):
A[(i+k)%x] = nums[i]
for i in range(0, x):
nums[i] = A[i]class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
for x in zip(*matrix):
matrix.pop(0)
matrix.append(x[::-1])# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head: ListNode, k: int) -> ListNode:
if not head:
return None
if not k==0:
tail = head
length = 1
while(tail.next):
length += 1
tail = tail.next
k = k % length
tail.next = head
tempnode = head
for _ in range(0, length-k-1):
tempnode = tempnode.next
a = tempnode.next
tempnode.next = None
return a
return headclass Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
def binary(nums, low, high, target):
if low <= high:
mid = low + (high - low) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
return binary(nums, low, mid-1, target)
else:
return binary(nums, mid+1, high, target)
else:
return high+1
return binary(nums, 0, len(nums)-1, target)
# ------------------------------------------
# Iterative Binary Search
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
low = 0
high = len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid - 1
else:
low = mid + 1
else:
return high + 1class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
shuf = self.nums.copy()
self.shuf = shuf
def reset(self) -> List[int]:
"""
Resets the array to its original configuration and return it.
"""
self.shuf = self.nums.copy()
return self.shuf
def shuffle(self) -> List[int]:
"""
Returns a random shuffling of the array.
"""
x = len(self.nums)
for i in range(x):
j = random.randrange(i, x)
self.shuf[i], self.shuf[j] = self.shuf[j], self.shuf[i]
return self.shuf
# ------------------------------------------
# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.reset()
# param_2 = obj.shuffle()# from collections import deque
class Solution:
def simplifyPath(self, path: str) -> str:
if(len(path)==0 or path==None or path==''):
return '/'
p = path.split('/')
stack = []
for item in p:
if (item=='..'):
if(stack):
stack.pop()
continue
if item=='.' or len(item)==0:
pass
else:
stack.append(item)
return '/'+'/'.join(stack)
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return int(((sum(set(nums))*3) - sum(nums))/2)class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
ans = []
for i in set(nums):
if nums.count(i)==1:
ans.append(i)
if(len(ans)==2):
return ans
return ansfrom collections import Counter
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = Counter(nums)
nums.clear()
for v in range(3):
for i in range(n[v]):
nums.append(v)class Solution:
def balancedStringSplit(self, s: str) -> int:
c = 0
rc = 0
lc = 0
for i in range(len(s)):
if s[i] == 'R':
rc += 1
if s[i] == 'L':
lc += 1
if rc == lc:
c += 1
rc = 0
lc = 0
return cclass Solution:
def myAtoi(self, str: str) -> int:
if len(str)==0:
return 0
str = list(str.strip())
if len(str)==0:
return 0
if(str[0]=='-'):
s = -1
else:
s = 1
if str[0] in ['-', '+']:
del str[0]
i = 0
exp = 0
while(i < len(str) and str[i].isdigit()):
exp = exp*10 + ord(str[i]) - ord('0')
i += 1
return max(-2**31, min(exp*s, 2**31-1))class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
tasksDict = collections.Counter(tasks)
heap = []
c = 0
for k, v in tasksDict.items():
heappush(heap, (-v,k))
while heap:
i = 0
stack = []
while i<=n:
if len(heap)>0:
index, task = heappop(heap)
if index!=-1:
stack.append((index+1, task))
c += 1
if len(heap)==0 and len(stack)==0:
break
i += 1
for i in stack:
heappush(heap, i)
return c## Naive Solution that runs in O(n^2)
## Traverses the array, and finds the maximum left or right element.
## rainwater that can be stored in the column = min(left, right) - height[i]
class NaiveSolution:
def trap(self, height) -> int:
res = 0
n = len(height)
for i in range(1, n-1):
left = height[i]
for j in range(i):
left = max(left, height[j])
right = height[i]
for j in range(i+1, n):
right = max(right, height[j])
res += min(left, right) - height[i]
return res
# ------------------------------------------
## Optimized solution that runs in O(N)
## Stores the left and right maximum values in two dp arrays.
## Space Complexity - O(N)
class Solution:
def trap(self, height: List[int]) -> int:
if height == []:
return 0
n = len(height)
res = 0
left = [0 for _ in range(n)]
right = [0 for _ in range(n)]
left[0] = height[0]
right[n-1] = height[n-1]
for i in range(1, n):
left[i] = max(left[i-1], height[i])
for i in range(n-2, -1, -1):
right[i] = max(right[i+1], height[i])
for i in range(n):
res += min(left[i], right[i]) - height[i]
return res class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp = [0 for _ in range(len(triangle)+1)]
for r in triangle[::-1]:
for i in range(len(r)):
dp[i] = r[i] + min(dp[i], dp[i+1])
return dp[0]class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
costs = sorted(costs, key = lambda x: x[0] - x[1])
return sum(i[0] for i in costs[0:len(costs)//2]) + sum(j[1] for j in costs[len(costs)//2:len(costs)])class Solution:
def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
m = len(obstacleGrid)
n = len(obstacleGrid[0])
if obstacleGrid[0][0] == 1:
return 0
obstacleGrid[0][0] = 1
for i in range(1, m):
obstacleGrid[i][0] = int(obstacleGrid[i][0] == 0 and obstacleGrid[i-1][0] == 1)
for i in range(1, n):
obstacleGrid[0][i] = int(obstacleGrid[0][i] == 0 and obstacleGrid[0][i-1] == 1)
for i in range(1, m):
for j in range(1, n):
if obstacleGrid[i][j] == 0:
obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]
else:
obstacleGrid[i][j] = 0
return obstacleGrid[-1][-1] from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)class Solution:
def isPalindrome(self, s: str) -> bool:
s = ''.join(a for a in s if a.isalnum()).lower()
return s == s[::-1]class Solution:
def checkValidString(self, s: str) -> bool:
lb = 0
rb = 0
for i in s:
if(i=='(' or i=='*'):
lb += 1
else:
lb -= 1
if lb < 0:
return False
if(lb==0):
return True
for i in range(len(s)-1, -1, -1):
if(s[i]==')' or s[i]=='*'):
rb += 1
else:
rb -= 1
if rb < 0:
return False
return Trueclass Solution(object):
def robotSim(self, commands, obstacles):
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
x = y = di = 0
obstacleSet = set(map(tuple, obstacles))
ans = 0
for cmd in commands:
if cmd == -2: #left
di = (di - 1) % 4
elif cmd == -1: #right
di = (di + 1) % 4
else:
for k in range(cmd):
if (x+dx[di], y+dy[di]) not in obstacleSet:
x += dx[di]
y += dy[di]
ans = max(ans, x*x + y*y)
# ------------------------------------------
# Solution for https://leetcode.com/problems/two-sum/
# Language : Python3
# ------------------------------------------
# O(n^2) Solution
class Solution:
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if(nums[i]+nums[j]==target):
return i, j
# O(n) Solution
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict = { v:k for k, v in enumerate(nums) }
for i in range(len(nums)):
if target - nums[i] in dict and nums.index(target - nums[i]) != i:
return i, nums.index(target-nums[i])
# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# ------------------------------------------# -------------------------------------------
````
```
```
{% endtab %}
{% endtabs %}
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://bryan-guner.gitbook.io/my-docs/pythonnotes/interview-prep/interview-resources/by-example/leetcode.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.