Python Tricks & Idioms

# LC 138

#-------------------------------------------------
# CASE 1) assignment : point to the same instance
#-------------------------------------------------

z = [1,2,3]

x = y = z

x  # -> [1, 2, 3]

y  # -> [1, 2, 3]

z  # -> [1, 2, 3]

z.append(4)

z  # -> [1, 2, 3, 4]

x  # -> [1, 2, 3, 4]

y  # -> [1, 2, 3, 4]

z  # -> [1, 2, 3, 4]


#-------------------------------------------------
# CASE 2) shallow copy : copy "parent" instance, but NOT sub instance
#-------------------------------------------------

# https://docs.python.org/3/tutorial/datastructures.html
# two spellings of the same shallow copy: a.copy() and a[:]

# demo
x = [1,2,3]

y = x[:]

y  # -> [1, 2, 3]

x.append(4)

x  # -> [1, 2, 3, 4]

y  # -> [1, 2, 3]


# LC 77 Combinations
class Solution(object):
    def combine(self, n, k):
        result = []
        
        def dfs(current, start):
            if(len(current) == k):
                result.append(current[:])
                return
            
            for i in range(start, n + 1):
                current.append(i)
                dfs(current, i + 1)
                current.pop()
            
        dfs([], 1)
        return result

#-------------------------------------------------
# CASE 3) deep copy : copy "parent" instance, AND sub instance
#-------------------------------------------------

import copy

x = [1,2,3]
z = copy.deepcopy(x)

x  # -> [1, 2, 3]

z  # -> [1, 2, 3]

x.append(4)

x  # -> [1, 2, 3, 4]

z  # -> [1, 2, 3]

z.append(5)

# NOTE : x, z NOT affect on each other

z  # -> [1, 2, 3, 5]

x  # -> [1, 2, 3, 4]

# ── The idiom you'll see everywhere (shallow copy of a list) ──
# how we make copy in py
intervals_cache = intervals[:]        # copy 1) slice
intervals_cache = intervals.copy()    # copy 2) .copy()  (same effect)
intervals_cache = list(intervals)     # copy 3) list()   (same effect)

#----------------------------------------------------------
# CASE A) FLAT list (ints, strings, …) → shallow copy IS enough
#----------------------------------------------------------
original = [1, 2, 3]
copy_    = original[:]         # independent copy

original.append(4)
original[0] = 99
print(original)   # [99, 2, 3, 4]
print(copy_)      # [1, 2, 3]     ← NOT affected  ✅

#----------------------------------------------------------
# CASE B) NESTED list (list of lists / objects) → shallow copy is NOT enough
#----------------------------------------------------------
original = [[1, 2], [3, 4]]
shallow  = original[:]        # copies OUTER list only; inner lists are SHARED

original.append([5, 6])       # outer-level change → safe
print(shallow)                # [[1, 2], [3, 4]]   ← NOT affected  ✅

original[0][0] = 99           # inner-level change → LEAKS through!
print(shallow)                # [[99, 2], [3, 4]]  ← AFFECTED  ❌

# → to be FULLY independent, use deepcopy:
import copy
deep = copy.deepcopy(original)
original[0][0] = -1
print(deep)                   # inner list unchanged  ✅

def _sort(x):
    _x = list(x)
    _x.sort()
    return "".join(_x)

x = "bca"
print (x)
x_ = _sort(x)
print (x_)

# ── The idiom ──
#   s[:i]      -> everything BEFORE index i   (i excluded)
#   ch         -> the new character to place at index i
#   s[i+1:]    -> everything AFTER index i    (i excluded, i.e. drop old s[i])
new_s = s[:i] + ch + s[i+1:]

# demo
s = "AACCGGTT"

s[:3] + "X" + s[3+1:]     # replace index 3 ('C') with 'X'  # -> 'AACXGGTT'

# original is untouched (immutable) — a NEW string is returned
s  # -> 'AACCGGTT'

s = "abc"
s[:1] + "X" + s[1+1:]   # 'aXc'  ← REPLACE index 1  (skip old 'b')
s[:1] + "X" + s[1:]     # 'aXbc' ← INSERT before index 1 (old 'b' kept)

# for each position i, try each candidate char ch
for i in range(len(cur_gene)):
    for ch in "ACGT":
        if ch == cur_gene[i]:
            continue
        # build the neighbor gene with position i mutated to ch
        new_gene = cur_gene[:i] + ch + cur_gene[i+1:]
        ...

>>> x = 'flower'
>>> x[:-1]
'flowe'
>>> x[:-1][:-1]
'flow'
>>> x[:-1][:-1][:-1]
'flo'
>>> ''[:-1]          # slicing never raises: an empty string stays empty
''

# LC 14 - Longest Common Prefix
# IDEA: take strs[0] as the candidate prefix; for each other word, drop the prefix's
#       last char (prefix[:-1]) until word.startswith(prefix)
# time = O(n * m + m^2), n = number of strings, m = len(strs[0]); space = O(m)
class Solution(object):
    def longestCommonPrefix(self, strs):
        if not strs:
            return ""

        prefix = strs[0]
        for i in range(1, len(strs)):
            word = strs[i]
            # shorten prefix from the right until this word starts with it
            while not word.startswith(prefix):
                prefix = prefix[:-1]
                # nothing left in common -> no later word can bring it back
                if not prefix:
                    return ""
        return prefix

strs = ["flower", "flow", "flight"]

word      prefix before   shrinks                      prefix after
"flow"    "flower"        flower -> flowe -> flow      "flow"
"flight"  "flow"          flow -> flo -> fl            "fl"
                                                       answer = "fl"

>>> s = "5#Hello5#World"
>>> s.find("#")          # from the beginning
1
>>> s.find("#", 7)       # search starts at index 7 -> next "#" is at 8
8
>>> s.find("#", 9)       # nothing at or after 9
-1
>>> s.find("#", 2, 7)    # optional end bound, exclusive: search s[2:7] only
-1
>>> s.index("#", 7)      # same search, but raises ValueError instead of -1
8

# LC 271 - Encode and Decode Strings
# IDEA: from header start i, s.find("#", i) locates the separator; the digits before it
#       are the word length, so slice the word and jump i to the next header
# time = O(N), N = len(s); space = O(N) for the output
def decode(self, s):
    res = []
    i = 0
    while i < len(s):
        sep = s.find("#", i)        # find first "#" from position i
        length = int(s[i:sep])
        res.append(s[sep + 1 : sep + 1 + length])
        i = sep + 1 + length
    return res

s = "5#Hello5#World"

i    s.find("#", i)   length = int(s[i:sep])   word                 next i
0    1                5                        s[2:7]  = "Hello"    7
7    8                5                        s[9:14] = "World"    14
                                                                    14 == len(s) -> stop

# python
# syntax : split(separator, number_of_split_result) 
# example 1
# In [17]: x = 'dig1 8 1 5 1'

# In [18]: x
# Out[18]: 'dig1 8 1 5 1'

# In [19]: x.split(" ")
# Out[19]: ['dig1', '8', '1', '5', '1']

# In [20]: x.split(" ", 1)
# Out[20]: ['dig1', '8 1 5 1']

# In [21]: x.split(" ", 2)
# Out[21]: ['dig1', '8', '1 5 1']

# In [22]: x.split(" ", 3)
# Out[22]: ['dig1', '8', '1', '5 1']

# In [23]: x.split(" ", 4)
# Out[23]: ['dig1', '8', '1', '5', '1']

# In [24]: x.split(" ", 100)
# Out[24]: ['dig1', '8', '1', '5', '1']

# example 2
# LC 937 Reorder Data in Log Files
class Solution:
    def reorderLogFiles(self, logs):
        def f(log):
            id_, rest = log.split(" ", 1)
            return (0, rest, id_) if rest[0].isalpha() else (1,)

        logs.sort(key = lambda x : f(x))
        return logs #sorted(logs, key = f)

# python
log = "let1 art can"

log.split(" ", 1)     # ['let1', 'art can']        <- head + the rest
log.split(" ")        # ['let1', 'art', 'can']     <- every space

identifier, content = log.split(" ", 1)   # ✅ always 2 parts here
# identifier, content = log.split(" ")    # ❌ ValueError: too many values to unpack

# the rest keeps its spaces, so it compares as one string
content                # 'art can'
content[0].isalpha()   # True  -> a letter-log (LC 937)

# LC 67. Add Binary
#NOTE : zfill syntax
#    -> fill n-1 "0" to a string at beginning

#example :
x = '1'

x.zfill(2)  # -> '01'

x.zfill(3)  # -> '001'

x.zfill(4)  # -> '0001'

x.zfill(10)  # -> '0000000001'

# python
# syntax : s.lstrip(chars) / s.rstrip(chars) / s.strip(chars)
#   - lstrip : remove matching chars from the LEFT  (leading)
#   - rstrip : remove matching chars from the RIGHT (trailing)
#   - strip  : remove matching chars from BOTH ends
#   - `chars` is a SET of characters to remove (NOT a substring/prefix!)
#   - no arg -> strips whitespace (space, \t, \n, \r ...)
#   - it does NOT touch chars in the MIDDLE, and returns a NEW string

#----------------------------
# example 1 : strip leading zeros (lstrip)
#----------------------------
x = "0000123"
x.lstrip("0")  # -> '123'

# no leading zeros -> unchanged (safe, no error)
y = "123"
y.lstrip("0")  # -> '123'

# all chars match -> empty string (WATCH OUT!)
"0000".lstrip("0")  # -> ''

#----------------------------
# example 2 : rstrip (trailing)
#----------------------------
"12300".rstrip("0")  # -> '123'

"hello!!!".rstrip("!")  # -> 'hello'

# common: drop trailing newline / whitespace when reading input
"  line\n".rstrip()  # -> '  line'

#----------------------------
# example 3 : strip (both ends) + whitespace default
#----------------------------
"  hi  ".strip()  # -> 'hi'

"xxhixx".strip("x")  # -> 'hi'

#----------------------------
# example 4 : GOTCHA — `chars` is a char SET, not a prefix string
#----------------------------
# removes ANY leading char that is 'a','b', or 'c' (in any order),
# NOT the literal prefix "abc"
"cabbage".lstrip("abc")  # -> 'ge'  (a set of chars, not a prefix: c,a,b,b,a go, 'g' stops it)

# to remove a real PREFIX/SUFFIX (py3.9+), use removeprefix / removesuffix:
"test.py".removesuffix(".py")  # -> 'test'
"img_001".removeprefix("img_")  # -> '001'

# LC 402. Remove K Digits
# after building the result digits in a stack, the front may have leading zeros
# e.g. stack -> "0200"  (must return "200", and "" must become "0")

res = "".join(stack).lstrip('0')   # "0200" -> "200",  "0000" -> ""
return res if res else "0"         # handle the all-zero / empty case

#-------------------------------
# ord() : char -> ASCII int
# chr() : ASCII int -> char
#-------------------------------
print(ord('a'))   # 97
print(ord('A'))   # 65
print(ord('0'))   # 48

print(chr(97))    # 'a'
print(chr(65))    # 'A'

# Common pattern: normalize letter to 0-25 index
ch = 'c'
idx = ord(ch) - ord('a')   # 2

# Shift a character by n positions
def shift(ch, n):
    return chr((ord(ch) - ord('a') + n) % 26 + ord('a'))

#-------------------------------
# String check methods
#-------------------------------
"abc".isalpha()     # True  — all letters
"abc123".isalpha()  # False
"123".isdigit()     # True  — all digits
"abc123".isalnum()  # True  — letters + digits
"  ".isspace()      # True
"ABC".isupper()     # True
"abc".islower()     # True

# LC 125 Valid Palindrome
def isPalindrome(s):
    filtered = [c.lower() for c in s if c.isalnum()]
    return filtered == filtered[::-1]

# NOTE: lower() has NO effect on digits — safe to call on any alphanumeric char
# >>> "0".lower()
# '0'
# >>> "A".lower()
# 'a'
# So the one-liner below works for both letters and numbers:
fixed_s = ''.join(c.lower() for c in s if c.isalnum())

s = "  Hello, World!  "

# Strip whitespace (or specific chars)
s.strip()          # "Hello, World!"
s.lstrip()         # "Hello, World!  "
s.rstrip()         # "  Hello, World!"
s.strip("!")       # "  Hello, World!  " (only strips specified chars from ends)

# Case
s.lower()          # "  hello, world!  "
s.upper()          # "  HELLO, WORLD!  "
s.title()          # "  Hello, World!  "
s.swapcase()       # "  hELLO, wORLD!  "

# Search
s.find("World")    # 9  (-1 if not found)
s.index("World")   # 9  (raises ValueError if not found)
s.count("l")       # 3
s.startswith("  H")  # True
s.endswith("!  ")    # True

# Replace and join
s.replace("World", "Python")   # "  Hello, Python!  "
", ".join(["a", "b", "c"])     # "a, b, c"
"a,b,c".split(",")             # ['a', 'b', 'c']

# Reverse a string
rev = s[::-1]

# String multiplication
"ab" * 3   # "ababab"
"-" * 10   # "----------"

# Check if string is a palindrome
def is_palindrome(s):
    return s == s[::-1]

# LC 008
s = '4193 with words'
res = re.search('(^[\+\-]?\d+)', s).group()
print (res)

x = "332"   # indices: 0, 1, 2

# ── Form 1: range(len(x)-1, -1, -1)  → stop = -1 (exclusive) → covers 2, 1, 0 (ALL indices)
for i in range(len(x)-1, -1, -1):
    print(i)
# 2
# 1
# 0   ← index 0 IS included

# ── Form 2: range(len(x)-1, 0, -1)   → stop = 0 (exclusive) → covers 2, 1 (MISSES index 0)
for i in range(len(x)-1, 0, -1):
    print(i)
# 2
# 1   ← index 0 is NOT included

# Equivalent ways to iterate a string/array in reverse (all indices)
x = "abc"

# Form A: range
for i in range(len(x) - 1, -1, -1):
    print(x[i])

# Form B: reversed() — cleaner, no index needed
for ch in reversed(x):
    print(ch)

# Form C: slice — creates a reversed copy
for ch in x[::-1]:
    print(ch)

# Safe to start from index 1 in forward loops, or stop before 0 in reverse loops
for i in range(len(x) - 1, 0, -1):   # compares x[i] vs x[i-1]; never i-1 = -1
    if x[i] == x[i - 1]:
        print(f"duplicate at {i}")

# example 1
# LC 973. K Closest Points to Origin
# IDEA : sort + lambda
class Solution(object):
    def kClosest(self, points, K):
        points.sort(key = lambda x : x[0]**2 +  x[1]**2)
        return points[:K]


# example 2
def my_func(x):
    return x**2

x = [-4,-5,0,1,2,5]
x.sort(key=lambda x: my_func(x))
print (x)  # -> [0, 1, 2, -4, -5, 5]

# LC 937
# https://leetcode.com/problems/reorder-data-in-log-files/solution/
def my_func(input):
    # do sth
    if condition:
        return key1, key2, key3....
    else:
        return key4, key5, key6....

my_array=["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
my_array.sort(key=lambda x : my_func(x))

# ── Context: LC 853 Car Fleet ──
# We have pos_speed = [[pos, speed, time], ...] and want to sort by position DESC.

# ── Form 1: negate the key  (in-place, fine-grained control) ──
pos_speed.sort(key=lambda x: -x[0])
# Use when:
#   • You need MIXED direction: primary DESC, secondary ASC
#     e.g. sort(key=lambda x: (-x[0], x[1]))  ← impossible with reverse=True alone
#   • Works for int and float keys

# ── Form 2: reverse=True  (cleaner for single-direction reversal) ──
pos_speed.sort(key=lambda x: x[0], reverse=True)
sorted_cars = sorted(cars, reverse=True)   # creates a NEW list
# Use when:
#   • ALL keys go the same direction (all DESC)
#   • More readable for simple cases
#   • sorted() is preferred over sort() when you need to keep the original

# ── Form 3: sort ASC then reverse/slice  (separate steps) ──
times = [(target - pos) / spe for pos, spe in sorted(cars)]   # ASC sort
for time in times[::-1]:        # iterate in reverse  — does NOT mutate list
    ...
# -- or --
for time in reversed(times):    # same effect, no extra list copy
    ...
# Use when:
#   • You want to keep the sorted-ASC list around for other uses
#   • reversed() is O(1) memory; [::-1] creates a new list copy

# ── Quick comparison ──
# Method              | In-place? | New list? | Mixed direction? | Readability
# -x[0]               |   yes     |    no     |      YES         |  moderate
# reverse=True        |   yes     |    no     |      no          |  high
# sorted(reverse=True)|   no      |    YES    |      no          |  high
# sort ASC + reversed |   yes     |    no     |      no          |  moderate

# ── Multi-key mixed direction example (only negation works here) ──
# Sort by position DESC, then by speed ASC as tiebreaker:
data.sort(key=lambda x: (-x[0], x[1]))

# python
y = [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
print (y)
# sort by x[0] DESC, then x[1] ASC
y.sort(key = lambda x : (-x[0], x[1]))
print (y)
# [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]
# [[7, 0], [7, 1], [6, 1], [5, 0], [5, 2], [4, 4]]

elem     | key = (-x[0], x[1])
---------------------------------
[7,0]    | (-7, 0)
[7,1]    | (-7, 1)
[6,1]    | (-6, 1)
[5,0]    | (-5, 0)
[5,2]    | (-5, 2)
[4,4]    | (-4, 4)

sort keys ASC  ->  (-7,0) < (-7,1) < (-6,1) < (-5,0) < (-5,2) < (-4,4)
                    ^^^^^^^^^^^^^^ 1st slot tied (-7) -> compare 2nd slot (0 < 1)
=> [[7,0], [7,1], [6,1], [5,0], [5,2], [4,4]]

# python
arr = [[1,'b'], [1,'a'], [2,'a']]

# (a) reverse=True flips the WHOLE ordering (every key), not just the 1st
sorted(arr, key = lambda x : (x[0], x[1]), reverse = True)
# [[2,'a'], [1,'b'], [1,'a']]   <-- x[0] DESC *and* x[1] DESC

# (b) negation flips only the negated slot
sorted(arr, key = lambda x : (-x[0], x[1]))
# [[2,'a'], [1,'a'], [1,'b']]   <-- x[0] DESC, x[1] ASC

# `-` only works on numbers
sorted(arr, key = lambda x : (-x[0], -x[1]))   # ❌ TypeError : bad operand type for unary -: 'str'

# python
# want : len(s) ASC, then s DESC  (can't do -s)
words = ["bb", "a", "ab", "c", "ba"]

words.sort(reverse = True)          # step 1 : least significant key (s DESC)
words.sort(key = len)               # step 2 : most  significant key (len ASC) - stable
print (words)
# ['c', 'a', 'bb', 'ba', 'ab']
#  ^^^^^^^^ len 1, DESC        ^^^^^^^^^^^^^^ len 2, DESC

# python
# LC 179 Largest Number : concat digits to form the biggest number
# rule : a before b  iff  a+b > b+a  -> not expressible as a single key
import functools

class Solution(object):
    def largestNumber(self, nums):
        # time = O(n log n * k), space = O(n)   (k = digit length)
        def cmp(a, b):
            if a + b > b + a:
                return -1      # a comes FIRST
            elif a + b < b + a:
                return 1       # b comes FIRST
            return 0

        strs = [str(x) for x in nums]
        strs.sort(key = functools.cmp_to_key(cmp))
        res = "".join(strs)
        return "0" if res[0] == "0" else res

# nums = [3,30,34,5,9] -> "9534330"

# python
# 1) sort dict by VALUE desc, then KEY asc  (LC 692 Top K Frequent Words)
from collections import Counter
cnt = Counter(["i","love","leetcode","i","love","coding"])
res = sorted(cnt.keys(), key = lambda w : (-cnt[w], w))
# ['i', 'love', 'coding', 'leetcode']

# 2) sort by "distance" (LC 973 K Closest Points to Origin)
points = [[1,3],[-2,2],[5,8],[0,1]]
points.sort(key = lambda p : p[0]**2 + p[1]**2)
# [[0,1], [-2,2], [1,3], [5,8]]

# 3) sort intervals by start (LC 56 / 57 / 253 / 435)
intervals = [[1,3],[8,10],[2,6],[15,18]]
intervals.sort(key = lambda x : x[0])
# [[1,3], [2,6], [8,10], [15,18]]

# 4) sort by end   (LC 435 Non-overlapping Intervals - greedy)
intervals.sort(key = lambda x : x[1])

# 5) sort chars of a string as the canonical key (LC 49 Group Anagrams)
"".join(sorted("tea"))    # 'aet'

# 6) sort with index preserved (need original position afterwards)
nums = [5,2,8]
idx_sorted = sorted(range(len(nums)), key = lambda i : nums[i])
# [1, 0, 2]   <-- indices in value order

# 7) sort intervals by BOTH ends (LC 56 Merge Intervals, LC 252 / 253 Meeting Rooms)
intervals.sort(key = lambda x : (x[0], x[1]))

# 8) primary ASC, secondary DESC -- negate only the secondary slot
events.sort(key = lambda x : (x[0], -x[1]))

# 9) sort a list of dicts by two fields
people = [{"age": 30, "name": "bob"}, {"age": 30, "name": "amy"}]
people.sort(key = lambda p : (p["age"], p["name"]))

# 10) three keys, same rule -- tuples compare left to right for any length
tasks.sort(key = lambda t : (t[0], t[1], t[2]))

# 11) sorted() returns a NEW list; .sort() mutates in place and returns None
sorted_events = sorted(event_list, key = lambda x : (x[0], x[1]))

// java
int[][] people = {{7,0},{4,4},{7,1},{5,0},{6,1},{5,2}};

// V1 : explicit comparator - x[0] DESC, tie-break x[1] ASC
Arrays.sort(people, (a, b) -> {
    if (a[0] != b[0]) {
        return Integer.compare(b[0], a[0]);   // (b, a) => DESC
    }
    return Integer.compare(a[1], b[1]);       // (a, b) => ASC
});

// V2 : Comparator chaining (more readable, Java 8+)
Arrays.sort(people,
        Comparator.<int[]>comparingInt(a -> a[0]).reversed()   // key1 DESC
                  .thenComparingInt(a -> a[1]));               // key2 ASC

// List version
List<int[]> list = new ArrayList<>();
list.sort(Comparator.<int[]>comparingInt(a -> a[0]).reversed()
                    .thenComparingInt(a -> a[1]));

// ⚠️ `b[0] - a[0]` can OVERFLOW for large/negative values
//    -> use Integer.compare(b[0], a[0]) instead
Arrays.sort(people, (a, b) -> Integer.compare(b[0], a[0]));

// ⚠️ `.reversed()` after `.thenComparing(...)` reverses the WHOLE chain
//    (same trap as python's reverse=True)
Comparator.comparingInt((int[] a) -> a[0])
          .thenComparingInt(a -> a[1])
          .reversed();          // <-- key1 DESC *and* key2 DESC

# 1) Expecting reverse=True to flip only the primary key
arr.sort(key = lambda x : (x[0], x[1]), reverse = True)   # ❌ flips BOTH keys
arr.sort(key = lambda x : (-x[0], x[1]))                  # ✅ only key1 DESC

# 2) Negating a string / tuple
arr.sort(key = lambda x : (-x[0], -x[1]))   # ❌ TypeError if x[1] is str
# ✅ use 2 stable sorts, or cmp_to_key

# 3) Comparing mixed types inside the key
sorted([1, "a"])            # ❌ TypeError : '<' not supported between 'str' and 'int'

# 4) Multi-pass sorts in the WRONG order
words.sort(key = len); words.sort(reverse = True)   # ❌ len grouping destroyed
words.sort(reverse = True); words.sort(key = len)   # ✅ least significant key FIRST

# 5) Forgetting the sort is what makes the greedy/2-pointer step valid
#    -> for interval problems, ALWAYS state which key you sorted on

# Return a tuple of sort keys; the FIRST element groups items,
# the rest order items WITHIN each group.
def compare(item):
    if condition:
        return (0, item.value, item.name)   # group 0 first; ASC by value, then name
    else:
        return (1, -item.priority, item.id)  # group 1 next; DESC by priority, ASC by id

items.sort(key=compare)        # in-place
# items = sorted(items, key=compare)   # or build a new list

class Solution:
    def reorderLogFiles(self, logs):
        def compare(log):
            id_, rest = log.split(" ", 1)
            if rest[0].isalpha():
                return (0, rest, id_)   # letter-logs: group 0, by content, then id
            else:
                return (1,)             # digit-logs: group 1, keep original order

        return sorted(logs, key=compare)

# python
# LC 937 - Reorder Data in Log Files (letter_logs already split from digit_logs)

# V1: lambda — fine for a one-off, but it calls split TWICE per log
letter_logs.sort(
    key=lambda log: (log.split(" ", 1)[1], log.split(" ", 1)[0])
)

# V2: helper function — split once, unpack into names, return the tuple
class Solution(object):
    def sort_key(self, log):
        identifier, content = log.split(" ", 1)
        return (content, identifier)    # by content, then identifier

    # ... inside reorderLogFiles:
    #     letter_logs.sort(key=self.sort_key)   # pass the function, do NOT call it

# LC 451 Sort Characters By Frequency
# V1
import collections
class Solution(object):
    def frequencySort(self, s):
        d = collections.Counter(s)
        d_dict = dict(d)
        res = []
        for x in sorted(d_dict, key=lambda k : -d_dict[k]):
            res.append(x)
        return res

x= [1, 2, 3, 1, 2, 1, 2, 1]
s = Solution()
r = s.frequencySort(x)

# V2
# https://stackoverflow.com/questions/613183/how-do-i-sort-a-dictionary-by-value
import collections
class Solution(object):
    def frequencySort(self, s):
        d = collections.Counter(s)
        d_dict = dict(d)
        res = []
        #for x in sorted(d_dict.items(), key=lambda items: -items[1]):
        for _ in sorted(d_dict.items(), key=lambda x: -x[1]):
            res.append(_)
        return res

x= [1, 2, 3, 1, 2, 1, 2, 1]
s = Solution()
r = s.frequencySort(x)

# LC 347 - Top K Frequent Elements
# IDEA: count with Counter, then most_common(k) hands back the k (num, freq) pairs
#       with the highest freq; keep only the num of each pair
# time = O(n + u log k), u = number of distinct values; space = O(u)
from collections import Counter

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        if not nums:
            return []

        cnt = Counter(nums)

        return [num for num, freq in cnt.most_common(k)]

nums = [1,1,1,2,2,3], k = 2
Counter(nums)          -> Counter({1: 3, 2: 2, 3: 1})
cnt.most_common(2)     -> [(1, 3), (2, 2)]
[num for num, freq ..] -> [1, 2]

# key= works exactly like sort's key= parameter
nums = [-3, -1, 2, 4]
print(max(nums, key=abs))   # -3  (largest absolute value)
print(min(nums, key=abs))   # -1  (smallest absolute value)

# With iterable of tuples
points = [(1, 5), (3, 2), (2, 8)]
print(max(points, key=lambda p: p[1]))  # (2, 8)

# min/max with default (avoids error on empty iterable)
print(min([], default=0))   # 0

# clamp a value between lo and hi
val = max(lo, min(val, hi))

# sorted() returns a NEW list; list.sort() is in-place
nums = [3, 1, 4, 1, 5]
print(sorted(nums))            # [1, 1, 3, 4, 5]  — nums unchanged
print(sorted(nums, reverse=True))  # [5, 4, 3, 1, 1]

# Sort list of tuples: primary key asc, secondary key desc
pairs = [(1, 3), (2, 1), (1, 5)]
pairs.sort(key=lambda x: (x[0], -x[1]))
# [(1, 5), (1, 3), (2, 1)]

# reversed() returns an iterator
for x in reversed([1, 2, 3]):
    print(x)  # 3 2 1

list(reversed([1,2,3]))  # [3, 2, 1]

# sum() with start
sum([1, 2, 3], 10)   # 16

# sum of 2D list
matrix = [[1,2],[3,4]]
total = sum(sum(row) for row in matrix)  # 10

# abs()
abs(-5)    # 5
abs(3+4j)  # 5.0  (complex magnitude)

x,y = divmod(100, 3)

x  # -> 33

y  # -> 1

#-----------------
# V1 : %=
#-----------------

x = 100

x %= 60

x  # -> 40

y = 120

y %= 60

y  # -> 0

#-----------------
# V2 : divmod
#-----------------
a = 100

q, r = divmod(a, 60)

q  # -> 1

r  # -> 40

b = 120

q2, r2 = divmod(b, 60)

q2  # -> 2

r2  # -> 0

# LC 1010
# V0
# IDEA : dict
class Solution(object):
    def numPairsDivisibleBy60(self, time):
        rem = {}
        pairs = 0
        for t in time:
            #print ("rem = " + str(rem))
            t %= 60
            if (60 - t) % 60 in rem:
                pairs += rem[(60 - t) % 60]
            if t not in rem:
                rem[t] = 1
            else:
                rem[t] += 1
        return pairs

# https://www.runoob.com/python/func-number-ceil.html
# https://www.runoob.com/python/func-number-ceil.html

"""
The method ceil(x) in Python returns a ceiling value of x 
-> i.e., the SMALLEST integer GREATER than or EQUAL to x.
"""
import math

# prints the ceil using ceil() method
print ("math.ceil(-23.11) : ", math.ceil(-23.11))
print ("math.ceil(300.16) : ", math.ceil(300.16))
print ("math.ceil(300.72) : ", math.ceil(300.72))
# -> math.ceil(-23.11) :  -23
#    math.ceil(300.16) :  301
#    math.ceil(300.72) :  301


# LC 875. Koko Eating Bananas
#...
# Iterate over the piles and calculate hour_spent.
# We increase the hour_spent by ceil(pile / middle)
for pile in piles:
    # python ceil : https://www.runoob.com/python/func-number-ceil.html
    hour_spent += math.ceil(pile / middle)
# Check if middle is a workable speed, and cut the search space by half.
if hour_spent <= h:
    right = middle
else:
    left = middle + 1
#...

# https://www.geeksforgeeks.org/floor-ceil-function-python/

"""
floor() method in Python returns the floor of x 
-> i.e., the LARGEST integer NOT GREATER than x. 
"""

# This will import math module
import math   
  
import math

# prints the ceil using floor() method
print ("math.floor(-23.11) : ", math.floor(-23.11))
print ("math.floor(300.16) : ", math.floor(300.16))
print ("math.floor(300.72) : ", math.floor(300.72))
# -> math.floor(-23.11) :  -24
#    math.floor(300.16) :  300
#    math.floor(300.72) :  300

# Built-in 3-arg pow is O(log n), much faster than (x**n) % mod
MOD = 10**9 + 7

print(pow(2, 10, MOD))    # 1024
print(pow(2, 100, MOD))   # 976371285  (computed efficiently)

# Modular inverse (when mod is prime): pow(a, mod-2, mod)
inv = pow(3, MOD - 2, MOD)   # modular inverse of 3

# LC 50 Pow(x, n) — manual fast power
def myPow(x, n):
    if n < 0:
        x, n = 1 / x, -n
    res = 1
    while n:
        if n % 2 == 1:
            res *= x
        x *= x
        n //= 2
    return res

#-------------------------------
# Integer division (floor division)
#-------------------------------
7 // 2    # 3
-7 // 2   # -4  (rounds toward -inf, NOT toward 0!)
int(-7/2) # -3  (truncation toward 0)

# Safe mid-point (avoids overflow in other languages)
lo, hi = 0, 100
mid = (lo + hi) // 2

#-------------------------------
# Bit operations (common in LC)
#-------------------------------
# AND, OR, XOR, NOT
5 & 3    # 1   (101 & 011 = 001)
5 | 3    # 7   (101 | 011 = 111)
5 ^ 3    # 6   (101 ^ 011 = 110)
~5       # -6  (bitwise NOT: ~x = -(x+1))

# Shift
5 << 1   # 10  (multiply by 2)
5 >> 1   # 2   (floor divide by 2)

# Check/set/clear bit i
x = 13          # 1101
x & (1 << i)    # check bit i (non-zero if set)
x | (1 << i)    # set bit i
x & ~(1 << i)   # clear bit i
x ^ (1 << i)    # flip bit i

# Count set bits
bin(13).count('1')   # 3
# or: use Brian Kernighan
def count_bits(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# x & (x-1) removes lowest set bit — useful for power-of-2 check
def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

# math.html

# How does int(x[,base]) work?
# -> https://stackoverflow.com/questions/33664451/how-does-intx-base-work
# -> int(string, base) accepts an arbitrary base. You are probably familiar with binary and hexadecimal, and perhaps octal; these are just ways of noting an integer number in different bases:
# exmaple :
# In [76]: int('10',2)      # transform '10' from 2 based to 10 based                                                  
# Out[76]: 2
#
# In [77]: int('11',2)      # # transform '11' from 2 based to 10 based                                                 
# Out[77]: 3
#
# In [78]: int('100',2)     # # transform '100' from 2 based to 10 based                                                 
# Out[78]: 4

# LC 089

# python
int("-2")      # -2
int("+7")      # 7
int(" 13 ")    # 13   (whitespace is stripped)
int("-0")      # 0
# int("3.5")   # ❌ ValueError — use int(float("3.5")) -> 3

# LC 150 - Evaluate Reverse Polish Notation
# IDEA: a token that is not one of "+-*/" is a number, signed or not -> int(t) parses it
# time = O(n), space = O(n)
class Solution(object):
    def evalRPN(self, tokens):
        st = []
        for t in tokens:
            if t not in {"+", "-", "*", "/"}:
                # int() handles both "13" and "-11"; no sign check needed
                st.append(int(t))
            else:
                right = st.pop()   # popped first = right operand
                left = st.pop()
                if t == "+":
                    st.append(left + right)
                elif t == "-":
                    st.append(left - right)
                elif t == "*":
                    st.append(left * right)
                else:
                    # truncate toward 0, NOT floor: see "Integer division" above
                    st.append(int(float(left) / right))
        return st[0]

# Use float('inf') / float('-inf') instead of sys.maxsize for clarity
INF = float('inf')
NEG_INF = float('-inf')

# Works with min/max comparisons
min_val = float('inf')
for x in [3, 1, 4, 1, 5]:
    min_val = min(min_val, x)
print(min_val)  # 1

# Common in DP initialization
dp = [[float('inf')] * n for _ in range(m)]

# Python int has no overflow — safe to use large numbers
# But float('inf') is cleaner for "unbounded" semantics

# example 1
a = "000"

all( i == "0" for i in a )  # -> True

# example 2
b = "abc123"

all ( i == "a" for i in b )  # -> False

# LC 763. Partition Labels
class Solution(object):
    def partitionLabels(self, s):
        d = {val:idx for idx, val in enumerate(list(s))}
        #print (d)
        res = []
        tmp = set()
        for idx, val in enumerate(s):
            """
            NOTE : below condition
            """
            if idx == d[val] and all(idx >= d[t] for t in tmp):
                res.append(idx+1)
            else:
                tmp.add(val)
        _res = [res[0]] + [ res[i] - res[i-1] for i in range(1, len(res)) ]
        return _res

# Returns True if ANY element in iterable is True (short-circuits)
any([False, False, True])  # -> True

any([False, False, False])  # -> False

any(x > 3 for x in [1, 2, 5])  # -> True

# Complement to all():
# all() -> every element must be True
# any() -> at least one element must be True

#----------------------------
# can be either None, [], ""
#----------------------------
x = None

not x  # -> True

y = []

not y  # -> True

z = ""

not z  # -> True

# Returns (index, value) pairs — avoids manual index tracking
fruits = ['apple', 'banana', 'cherry']

for i, v in enumerate(fruits):
    print(i, v)
# 0 apple
# 1 banana
# 2 cherry

# start parameter
for i, v in enumerate(fruits, start=1):
    print(i, v)
# 1 apple  2 banana  3 cherry

# Build index map (very common in LC)
s = "abcba"
idx_map = {v: i for i, v in enumerate(s)}
print(idx_map)  # {'a': 4, 'b': 3, 'c': 2}  (last occurrence)

# python
for x, y in zip([-1, 1, 0, 0], [0, 0, -1, 1]):
    print (x, y)
# -> -1 0
#    1 0
#    0 -1
#    0 1

for x, y, z in zip([-1, 1, 0, 0], [0, 0, -1, 1], [0,0,0,0]):
    print (x,y,z)
# -> -1 0 0
#    1 0 0
#    0 -1 0
#    0 1 0

for x, y, z, u in zip([-1, 1, 0, 0], [0, 0, -1, 1], [0,0,0,0], [9,9,9,9]):
    print (x,y,z,u)
# -> -1 0 0 9
#    1 0 0 9
#    0 -1 0 9
#    0 1 0 9

d = {'a':1, 'b':2, 'c': 3}
# loop over key, value
for k, v in d.items():
    print (k, v)

# loop over key
for k in d.keys():
    print (k)

# loop over value
for v in d.values():
    print (v)

# Extended Iterable Unpacking

# https://www.python.org/dev/peps/pep-3132/
# http://swaywang.blogspot.com/2012/01/pythonstarred-expression.html

# example 1
a, *b, c = range(5)

a  # -> 0

b  # -> [1, 2, 3]

c  # -> 4

# example 2
for a, *b in [(1, 2, 3), (4, 5, 6, 7)]:
    print ("a = " + str(a) + " b = " + str(b))
# -> a = 1 b = [2, 3]
#    a = 4 b = [5, 6, 7]

# example 3
first, *rest = [1, 2, 3, 4, 5]

first  # -> 1

rest  # -> [2, 3, 4, 5]

# example 4
*directories, executable = "/usr/local/bin/vim".split("/")
print (directories)
print (executable)
# -> ['', 'usr', 'local', 'bin']
#    vim

# example 5
args = [1,3]
print (range(*args))

# https://www.runoob.com/python/python-func-filter.html

#-----------------------------------------------
# syntax : filter(<filter_func>, <iterable>)
#-----------------------------------------------

# note !!! : in py 3, it will return iterable instance; while in py 2, it will return a list directly

#----------------------------
# example 1
#----------------------------
def is_odd(n):
    return n % 2 == 1

newlist = filter(is_odd, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
print(newlist)  # -> <filter object at 0x...>  (lazy: nothing computed yet)
list(newlist)  # -> [1, 3, 5, 7, 9]


#----------------------------
# example 2
#----------------------------
import math
def is_sqr(x):
    return math.sqrt(x) % 1 == 0

newlist = filter(is_sqr, range(1, 101))
print(newlist)  # -> <filter object at 0x...>
list(newlist)  # -> [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]

#----------------------------
# example 1
#----------------------------
# https://stackoverflow.com/questions/4260280/if-else-in-a-list-comprehension

[ x for x in range(5) ]  # -> [0, 1, 2, 3, 4]

# NOTE this !!!!
[ x if x % 2 == 0 else -1 for x in range(5) ]  # -> [0, -1, 2, -1, 4]

def my_func(x):
    if x % 2 ==0:
        return True
    return False

[ x if my_func(x) else 999  for x in range(5)]  # -> [0, 999, 2, 999, 4]

# map(func, iterable) — lazy, returns iterator
nums = ["1", "2", "3"]
ints = list(map(int, nums))    # [1, 2, 3]

# map with lambda
doubled = list(map(lambda x: x * 2, [1, 2, 3]))  # [2, 4, 6]

# Generator expression (lazy list comprehension) — memory efficient
gen = (x**2 for x in range(1000000))   # nothing computed yet
total = sum(x**2 for x in range(1000000))  # computed on the fly

# Prefer generator expression over list comprehension inside sum/any/all/max/min
max_val = max(abs(x) for x in nums)
has_neg = any(x < 0 for x in nums)

# syntax: <value_if_true> if <condition> else <value_if_false>
x = 5
result = "even" if x % 2 == 0 else "odd"   # "odd"

# Nested ternary (keep shallow — hard to read beyond two levels)
sign = "positive" if x > 0 else ("zero" if x == 0 else "negative")

# Common LC use
ans = left if left else right          # return whichever is not None
val = node.val if node else 0

d = {'a': 1, 'b': 2}

# get(key, default) — safe access
d.get('c', 0)     # 0  (no KeyError)
d.get('a', 0)     # 1

# setdefault(key, default) — insert if missing, return value
d.setdefault('c', []).append(3)   # d['c'] = [3]
d.setdefault('c', []).append(4)   # d['c'] = [3, 4]

# dict comprehension
squares = {x: x**2 for x in range(5)}
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

# invert a dict (assuming unique values)
inv = {v: k for k, v in squares.items()}

# filter dict
evens = {k: v for k, v in squares.items() if v % 2 == 0}

# plain dict: insertion order is guaranteed, and these two idioms cover most needs
d = {'a': 1, 'b': 2, 'c': 3}

d['a'] = d.pop('a')        # "move to the end"     -> ['b', 'c', 'a']
first = next(iter(d))      # peek the OLDEST key   -> 'b'   (no popitem(last=False) here)
d.popitem()                # pops the NEWEST pair  -> ('a', 1)

# IDEA: OrderedDict basics — build, iterate in insertion order, pop from either end
from collections import OrderedDict

#----------------------------
# build (three equivalent ways)
#----------------------------
d = OrderedDict()
d['a'] = 1
d['b'] = 2
d['c'] = 3

d = OrderedDict([('a', 1), ('b', 2), ('c', 3)])   # from pairs
d = OrderedDict(a=1, b=2, c=3)                    # from kwargs

#----------------------------
# iterate — always in INSERTION order
#----------------------------
for key, value in d.items():
    print(key, value)       # a 1 / b 2 / c 3

list(d)                     # ['a', 'b', 'c']   keys
list(reversed(d))           # ['c', 'b', 'a']   newest first

#----------------------------
# read / write — ordinary dict behaviour
#----------------------------
d['b']                      # 2
d.get('z', 0)               # 0   (no KeyError)
'a' in d                    # True
len(d)                      # 3

d['a'] = 99                 # NOTE: updating a value does NOT reorder -> ['a', 'b', 'c']
d.move_to_end('a')          # this is what reorders           -> ['b', 'c', 'a']

#----------------------------
# pop — the argument picks the END, not the count
#----------------------------
d = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
d.popitem(last=False)       # ('a', 1)  FIFO — the EARLIEST inserted  (the LRU victim)
d.popitem()                 # ('c', 3)  LIFO — the latest  (the default)
del d['b']                  # by key, like any dict
# popitem() on an empty OrderedDict raises KeyError('dictionary is empty')

a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

# Basic ops
a | b    # union        {1, 2, 3, 4, 5, 6}
a & b    # intersection {3, 4}
a - b    # difference   {1, 2}
a ^ b    # symmetric diff {1, 2, 5, 6}

# Membership: O(1) average
3 in a   # True

# Mutation
a.add(5)
a.discard(99)   # no error if missing (vs remove() which raises KeyError)
a.remove(1)     # raises KeyError if missing

# NOTE: can directly remove a specific element from a set by value (not index)
# Common in sliding window problems (LC 3)
seen = set()
seen.add('a')
seen.remove('a')   # removes 'a' directly — no index needed

# Set comprehension
squares = {x**2 for x in range(5)}   # {0, 1, 4, 9, 16}

# Freeze (hashable, usable as dict key)
fs = frozenset([1, 2, 3])

reachable_u = {0, 1}
reachable_v = {2, 3}

reachable_v.update(reachable_u)
print(reachable_v)          # {0, 1, 2, 3}
print(reachable_u)          # {0, 1}  -- the argument is untouched

# same result, three spellings
x = {2, 3}; x.update({0, 1})       # in place, returns None
y = {2, 3}; y |= {0, 1}            # in place, operator form
z = {2, 3} | {0, 1}                # NEW set; the operands are untouched

# GOTCHA: update returns None, so never assign its result
# s = s.update(t)                  # ❌ s is now None

# LC 1462 - Course Schedule IV
# IDEA: Kahn's topological sort; reachable[v] = every course that must come before v.
#       For each edge u -> v: add u itself, then union in everything u needs.
# time = O(n * e + q), space = O(n^2)
from collections import defaultdict, deque

class Solution(object):
    def checkIfPrerequisite(self, numCourses, prerequisites, queries):
        graph = defaultdict(list)
        indegree = [0] * numCourses
        for u, v in prerequisites:
            graph[u].append(v)
            indegree[v] += 1

        # reachable[v]: every course that is a prerequisite of v, direct or indirect
        reachable = [set() for _ in range(numCourses)]

        q = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)

        while q:
            u = q.popleft()
            for v in graph[u]:
                # u itself is a prerequisite of v
                reachable[v].add(u)
                # every prerequisite of u is also a prerequisite of v
                reachable[v].update(reachable[u])

                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)

        res = []
        for u, v in queries:
            res.append(u in reachable[v])
        return res

numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]]
pop 1: edge 1->2  reachable[2] = {1}
       edge 1->0  reachable[0] = {1}
pop 2: edge 2->0  reachable[0].add(2)            -> {1, 2}
                  reachable[0].update({1})       -> {1, 2}
pop 0: no edges
queries [[1,0],[1,2]] -> [1 in {1,2}, 1 in {1}] -> [True, True]

def test(l1, l2):
    if l1 or l2:
        return l1 or l2

res = test("l1", None)
print (res)

res2 = test(None, "l2")
print (res2)
# -> l1
#    l2

#-------------------------------------------------
# CORRECT way — use list comprehension (independent rows)
#-------------------------------------------------
m, n = 3, 4
grid = [[0] * n for _ in range(m)]
grid[0][0] = 1
# Only grid[0][0] is changed

#-------------------------------------------------
# WRONG way — all rows share the same list!
#-------------------------------------------------
bad = [[0] * n] * m
bad[0][0] = 1
# ALL rows become [1, 0, 0, 0]  — common bug!

#-------------------------------------------------
# Common DP patterns
#-------------------------------------------------
# 1D DP
dp = [0] * (n + 1)

# 2D DP (m rows, n cols, filled with False)
dp = [[False] * (n + 1) for _ in range(m + 1)]

# Fill with infinity
dp = [[float('inf')] * n for _ in range(m)]

# python
# List `+` makes a NEW list, so the ends can be glued on in one expression:
#   [1]        -> the fixed first element
#   new_val    -> the computed middle (may be empty)
#   [1]        -> the fixed last element
#
# NOTE : this is concatenation, NOT append —
#        [1] + [2, 3] + [1]  ->  [1, 2, 3, 1]
#        [1].append([2, 3])  ->  None (mutates in place, returns nothing)

# an empty middle still works — no special case needed
[1] + [] + [1]        # [1, 1]

# python
# LC 118 Pascal's Triangle
# IDEA: 1D DP — row i is built from row i-1
class Solution(object):
    def generate(self, numRows):
        # edge
        if numRows == 0:
            return []
        if numRows == 1:
            return [[1]]
        if numRows == 2:
            return [[1], [1, 1]]

        n = numRows

        # dp[i] = the i-th row
        dp = [None] * n

        dp[0] = [1]
        dp[1] = [1, 1]

        for i in range(2, n):

            new_val = []

            # previous row
            prev = dp[i - 1]

            # calculate middle values
            for j in range(len(prev) - 1):
                new_val.append(prev[j] + prev[j + 1])

            # how we add [1] at beginning and end
            # first and last are always 1
            dp[i] = [1] + new_val + [1]

        return dp

# time = O(n^2), space = O(n^2)

# nonlocal: modify a variable in the ENCLOSING (not global) scope
def outer():
    count = 0
    def inner():
        nonlocal count
        count += 1
    inner()
    inner()
    print(count)  # 2

# Without nonlocal, count += 1 raises UnboundLocalError

# global: modify a module-level variable inside a function
total = 0
def add(x):
    global total
    total += x

# Common LC pattern: DFS with mutable result
def maxDepth(root):
    res = [0]
    def dfs(node, depth):
        if not node:
            return
        res[0] = max(res[0], depth)  # list trick avoids nonlocal
        dfs(node.left, depth + 1)
        dfs(node.right, depth + 1)
    dfs(root, 1)
    return res[0]

isinstance(3, int)        # True
isinstance(3.0, float)    # True
isinstance("hi", str)     # True
isinstance([], list)      # True
isinstance({}, dict)      # True

# Check multiple types at once
isinstance(3, (int, float))   # True

# type() for exact type (no inheritance)
type(3) == int    # True
type(True) == int # False  (bool is subclass of int, but type() is exact)
isinstance(True, int)  # True  (True IS an int!)

// java — the pattern we want to port
private static class SubtreeInfo {
    int height;
    int size;
    boolean isPerfect;
}

# python
from dataclasses import dataclass

@dataclass
class SubtreeInfo:
    height: int
    size: int
    is_perfect: bool


def dfs(node):
    # returns SubtreeInfo carrying 3 values up the recursion
    if node is None:
        return SubtreeInfo(0, 0, True)

    left = dfs(node.left)
    right = dfs(node.right)

    is_perfect = (
        left.is_perfect
        and right.is_perfect
        and left.height == right.height
    )

    size = left.size + right.size + 1
    height = max(left.height, right.height) + 1

    if is_perfect:
        perfect_sizes.append(size)

    return SubtreeInfo(height, size, is_perfect)

# usage
info = dfs(root)
print(info.height, info.size, info.is_perfect)

# python
class SubtreeInfo:
    def __init__(self, height, size, is_perfect):
        self.height = height
        self.size = size
        self.is_perfect = is_perfect

# usage is identical
info = dfs(root)
print(info.height)

# python
from typing import NamedTuple

class SubtreeInfo(NamedTuple):
    height: int
    size: int
    is_perfect: bool

info = dfs(root)
print(info.height)          # attribute access
h, s, p = info              # tuple unpacking also works

# https://www.runoob.com/python/python-func-eval.html
# https://www.programiz.com/python-programming/methods/built-in/eval
# The eval() method parses the expression passed to this method and runs python expression (code) within the program.

# LC 640
# LC 150

# syntax : eval(expression[, globals[, locals]])

# eample
x = 7
eval('3 * x')  # -> 21

eval ('2 + 2')  # -> 4

n = 81
eval('n + 4')  # -> 85

if len(l1) < len(l2):
   l1, l2 = l2, l1

- if path is `str` type, we DON'T need to undo (backtrack)
     -> since it's IMMUTABLE.

- if path is `array` ([]) type, we NEED to undo (backtrack)
     -> since it's MUTABLE.

# LC 257 - Binary Tree Paths
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Depth-First-Search/binary-tree-paths.py

#-------------------------------------------------
# CASE 1) path as ARRAY (mutable) -> MUST backtrack (path.pop())
#-------------------------------------------------
class Solution(object):
    def binaryTreePaths(self, root):
        self.res = []
        self.helper(root, [])      # use array ([]) as tmp cache
        return self.res

    def helper(self, root, path):
        if not root:
            return
        path.append(str(root.val))            # mutate shared list
        # leaf node
        if not root.left and not root.right:
            self.res.append("->".join(path))
        else:
            self.helper(root.left, path)
            self.helper(root.right, path)
        # backtrack at the final stage (undo the append)
        path.pop()

#-------------------------------------------------
# CASE 2) path as STRING (immutable) -> NO backtrack needed
#-------------------------------------------------
class Solution(object):
    def binaryTreePaths(self, root):
        res = []
        def dfs(node, cur):
            if not node:
                return
            cur = str(node.val) if cur == "" else cur + "->" + str(node.val)  # new string each call
            if not node.left and not node.right:
                res.append(cur)
                return
            # no path.pop() — each branch got its own string copy
            dfs(node.left, cur)
            dfs(node.right, cur)
        dfs(root, "")
        return res

# trick: build a NEW list per call (tmp + [x]) instead of append+pop
def dfs(r, tmp):
    if not r.left and not r.right:
        ans.append("->".join(tmp))
    if r.left:
        dfs(r.left, tmp + [str(r.left.val)])    # tmp + [..] -> new list, no pop
    if r.right:
        dfs(r.right, tmp + [str(r.right.val)])

# LC 113 - Path Sum II
# https://github.com/yennanliu/CS_basics/blob/master/leetcode_python/Depth-First-Search/path-sum-ii.py
class Solution(object):
    def pathSum(self, root, targetSum):
        self.res = []
        if not root:
            return self.res
        self.helper(root, targetSum, 0, [])
        return self.res

    def helper(self, root, targetSum, cur_sum, cache):
        if not root:
            return

        cur_sum += root.val        # int  -> rebinds LOCAL name to a new int (immutable)
        cache.append(root.val)     # list -> mutates the ONE shared list

        if not root.left and not root.right and cur_sum == targetSum:
            self.res.append(cache[:])    # snapshot — cache[:] copies, else later pops corrupt it

        self.helper(root.left,  targetSum, cur_sum, cache)
        self.helper(root.right, targetSum, cur_sum, cache)

        cache.pop()                # MUST backtrack the list ...
        # NOTE: NO `cur_sum -= root.val` — the int never changed for the parent

# 445 Add Two Numbers II
# 394 Decode String
def str_2_int(x):
    r=0
    for i in x:
        r = int(r)*10 + int(i)
        print (i, r)
    return r

def str_2_int_v2(x):
    res = 0
    for i in x:
        res = (res + int(i) % 10) * 10
    return int(res / 10)

# example 1
x="131"
r=str_2_int(x)
print (r)
# 1 1
# 3 13
# 1 131
# 131

# example 2
z = '5634'

ans = 0

for i in z:
    ans = 10 * ans + int(i)

ans  # -> 5634