liyunrui

class Solution:
    def areSentencesSimilar(self, words1: List[str], words2: List[str], pairs: List[List[str]]) -> bool:
        """
        Problem formulation:
            1.We take each word as a node and pairs as edge.
            2.Because it's not transitive and symmetric, so it's a undirected graph with lots of connected component. Each component has at least two nodes and one edges or with maximum length 2.
            
        Thought Process:
            1. We build the graph.
            2. And to see if there's a path from word1 to words2 for all the words. If yes, retur True. One of them fails, return False.

liyunrui

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        """
        Thought prcoess:
            1. we are trying to add the edge [u,v] and want to know if this operation will form a cyle
            2. we progressively build graph(adjacency list representation)
                -we do dfs on the existing graph to see if we can reach v from u. If we can, then adding [u,v] will form a cycle.
                -Otherwise, we add this edge into graph
                
        Time complexity analysis:

liyunrui

class UnionFindSet:
    def __init__(self, n):
        self._parents = [node for node in range(n)]
        self._ranks = [1 for _ in range(n)]
    
    def find(self, u):
        while u != self._parents[u]:
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u

liyunrui

class UnionFindSet:
    def __init__(self, n):
        #Initially, all elements are single element subsets.
        self._parents = [node for node in range(n)]
        # it's like height of tree but it's not always equal to height because path compression technique.
        self._ranks = [1 for i in range(n)]
    
    def find(self, u):
        """
        The find method with path compression, return root of node x, whih can be found by following the chain that begins at x.

liyunrui

class UnionFindSet:
    def __init__(self, n):
        #Initially, all elements are single element subsets.
        self._parents = [node for node in range(n)]
        # it's like height of tree but it's not always equal to height because path compression technique.
        self._ranks = [1 for i in range(n)]
    
    def find(self, u):
        """
        The find method with path compression, return root of node u.

liyunrui

class NumArray:

    def __init__(self, nums: List[int]):
        self._prefix_sum = [0 for _ in range(len(nums))]
        if len(nums) != 0:
            self._prefix_sum[0] = nums[0]
        for i in range(1, len(nums)):
             self._prefix_sum[i] =  self._prefix_sum[i-1] + nums[i]
        
    def sumRange(self, i: int, j: int) -> int:

liyunrui

class NumArray:
    """
    Problem Clarification:
        1. Can ask if update and sumRange function is distributed evenly. If not, we can use naive method.
        
    Problem Pormulation:
        We need to have two functionality of this class:
            1. update a val of array given index.
            2. compute range sum queries.
    

liyunrui

class BinaryIndexTree:
    def __init__(self, n):
        # we stor partial sum in each node of the tree
        self._trees = [0 for _ in range(n+1)]
        
    def update(self, i, delta):
        while i < len(self._trees):
            self._trees[i] += delta
            i += self.lowbit(i)
            

liyunrui

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        """
        Problem Clarification:
            1. what's input's length? what's minimum length and maximum length of array
            2. Can I assume I know range of element in the array? For example, nums[i] is between 0 to 100. If no, we have to use method 2 to reduce time complexity from brute force. If yes, we can use Method 3
            
        Problem formulation:
            Our goal is to count number of smaller element than the current element, given a fixed size input array.
        Thought Process:

liyunrui

# 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 findFrequentTreeSum(self, root: TreeNode) -> List[int]:
        """
        Problem formulation: