Week 1 - Practicing
| 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 |