Scribbling

Solution below is not very efficient, however, is seemingly intuitive and easy to understand. The core idea is to reuse solution for "57. Insert Interval". (Link: https://leetcode.com/problems/insert-interval/) The problem is about inserting an interval such that intervals are sorted in ascending order while not having any overlapping intervals. We can use exactly the same idea to implement "add..

class Solution: def longestStrChain(self, words: List[str]) -> int: ret = 1 # First, we sort words by its length # By this way, we only need to check the previous length (or current length - 1) # That is, if the length(word) is k, # We only need to check words that have length of k - 1. words.sort(key=lambda word: len(word)) # dp[word]: max chain length until the word dp = {} for word in words: ..

class Solution: def equationsPossible(self, equations: List[str]) -> bool: # Define parents list for find/union parent operations parents = [i for i in range(26)] # find parent operation def find_parent(node): if node == parents[node]: return node parents[node] = find_parent(parents[node]) return parents[node] # union parent operation def union_parent(node1, node2): node1 = find_parent(node1) no..

All we have to do is traversing every node by dfs and checking whether current node's structure is already seen or not. Then, we need to come up with a way to 'represent' a tree's structure. Here, we use a string to represent the tree structure. --> str(node.val) + (left tree structure) + (right tree structure) If it is a new string, we add to our dictionary (self.dp). If it is a already seen st..

First, we look through all the transactions and check how much money(or debt) each one has. Array self.money is storing that information, and we excluded the ones who don't have any money or debt. Next, let's define "helper(self, indexs)" as our goal function. It will return 'min # of transactions needed'. Here, we take indexes (tuple type) as the parameter of the function so that we can easily ..

DP Solution Time complexity: O(M*N**2) class Solution: def splitArray(self, nums: List[int], m: int) -> int: self.nums = nums self.table = [0] * (len(nums)+1) summed = 0 for i in range(len(nums)): summed += nums[i] self.table[i+1] = summed self.dp = {} return self.helper(0, len(nums)-1, m) def helper(self, i, j, m): if m == 1: return self.table[j+1] - self.table[i] if i == j: return self.nums[i]..

Several solutions and short analysis of each one. 1. List + Binary Search The most straightforward solution, however, time complexity is O(N**2). class Solution: def countSmaller(self, nums: List[int]) -> List[int]: from bisect import insort, bisect_left arr = [] count = [] for i in range(len(nums) - 1, -1, -1): num = nums[i] idx = bisect_left(arr, num) count.append(idx) insort(arr, num) return ..

Key idea: one's number of candies is affected by all the left and right neighbors. So we iterate the list twice, forward and backward. class Solution: def candy(self, ratings: List[int]) -> int: n = len(ratings) candies = [1] * n # forward pass for i in range(1, n): if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1 # backward pass for i in range(n-2, -1, -1): if ratings[i] > ratings[i+..

# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]: self.ret = [] self.dfs(root) return self.ret def dfs(self, node): if node.left and node.right: h = max(self.dfs(node.left), self.dfs(node.right)) + 1 e..

O(N) Time complexity, O(1) Memory Solution using Recursion # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def sortedListToBST(self, he..