Mock Interview(1), LeetCode

 parent = [i for i in range(n)]
 def find(a):
    while parent[x] != x:
        # when parent[x] == x, then it is the true root
        parent[x] = parent[parent[x]] 
        # find the true father node of x
        # since the father node of x is parent[x], the father node of parent[x] is parent[parent[x]]
        # then the true father node of x is parent[parent[x]]
        # x is not the root, but parent[x] and parent[parent[x]] may be the root
        x = parent[x] 
        # update the x
    return x

 class Solution:
    def validTree(self, edges: List[List[int]]) -> bool:
        # [[1, 2]], [[1], [2]] all belongs to Lits[List[int]]
        if len(edges) != n - 1:
            return False

        parent = [i for i in range(n)]
        rank = [1] * n
        # each node is own root
        
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        
        def union(a, b):
            rootA = find(a)
            rootB = find(b)

            # if rootA = rootB, it means they already connected, there is a cycle
            if rootA == rootB:
                return False 
            
            if rank[rootA] > rank[rootB]:
                parent[rootB] = rootA 
                # update the parent root
            else: 
                parent[rootA] = rootB
                rank[rootA] += 1
            return True
        for u, v in range(edges):
            if not union(u, v):
                return False
        return True

from typing import List
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        result = []
        nums.sort() # the nums should be in order
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # Avoid duplicate group result in same element for i index
            left = i + 1
            right = len(nums) - 1
            while left < right:
                _sum = nums[i] + nums[left] + nums[right]
                if _sum < 0:
                    left += 1
                elif _sum > 0:
                    right -= 1
                else:
                    result.append([nums[i], nums[left], nums[right]])

                    # Avoid duplicate group result in same elements for left/right index
                    while left < right and nums[left] == nums[left + 1]:
                        # check left < right first to avoid list index out of range
                        left += 1
                    while left > right and nums[right] = nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
        return result

origin_num = [0, 1, 2, 3, 4, 5]
prefix_sum = [0, 1, 3, 6, 10, 15]
reminder_5 = [0, 1, 3, 1, 0, 0]
                 |     |
                    2 + 3 = 5

class Solution:
    def checkSubarraySum(self, nums, k):
        hashmap = {0: -1}
        _sum = 0
        for j in range(len(nums)):
            _sum += nums[j]
            remainder = _sum % k
            
            if remainder in hashmap:
                if j - hashmap[remainder] >= 2:
                    return True
            else:
                hashmap[remainder] = j
        return False