humpydonkey

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        """
        If we fix one dimension, the question essentially becomes a "two sum smaller" problem
        The ideas are:
        1) when sum < target, count += r - l, then we need to move left to the next bigger value
        2) otherwise move r to the next smaller value
        """
        nums.sort()
        n = len(nums)

humpydonkey

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        """
        One outer loop + Two pointer
        Time: O(n^2)
        Space: O(1)
        """
        nums.sort()
        n = len(nums)
        closest_distance = float('inf') 

humpydonkey

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s)-1
        while l < r:
            if not s[l].isalnum():
                l += 1
            elif not s[r].isalnum():
                r -= 1
            else:
                if s[r].lower() != s[l].lower():

humpydonkey

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        Three pointer solution built on top of the two-sum problem. 
        Time: O(n^2)
        Space: O(1)
        The trick is how to handle duplicate. The order of checking two pointers' equality matters: one must move pointer first, 
        then check equality against the prior value. The case starting from the prior value included the second case.  
        E.g. -1, 0, 0, 1
        0, 0, 1 included the case of 0, 1. But the case starts from the second 0 doesn't include the prior case.

humpydonkey

"""
# Definition for Employee.
class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates
"""

class Solution:

humpydonkey

class SparseVector:
    """
    Time: O(n) for __init__, O(L) for dotProduct
    Space: O(L), where L is the number of non-zero values
    """
    def __init__(self, nums: List[int]):
        self.values = []
        self.index = []
        for i in range(len(nums)):
            if nums[i] != 0:

humpydonkey

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        """ 
        Idea: find (i, j) where prefix_sums_j - prefix_sums_i == k
        tip: sum(i,j)=sum(0,j)-sum(0,i), 
        where sum(i,j) represents the sum of all the elements from index i to j-1.
        """
        sum_counts = defaultdict(int)
        sum_counts[0] = 1
        accumulate_sum = 0

humpydonkey

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        """
        Trick: remainder + n * k = some prefix sum (i...j)
             => (remainder + n * k) % k = some prefix sum (i...j) % k
             => remainder = some prefix sum (i...j) % k
         In other words:
            a % k = x
            b % k = x
            (a - b) % k = x -x = 0

humpydonkey

import os


def flat_directory(source_dir: str) -> None:
    """
    Move all the files under src directory to the root of src directory.
    Flatten the structure.
    """
    count = 0
    for currDir, subDirs, files in os.walk(source_dir):

humpydonkey

import os
from typing import Set
import shutil


def check_existence_or_copy(source_dir: str, check_against_dir: str, copy_dst_dir: str) -> None:
    missing_files = check_missing(source_dir, check_against_dir)
    copy_missing_files(source_dir, copy_dst_dir, missing_files)