leetcode
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def asteroidCollision(self, asteroids: List[int]) -> List[int]: | |
| if len(asteroids) <= 1: | |
| return asteroids | |
| ans = [asteroids[0]] | |
| i = 1 | |
| while i < len(asteroids): | |
| if len(ans) > 0 and ans[-1] > 0 and asteroids[i] < 0: | |
| if ans[-1] == -asteroids[i]: | |
| ans.pop(-1) | |
| i = i + 1 | |
| elif -asteroids[i] > ans[-1]: | |
| ans.pop(-1) | |
| else: | |
| i = i + 1 | |
| else: | |
| ans.append(asteroids[i]) | |
| i = i + 1 | |
| return ans |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def combinationSum(self, nums: List[int], target: int) -> List[List[int]]: | |
| ans = [] | |
| nums.sort() | |
| for i in range(len(nums)): | |
| n = nums[i] | |
| new_target = target - n | |
| if new_target == 0: | |
| ans.append([n]) | |
| elif new_target > 0: | |
| lst = self.combinationSum(nums[i:], target -n) | |
| if len(lst) > 0: | |
| print(lst) | |
| for i in range(len(lst)): | |
| l = lst[i] | |
| l.append(n) | |
| ans.append(l) | |
| return ans |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def numIslands(self, grid: List[List[str]]) -> int: | |
| count = 0 | |
| m = len(grid) | |
| n = len(grid[0]) | |
| def dfs(i, j): | |
| if i < 0 or i >= m: | |
| return | |
| if j < 0 or j >= n: | |
| return | |
| if grid[i][j] == "1": | |
| # print((i,j)) | |
| grid[i][j] = "0" | |
| dfs(i+1,j) | |
| dfs(i-1,j) | |
| dfs(i,j+1) | |
| dfs(i,j-1) | |
| for i in range(m): | |
| for j in range(n): | |
| if grid[i][j] == "1": | |
| dfs(i,j) | |
| count = count + 1 | |
| return count | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import heapq | |
| class MedianFinder: | |
| def __init__(self): | |
| self.smaller = [] | |
| self.greater = [] | |
| heapq.heapify(self.smaller) | |
| heapq.heapify(self.greater) | |
| def addNum(self, num: int) -> None: | |
| # print(f"Adding num: {num}") | |
| if self.smaller and num <= -self.smaller[0]: | |
| heapq.heappush(self.smaller,-num) | |
| if len(self.smaller) > len(self.greater) + 1: | |
| n = heapq.heappop(self.smaller) | |
| heapq.heappush(self.greater,-n) | |
| else: | |
| heapq.heappush(self.greater,num) | |
| if len(self.smaller) < len(self.greater): | |
| n = heapq.heappop(self.greater) | |
| heapq.heappush(self.smaller,-n) | |
| def findMedian(self) -> float: | |
| if len(self.smaller) == len(self.greater): | |
| return (self.greater[0] -self.smaller[0])/2.0 | |
| else: | |
| return -self.smaller[0] | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class PrefixTree: | |
| def __init__(self): | |
| self.data = {} | |
| def insert(self, word: str) -> None: | |
| if len(word) == 0: | |
| self.data[' '] = True | |
| return | |
| child = self.data.get(word[0],None) | |
| if child == None: | |
| child = PrefixTree() | |
| self.data[word[0]] = child | |
| child.insert(word[1:]) | |
| def search(self, word: str) -> bool: | |
| if len(word) == 0: | |
| if ' ' in self.data: | |
| return True | |
| else: | |
| return False | |
| if word[0] in self.data: | |
| return self.data[word[0]].search(word[1:]) | |
| else: | |
| return False | |
| def startsWith(self, prefix: str) -> bool: | |
| if len(prefix) == 0: | |
| return True | |
| if prefix[0] in self.data: | |
| return self.data[prefix[0]].startsWith(prefix[1:]) | |
| else: | |
| return False | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class MyQueue: | |
| def __init__(self): | |
| self.latest_last = [] | |
| self.latest_first = [] | |
| def push(self, x: int) -> None: | |
| if self.latest_last: | |
| self.latest_last.append(x) | |
| else: | |
| while self.latest_first: | |
| self.latest_last.append(self.latest_first.pop()) | |
| self.latest_last.append(x) | |
| def pop(self) -> int: | |
| if self.latest_first: | |
| return self.latest_first.pop() | |
| else: | |
| while self.latest_last: | |
| self.latest_first.append(self.latest_last.pop()) | |
| return self.latest_first.pop() | |
| def peek(self) -> int: | |
| if self.latest_first: | |
| return self.latest_first[-1] | |
| else: | |
| while self.latest_last: | |
| self.latest_first.append(self.latest_last.pop()) | |
| return self.latest_first[-1] | |
| def empty(self) -> bool: | |
| return len(self.latest_first) == 0 and len(self.latest_last) == 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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import heapq | |
| class KthLargest: | |
| def __init__(self, k: int, nums: List[int]): | |
| self.data = [] | |
| self.capacity = k | |
| heapq.heapify(self.data) | |
| for n in nums: | |
| self.add(n) | |
| def add(self, val: int) -> int: | |
| if len(self.data) < self.capacity: | |
| heapq.heappush(self.data, val) | |
| return None | |
| else: | |
| heapq.heappush(self.data, val) | |
| heapq.heappop(self.data) | |
| return self.data[0] | |
| # Your KthLargest object will be instantiated and called as such: | |
| # obj = KthLargest(k, nums) | |
| # param_1 = obj.add(val) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node: | |
| def __init__(self, key, value): | |
| self.key = key | |
| self.value = value | |
| self.freq = 1 | |
| self.prev = None | |
| self.next = None | |
| class LinkedList: | |
| def __init__(self): | |
| self.head = Node(0,0) | |
| self.tail = Node(0,0) | |
| self.head.next = self.tail | |
| self.tail.prev = self.head | |
| self.curr = 0 | |
| def insert(self, n): | |
| tmp_prev = self.tail.prev | |
| self.tail.prev = n | |
| n.next = self.tail | |
| n.prev = tmp_prev | |
| tmp_prev.next = n | |
| self.curr = self.curr + 1 | |
| def remove(self, n): | |
| tmp_prev = n.prev | |
| tmp_next = n.next | |
| tmp_prev.next = tmp_next | |
| tmp_next.prev = tmp_prev | |
| self.curr = self.curr -1 | |
| def length(self): | |
| return self.curr | |
| def pop(self): | |
| if self.curr > 0: | |
| tmp = self.head.next | |
| self.head.next = tmp.next | |
| self.head.next.prev = self.head | |
| self.curr = self.curr -1 | |
| return tmp | |
| else: | |
| return None | |
| class LFUCache: | |
| def __init__(self, capacity: int): | |
| self.k_v = {} | |
| self.f_k = {} | |
| self.capacity = capacity | |
| self.curr = 0 | |
| self.min_freq = 1 | |
| def get(self, key: int) -> int: | |
| if key in self.k_v: | |
| n = self.k_v[key] | |
| f = n.freq | |
| self.f_k[f].remove(n) | |
| if self.f_k[f].length() == 0: | |
| self.min_freq = f + 1 | |
| n.freq = n.freq + 1 | |
| if f+1 not in self.f_k: | |
| self.f_k[f+1] = LinkedList() | |
| self.f_k[f+1].insert(n) | |
| return n.value | |
| else: | |
| return -1 | |
| def put(self, key: int, value: int) -> None: | |
| if key in self.k_v: | |
| n = self.k_v[key] | |
| f = n.freq | |
| self.f_k[f].remove(n) | |
| n.freq = n.freq + 1 | |
| if n.freq not in self.f_k: | |
| self.f_k[n.freq] = LinkedList() | |
| self.f_k[n.freq].insert(n) | |
| n.value = value | |
| else: | |
| # get the smallest freq key | |
| # remove the smallest freq key | |
| # add key and value | |
| if self.curr < self.capacity: | |
| self.curr = self.curr + 1 | |
| else: | |
| n = self.f_k[self.min_freq].pop() | |
| # print(self.k_v) | |
| # print(n.key) | |
| # print(self.k_v[n.key]) | |
| del self.k_v[n.key] | |
| n = Node(key,value) | |
| self.k_v[key] = n | |
| if n.freq not in self.f_k: | |
| self.f_k[n.freq] = LinkedList() | |
| self.f_k[n.freq].insert(n) | |
| self.min_freq = n.freq | |
| # Your LFUCache object will be instantiated and called as such: | |
| # obj = LFUCache(capacity) | |
| # param_1 = obj.get(key) | |
| # obj.put(key,value) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node: | |
| def __init__(self, k, v): | |
| self.key = k | |
| self.value = v | |
| self.prev, self.next = None, None | |
| class LRUCache: | |
| def __init__(self, capacity: int): | |
| self.data = {} | |
| self.head = Node(0,0) | |
| self.tail = Node(0,0) | |
| self.capacity = capacity | |
| self.curr = 0 | |
| self.head.next = self.tail | |
| self.tail.prev = self.head | |
| def insert(self, n): | |
| temp = self.tail.prev | |
| self.tail.prev = n | |
| n.next = self.tail | |
| n.prev = temp | |
| temp.next = n | |
| def remove(self, n): | |
| tmp_prev = n.prev | |
| tmp_next = n.next | |
| tmp_prev.next, tmp_next.prev = tmp_next, tmp_prev | |
| def get(self, key: int) -> int: | |
| # print(self.data) | |
| if key in self.data: | |
| self.remove(self.data[key]) | |
| self.insert(self.data[key]) | |
| return self.data[key].value | |
| else: | |
| return -1 | |
| def put(self, key: int, value: int) -> None: | |
| if key in self.data: | |
| self.data[key].value = value | |
| self.remove(self.data[key]) | |
| self.insert(self.data[key]) | |
| else: | |
| n = Node(key,value) | |
| self.insert(n) | |
| self.data[key] = n | |
| if self.curr < self.capacity: | |
| self.curr = self.curr + 1 | |
| else: | |
| lru = self.head.next.key | |
| self.remove(self.data[lru]) | |
| del self.data[lru] | |
| # Your LRUCache object will be instantiated and called as such: | |
| # obj = LRUCache(capacity) | |
| # param_1 = obj.get(key) | |
| # obj.put(key,value) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def maxAreaOfIsland(self, grid: List[List[int]]) -> int: | |
| ans = 0 | |
| m = len(grid) | |
| n = len(grid[0]) | |
| def dfs(i,j): | |
| if i < 0 or i >= m: | |
| return 0 | |
| if j < 0 or j >= n: | |
| return 0 | |
| if grid[i][j] == 0: | |
| return 0 | |
| else: | |
| grid[i][j] = 0 | |
| return dfs(i+1,j) + dfs(i-1,j) + dfs(i,j+1) + dfs(i,j-1) + 1 | |
| for i in range(m): | |
| for j in range(n): | |
| if grid[i][j] == 1: | |
| ans = max(ans, dfs(i,j)) | |
| return ans |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def minWindow(self, s: str, t: str) -> str: | |
| if len(t) > len(s): | |
| return "" | |
| t_count = {} | |
| for c in t: | |
| t_count[c] = t_count.get(c,0) + 1 | |
| left = 0 | |
| right = 0 | |
| count = {} | |
| required = len(t_count) | |
| ans = float('inf'), None, None | |
| formed = 0 | |
| while right < len(s): | |
| c_right = s[right] | |
| count[c_right] = count.get(c_right,0) + 1 | |
| if c_right in t_count and count[c_right] == t_count[c_right]: | |
| formed = formed + 1 | |
| while left <= right and formed == required: | |
| c_left = s[left] | |
| if right - left + 1 < ans[0]: | |
| ans = (right - left + 1, left, right) | |
| count[c_left] -= 1 | |
| if c_left in t_count and count[c_left] < t_count[c_left]: | |
| formed = formed -1 | |
| left = left + 1 | |
| right = right + 1 | |
| return "" if ans[0] == float('inf') else s[ans[1]:ans[2]+1] | |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: | |
| m = len(heights) | |
| n = len(heights[0]) | |
| visited = set() | |
| def dfs(i,j,prev): | |
| if i < 0: | |
| return | |
| if j < 0: | |
| return | |
| if i >= m: | |
| return | |
| if j >= n: | |
| return | |
| curr = heights[i][j] | |
| if curr >= prev and (i,j) not in visited: | |
| visited.add((i,j)) | |
| dfs(i+1,j,curr) | |
| dfs(i,j+1,curr) | |
| dfs(i-1,j,curr) | |
| dfs(i,j-1,curr) | |
| for i in range(0,m): | |
| dfs(i,0,heights[i][0]) | |
| for j in range(0,n): | |
| dfs(0,j,heights[0][j]) | |
| pacific = visited | |
| visited = set() | |
| for i in range(0,m): | |
| dfs(i,n-1,heights[i][n-1]) | |
| for j in range(0,n): | |
| dfs(m-1,j,heights[m-1][j]) | |
| common = pacific & visited | |
| return [list(d) for d in common] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: | |
| row, col = 0, len(matrix[0]) - 1 | |
| while row < len(matrix) and col >= 0: | |
| if target == matrix[row][col]: | |
| return True | |
| elif target < matrix[row][col]: | |
| col = col - 1 | |
| else: | |
| row = row + 1 | |
| return False |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution: | |
| def exist(self, board: List[List[str]], word: str) -> bool: | |
| visited = set() | |
| rows = len(board) | |
| cols = len(board[0]) | |
| def dfs(r,c,i): | |
| if i == len(word): | |
| return True | |
| if r < 0 or r >= rows or c < 0 or c >= cols or (r,c) in visited or board[r][c] != word[i]: | |
| return False | |
| else: | |
| visited.add((r,c)) | |
| res = (dfs(r+1,c,i+1) or dfs(r,c+1,i+1) or dfs(r-1,c,i+1) or dfs(r,c-1,i+1)) | |
| visited.remove((r,c)) | |
| return res | |
| for i in range(rows): | |
| for j in range(cols): | |
| if dfs(i,j,0): | |
| return True | |
| return False |