Solution)class Solution: def twoSum(self, numbers: List[int], target: int) -> List[int]: # Two Pointers left, right = 0, len(numbers)-1 while left target: right -= 1 # If the sum is less than target else: left += 1 Problem: ..
[LeetCode]
Solution) class Solution: def convert(self, s: str, numRows: int) -> str: # Edge Case if numRows == 1: return s # Initialization res = {} for i in range(numRows): res[i] = [] # Add characters according to its row char, row = 0, 0 while char 0 and char < len(s): res[row].append(s[char]) row ..
Solution) class Solution: def reverseWords(self, s: str) -> str: # Initialization res = deque() cur = "" for i in range(len(s)): if s[i] == ' ': # If there is a word before current space if cur: res.appendleft(cur) cur = "" else: # Save characters until it becomes a word cur += s[i] # When it reaches the end of s if i == len(s)-1: res.appendleft(cur) return ' '.join(res) Problem: LeetCode Time C..
Solution) class Solution: def intToRoman(self, num: int) -> str: # Initialization dic = {1000:'M', 500:'D', 100:'C', 50:'L', 10:'X', 5:'V', 1:'I'} res = "" digit = 1 # while num > 0 while num: # Current digit integer's string variable cur = "" # Get a remainder, but with its zeros remainder = num % (digit*10) # Update num beforehand num -= remainder # If remainder = 4, 9, 40, 90, 400, 900 if rem..
Solution)class Solution: def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int: # Check if there exists a solution if sum(gas) < sum(cost): return -1 # Initialization total, start = 0, 0 for i in range(len(gas)): diff = gas[i] - cost[i] total += diff # If the current index cannot be a starting index if total < 0: # Try the next index start = i+1 total = 0 return start Problem: Lee..
Solution) class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: # Initialization res = [1] * len(nums) pre = 1 # Multiply prefixes for i in range(len(nums)): res[i] *= pre pre *= nums[i] post = 1 # Multiply postfixes for i in range(len(nums)-1, -1, -1): res[i] *= post post *= nums[i] return res Problem: LeetCode Reference: NeetCode Time Complexity: O(n) Space Complexity: O(1..
Solution)class RandomizedSet: # Have a dictionary and a list def __init__(self): self.dic = {} self.ls = [] def insert(self, val: int) -> bool: if val in self.dic: return False # After appending val, save the val's index in dic self.ls.append(val) self.dic[val] = len(self.ls)-1 return True def remove(self, val: int) -> bool: if val in self.dic: # Find the index of val saved in dic index = self.d..
Solution)class Solution: def hIndex(self, citations: List[int]) -> int: # Initialization space = [] for i in range(len(citations)): # Fill empty space if not space: if citations[i] > 0: space.append(citations[i]) else: # If cur elem is bigger than cur h-index if citations[i] > len(space): space.append(citations[i]) # If the smallest elem is smaller than updated h-index if min(space) < len(space)..
Solution)class Solution: def jump(self, nums: List[int]) -> int: # Initialization step, l, r = 0, 0, 0 # while the end of nums is not reached while r < len(nums)-1: farthest = 0 # Find the farthest index that can be jumped from each window for i in range(l, r+1): farthest = max(farthest, nums[i]+i) # Slide window l = r+1 r = farthest # Increment each jump step += 1 return step Problem: LeetCode ..
Solution)class Solution: def canJump(self, nums: List[int]) -> bool: # Initialization goal = len(nums) - 1 # Check if current goal can be reached and update goal for i in range(len(nums)-2, -1, -1): if nums[i] + i >= goal: goal = i # Check if the end can be reached return True if goal == 0 else False Problem: LeetCode Reference: NeetCode Time Complexity: O(n) Space Complexity: O(1)Explanation)I ..
