Sandbox

Problem Solution DFS problem Each row = One city Don't need to look at one more than once -- keep track of them in 'seen' dictionary. Time Complexity O(n) (n = num of cities) Space Complexity O(N) class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: if not isConnected: return 0 rows = len(isConnected) seen = set() count = 0 def dfs(r): for index, val in enumerate(isConne..

Problem Solution First element of preorder will always be the root of the tree. Inorder traversal searches left tree and then right tree, so we can find the root element in the list and divide the list up into left and right side(trees). Now we can build those trees. Repeat this process with the root of left tree, which is the second element in the preorder list. Then use the third element as th..

Problem Iterative Solution Things to do: 1. visit every node 2. copy all elements in neighbor Time Complexity O(N+M), where N is the number of nodes and M is the number of edges Space Complexity O(N) """ # Definition for a Node. class Node(object): def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """ class Solution(object):..

Problem Solution Time Complexity O(N) Space Complexity O(1) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ # If p and q are on the same subtree of the cu..

Problem Solution The nodes need to know their parent node when they connect to the next node. But since there is no parent value in Node class, the code needs to connect nodes by being on the previous level and updating child nodes. Time Complexity O(N) Space Complexity O(1) """ # Definition for a Node. class Node(object): def __init__(self, val=0, left=None, right=None, next=None): self.val = v..

Problem Recursive Solution This problem is somewhat like BFS, except that we need to examine every node on the same level before expanding. Since the first element of a level is a left child of some node, first traverse down the left subtrees and store the values. Then examine the right nodes while coming back up. After coming back to the root, go to the right subtree and examine the left nodes ..

Problem Recursive Solution Time Complexity O(N) Space Complexity O(N) worst case, O(logN) average case (recursive space of tree height) # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype:..

Problem Recursive Solution Use inorder traversal to go through the BST. If the value of current node is smaller than or equal to the value of previous node, the BST is not valid. When using recursion, verify the left side of the tree first. After reaching the very left node, move up to the root while checking the right nodes of each node on the way. Then check the right side of the tree. I tried..

Problem Solution Ignore the random pointers for now. We need a way to make the next property point to a new node. First, create new nodes with original values in the linked list and plug them after the node of the original value. Then we can work through the interweaved list and take care of random pointers for the new nodes. Lastly, break the next links so that old nodes point to old nodes and ..

Problem Solution My initial approach was to compare the head nodes from each list, put the smallest onto the result linked list, and proceed the pointer that was on the smallest node. The time complexity for this approach would be O(kN) where k is the number of elements in lists and N is the number of nodes in the final linked list. I did not find a clean way to implement this. Solution using me..