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 Use deque (double-ended queue) to store indices and a result array to keep track of the maximum integers for each window. When pushing an index into the deque, pop every index that contains smaller integer than the current integer. If current integer is less than the integer held by the index at the head, just append current index to the deque. class Solution(object): def maxSli..

Problem Solution class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ left = 0 right = len(nums)-1 while left nums[mid]: left = mid + 1 return -1