Sandbox

Problem Solution If next interval's start point is larger than current interval's end point, just add the next interval to the result array. If not, see if current interval's end point should be replaced. class Solution: def merge(self, intervals: List[List[int]]) -> List[List[int]]: intervals.sort(key = lambda x:x[0]) result = [] for interval in intervals: if not result or result[-1][1] < inter..

Problem Solution class Solution: def maxProfit(self, prices: List[int]) -> int: low = -1 profit = 0 for price in prices: if price profit: if low < 0: low = price else: profit = price - low return profit Time Complexity O(N) Space Complexity O(1)

Problem Solution class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # z keeps track of latest 0 encountered, i keeps track first of nonzero after z z = 0 for i in range(len(nums)): if nums[i] != 0: nums[i], nums[z] = nums[z], nums[i] z += 1 # next element is always zero since i checks for nonzero elements Time Complexity O..

Problem Solution class Solution: def searchRange(self, nums: List[int], target: int) -> List[int]: # find target with binary search, # then expand until the number changes left = 0 right = len(nums)-1 start = -1 end = -1 while left

Problem Reverse the whole array. Divide the array by k index, and reverse the two subarrays. ex) k=3 1 2 3 4 5 6 7 -> 7 6 5 4 3 2 1 -> 7 6 5 | 4 3 2 1 -> 5 6 7 | 1 2 3 4 Solution Time Complexity O(N) Space Complexity O(1) class Solution: def rotate(self, nums: List[int], k: int) -> None: """ Do not return anything, modify nums in-place instead. """ k %= len(nums) nums = self.reverse(nums, 0, len..

Problem Solution Look at the first number on the first row. Then perform binary search (time complexity = log N) to find that element in the rest of the matrix. If the loop ended before currRow is updated to the row length of matrix, the code did not find the number in the rest of the rows. Move onto the next number in the first row and repeat. Time Complexity O(M+N) maximum Space Complexity O(1..

Problem Solution Time complexity constraint is O(log N) -> perform binary search First determine the how the array rotated, then do the search """ No rotated: 1 2 3 4 5 6 7 mid left rotated: pivot at the left side of the origin sorted array, A[mid] >= A[left] 3 4 5 6 7 1 2 mid search in A[left] ~ A [mid] if A[left]

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):..