Skip to content

Instantly share code, notes, and snippets.

@juniorkrvl
Last active September 27, 2022 15:27
Show Gist options
  • Save juniorkrvl/2528f4e532dccaea8e74b51038546370 to your computer and use it in GitHub Desktop.
Save juniorkrvl/2528f4e532dccaea8e74b51038546370 to your computer and use it in GitHub Desktop.
Grind 75 - Week 1
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
# Use DICTIONARY as a memory to keep track of the difference between the
# current number and the target, the store the index in it.
diff = {}
for idx, num in enumerate(nums):
if diff.get(num) != None:
return[diff.get(num), idx]
if not diff.get(target-num):
diff[target-num] = idx
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
# From the root node, if the have one node to the right and one to the left, it means that
# the current node is the LCA
# If the current node is not equal to q or p and we have both nodes either to the right or to the
# left of the tree we go down one level to where both nodes are, and then repeat the process
# If the node is equal to one of the target nodes, then there is no other node that can be the LCA
# because LCA must contain both nodes
# Complexity
# Time (n*h) we traverse all the nodes to find a node times the height of the tree
# Space (n) for each call we stack in memory to find a node
if root == q or root == p:
return root
if self.findNode(root.left, p) and self.findNode(root.left, q):
return self.lowestCommonAncestor(root.left, p, q)
if self.findNode(root.right, p) and self.findNode(root.right, q):
return self.lowestCommonAncestor(root.right, p, q)
return root
def findNode(self, root: 'TreeNode', target: 'TreeNode'):
if root is None:
return None
if root == target:
return root
left = self.findNode(root.left, target)
right = self.findNode(root.right, target)
return left or right
# 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 isBalanced(self, root: Optional[TreeNode]) -> bool:
if not root:
return True
# if not root.left and not root.right:
# return True
left = self.height(root.left)
right = self.height(root.right)
if left == -1 or right == -1:
return False
return abs(left-right) < 2
def height(self, root: Optional[TreeNode]):
if root is None:
return 0
left = self.height(root.left)
right = self.height(root.right)
if abs(left-right) > 1:
return -1
if left == -1 or right == -1:
return -1
return max(left, right) + 1
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# We got TWO POINTER one going twice as fast that the other.
# We traverse the whole linked list. If both of them collide, it means that there is a cycle in the list
# Otherwise the while loop will go until the end and then there won't be a cycle
# Complexity
# Time O(n) we need to traverse the whole list until either the list is finished
# or we find the cycle
# Space O(1) we have constant space for the pointers. There is no variable growing together with the input
pointer = head
fasterpointer = head
while fasterpointer:
pointer = pointer.next
if fasterpointer.next and fasterpointer.next.next:
fasterpointer = fasterpointer.next.next
else:
break
if pointer == fasterpointer:
return True
return False
class MyQueue:
def __init__(self):
self.stack = []
def push(self, x: int) -> None:
self.stack.insert(0,x)
def pop(self) -> int:
return self.stack.pop()
def peek(self) -> int:
return self.stack[-1]
def empty(self) -> bool:
return len(self.stack) == 0
# 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()
class Solution:
def isValid(self, s: str) -> bool:
# Use a STACK to enqueue the opening brackets
# Then as soon we see a closing bracket, it needs to be
# the correct one, otherwise we can return False
# If at the end we still have opening brackets in the stack, it means
# we didnt find closing brackets to cancel them.
# Complexity
# Time O(n) we travers the string and stack open brackets
# Space O(n) our stack of opening brackets grow as our input grows
dict = {
'(': ')',
'[': ']',
'{': '}',
}
stack = []
for idx in range(len(s)):
if s[idx] in dict:
stack.append(s[idx])
else:
if len(stack) == 0:
return False
lastOpen = stack.pop()
if dict[lastOpen] != s[idx]:
return False
return len(stack) == 0
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# Tricky because it uses the reference of the object in memory, pay attention to that!
# We need to create a HEAD list, and then copy it to another variable TAIL so we can navigate
# in the subsequent nodes without changing the head.
# Complexity
# The solution traverses both linked lists, so the time complexity is O(n+m)
# The space complexity is O(1) since we are not creating new data in memory
head = ListNode()
tail = head
while list1 and list2:
if list1.val <= list2.val:
#print(list1.val)
tail.next = ListNode(list1.val, None)
list1 = list1.next
else:
#print(list2.val)
tail.next = ListNode(list2.val, None)
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
return head.next
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Use GREEDY algorithm to get the best price as we traverse the array
# We compare each day, if the current day is better than what we picked, we change
# Then we compare the (current price - how much we bought) and it needs to increase profit
# In the end we will have the highest profit.
# Complexity
# Time O(n) we traverse the array once
# Space O(1) we don't have any variable that grows with input
if len(prices) == 1:
return 0
buy = prices[0]
profit = 0
for idx in range(1, len(prices)):
if prices[idx] < buy:
buy = prices[idx]
if prices[idx] - buy > profit:
profit = prices[idx]-buy
return profit
class Solution:
def isPalindrome(self, s: str) -> bool:
# First format the string to remove non alpha numeric characters
# This results in an array with all lower case letters
formatted = [val.lower() for val in s if val.isalnum()]
# create TWO POINTERS one from the start to end and vice versa
# each pointer needs to point to a letteer from start and end respectively
# if at any moment the pointers point to a different character, than it means
# the text is not a palindrome
# Complexity
# Time O(n+a/2) = O(n) we traverse the string to transform it,
# then we traverse the string only half way with the pointers
# Space O(1) we don't have any variable growing with the input,
# but if you consider the formatted variable that would be O(n)
left = 0
right = len(formatted)-1
while left < right:
if formatted[left] == formatted[right]:
left +=1
right -=1
else:
return False
return True
# 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: Optional[TreeNode]) -> Optional[TreeNode]:
return self.invertTreeInterative(root)
def invertTreeRecursive(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# Recursive function, divide the problem in subproblems
# The logic is the same for each level we traverse in the tree
# So what we need to do is consider we have only a root and two children
# then we propagate the logic recursively
# Complexity
# Time O(n) we will traverse all nodes in the tree
# Space O(n) we will add to memory the call stack for each node
if not root:
return None
temp = self.invertTreeRecursive(root.left)
root.left = self.invertTreeRecursive(root.right)
root.right = temp
return root
def invertTreeInterative(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# The interactive mode we use the Breath First Search to navigate in the three
# Each iteration we push the nodes left and right to the queue and then get the
# First element with pop(0) rinse and repeat
# Complexity
# Time O(n) we will traverse all nodes in the tree
# Space O(n) we will add elements to the stack two at a time
stack = []
stack.append(root)
while len(stack) > 0:
node = stack.pop(0)
if not node:
continue
temp = node.left
node.left = node.right
node.right = temp
stack.append(node.left)
stack.append(node.right)
return root
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
# Use Hashmap to store the number of letters of first word
# Use variable to keep track of the current sum of the letters
# Then use the same hashmap to subtract the second word
# If the second word has a specific letter more than the first letter then we can return False
# because it is not an anagram
# In the end we need to check the sum variable to make sure it is 0,
# or all characters cancelled each other
# Complexity
# Time O(n+m) we traverse two strings to count its letters
# Space O(n) we use the dictionary to count the amount of letters
dict = {}
sum = 0
for word in s:
if word not in dict:
dict[word] = 0
dict[word]+=1
sum += 1
for word in t:
if word in dict and dict[word] > 0:
dict[word]-=1
sum -= 1
else:
return False
return sum == 0
class Solution:
def search(self, nums: List[int], target: int) -> int:
# Because we have a sorted list, we can use TWO POINTERS
# one starting from beginning and other from the end
# we check the middle point and adjust the left and right halving the set by each time
# If we can't find the item just return -1
# Complexity
# Time O(logn) we only check the middle point for each iteration
# Space O(1) constant time because we don't have any variable that increase with input
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid+1
else:
right = mid-1
return -1
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
# Use graph traversal from the first item (DFS)
# check if the current element has the same starting color,
# if so, change the color and enqueue the subjacent elements
# if the indexes are out of bound, just continue to the next
# I marked the element as visited so we dont enqueue it again
# Complexity
# Time O(n) we traverse a subset of elements from the matrix
# Space O(n) we keep stacking the next elements
# TODO: improve performance by only queueing the elegible elements instead of all of them.
startingColor = image[sr][sc]
stack = [(sr,sc)]
visited = {}
while len(stack) > 0:
sr, sc = stack.pop()
if sr < 0 or sr > len(image) - 1:
continue
if sc < 0 or sc > len(image[sr]) - 1:
continue
if image[sr][sc] == startingColor:
image[sr][sc] = color
visited[(sr,sc)] = 1
else:
continue
if (sr-1,sc) not in visited:
stack.append((sr-1,sc))
if (sr+1,sc) not in visited:
stack.append((sr+1,sc))
if (sr,sc-1) not in visited:
stack.append((sr,sc-1))
if (sr,sc+1) not in visited:
stack.append((sr,sc+1))
return image
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment