Python Interview Prep — The Complete Guide

class Dog:
    def __init__(self, name):
        self.name = name       # instance attribute
 
    def bark(self):
        print("Woof!")
 
dog1 = Dog("Johnny")           # object = instance of class
dog1.bark()                    # Woof!

class Account:
    def __init__(self, balance):
        self.__balance = balance   # __ prefix = private (name mangling)
 
    def get_balance(self):
        return self.__balance
 
    def set_balance(self, amount):
        if amount >= 0:
            self.__balance = amount
 
acc = Account(1000)
acc.get_balance()              # 1000
# acc.__balance                # AttributeError — private!

class Animal:
    def has_legs(self):
        print("Has 4 legs")
 
class Dog(Animal):             # Dog inherits Animal
    def bark(self):
        print("Woof!")
 
dog = Dog()
dog.has_legs()                 # inherited from Animal
dog.bark()                     # own method

class Dog(Animal):
    def sound(self):
        super().sound()        # call parent first
        print("Woof")

class Animal:
    def sound(self): print("Some Sound")
 
class Dog(Animal):
    def sound(self): print("Woof")    # method overriding
 
class Cat(Animal):
    def sound(self): print("Meow")
 
animals = [Dog(), Cat()]
for a in animals:
    a.sound()                  # Woof, then Meow — runtime polymorphism

from abc import ABC, abstractmethod
 
class PaymentGateway(ABC):
    @abstractmethod
    def pay(self, amount):     # contract — every child MUST implement this
        pass
 
class UpiPayment(PaymentGateway):
    def pay(self, amount):
        print(f"Paid {amount} via UPI")
 
class CreditCardPayment(PaymentGateway):
    def pay(self, amount):
        print(f"Paid {amount} via Credit Card")
 
# Polymorphic usage
def checkout(method: PaymentGateway, amount):
    method.pay(amount)
 
checkout(UpiPayment(), 300)          # Paid 300 via UPI
checkout(CreditCardPayment(), 500)   # Paid 500 via Credit Card
 
# PaymentGateway()   # TypeError — can't instantiate abstract class

# ❌ WRONG — second replaces first
class Calc:
    def add(self, a, b): return a + b
    def add(self, a, b, c): return a + b + c  # overwrites above!
 
# ✅ Use default args or *args
class Calc:
    def add(self, *nums):
        return sum(nums)
 
c = Calc()
c.add(1, 2)       # 3
c.add(1, 2, 3)    # 6

class A: pass
class B(A): pass
class C(A): pass
class D(B, C): pass
 
print(D.__mro__)   # D → B → C → A → object

from collections import Counter, defaultdict
 
Counter("abracadabra")                    # char frequency dict
Counter(lst).most_common(k)              # top k elements
{k: v for k, v in Counter(s).items() if v > 1}  # only duplicates
 
freq = defaultdict(int)
freq[item] += 1                           # auto-init to 0, safe increment

lst[::-1]                                 # reverse list
sorted(lst, key=lambda x: (-x[1], x[0])) # sort by value desc, key asc
list(set(lst))                            # remove duplicates (order lost)
[x for x in lst if x > 0]               # filter positives
 
# Flatten nested list
[x for sub in nested for x in sub]
 
# Running max via accumulate
import itertools
list(itertools.accumulate(lst, max))
 
# Partition list
evens = [x for x in lst if x % 2 == 0]
odds  = [x for x in lst if x % 2 != 0]

''.join(sorted(word))                     # anagram key
s[::-1] == s                             # palindrome check
' '.join(s.split())                      # normalize whitespace
sum(c.isdigit() for c in s)             # count digits in string
 
Counter(s1) == Counter(s2)               # anagram check
len(set(s)) == len(s)                    # all unique chars?

d.get(k, 0)                              # safe get, no KeyError
d.setdefault(k, []).append(v)            # group items
{v: k for k, v in d.items()}            # invert dict
sorted(d, key=d.get, reverse=True)       # sort keys by value desc
{k: v for k, v in d.items() if v > 0}  # filter dict entries
 
{**d1, **d2}                             # merge — d2 wins on conflicts
d1 | d2                                  # merge (Python 3.9+)

pow(base, exp, mod)                      # fast modular exponentiation O(log n)
divmod(17, 5)                            # (3, 2) — quotient + remainder
math.gcd(a, b)                           # greatest common divisor
math.isqrt(n)                            # integer square root (no float)
math.comb(n, r)                          # C(n,r) combinations
 
x & (x - 1) == 0                        # is power of 2?
bin(n).count('1')                        # count set bits
 
sum(int(d) for d in str(n))             # digit sum

list(zip(*matrix))                       # transpose matrix
[[row[i] for row in m] for i in range(len(m[0]))]  # transpose manual
[cell for row in matrix for cell in row] # flatten matrix
[[0] * m for _ in range(n)]             # n×m zero matrix — CORRECT way

import heapq
 
heapq.nlargest(k, lst)                  # k largest — O(n log k)
heapq.nsmallest(k, lst)                # k smallest
heapq.heappush(h, -val)                # max-heap trick (negate values)
heapq.heappush(h, (priority, counter, item))  # priority queue with tiebreaker

import bisect
 
bisect.bisect_left(arr, target)         # leftmost insertion point
bisect.bisect_right(arr, target) - 1   # rightmost occurrence index
# Count elements in range [lo, hi]:
bisect.bisect_right(arr, hi) - bisect.bisect_left(arr, lo)

from collections import defaultdict, deque
 
graph = defaultdict(list)
graph[u].append(v)                       # build adjacency list
 
# BFS shortest path
dist = {start: 0}
q = deque([start])
while q:
    n = q.popleft()
    for nb in graph[n]:
        if nb not in dist:
            dist[nb] = dist[n] + 1
            q.append(nb)

import itertools
 
list(itertools.combinations(lst, r))     # C(n,r) — order doesn't matter
list(itertools.permutations(lst, r))     # P(n,r) — order matters
list(itertools.product(a, b))           # cartesian product
list(itertools.chain(*nested))           # flatten one level
list(itertools.accumulate(lst))          # prefix sums
list(itertools.islice(gen, k))          # first k items from any iterator

# ❌ BUG — list is shared across ALL calls
def append_to(element, to=[]):
    to.append(element)
    return to
 
append_to(1)   # [1]
append_to(2)   # [1, 2] ← NOT [2]!
 
# ✅ FIX
def append_to(element, to=None):
    if to is None:
        to = []
    to.append(element)
    return to

# ❌ BUG — all lambdas share same 'i' variable
funcs = [lambda: i for i in range(5)]
[f() for f in funcs]     # [4, 4, 4, 4, 4]
 
# ✅ FIX — capture current value
funcs = [lambda i=i: i for i in range(5)]
[f() for f in funcs]     # [0, 1, 2, 3, 4]

# ❌ BUG — all rows are the SAME list object
grid = [[0] * 3] * 3
grid[0][0] = 1
print(grid)   # [[1,0,0], [1,0,0], [1,0,0]] — all rows changed!
 
# ✅ FIX
grid = [[0] * 3 for _ in range(3)]
grid[0][0] = 1
print(grid)   # [[1,0,0], [0,0,0], [0,0,0]] — only first row

# ❌ DANGEROUS — skips elements unpredictably
for x in lst:
    if x % 2 == 0:
        lst.remove(x)
 
# ❌ DANGEROUS — RuntimeError on dict
for k in d:
    if d[k] > 1: del d[k]
 
# ✅ FIX — iterate over copy
for x in lst[:]:
    if x % 2 == 0: lst.remove(x)
 
for k in list(d.keys()):
    if d[k] > 1: del d[k]
 
# ✅ BETTER — use comprehension
lst = [x for x in lst if x % 2 != 0]
d   = {k: v for k, v in d.items() if v <= 1}

lst = [3, 1, 2]
lst.sort()              # IN PLACE, returns None
new = sorted(lst)       # returns NEW list, original unchanged
 
lst = [3, 1, 2].sort()  # ❌ lst = None!
lst = sorted([3, 1, 2]) # ✅ correct

[1, 2, 3] == [1, 2, 3]   # True  — value comparison ✅
[1, 2, 3] is [1, 2, 3]   # False — different objects
 
# Use 'is' ONLY for None, True, False:
if x is None: ...
if flag is True: ...
 
# Integer caching trap (-5 to 256):
a = 256; b = 256; a is b   # True  — CPython caches these
a = 257; b = 257; a is b   # False — outside cache range
# Rule: NEVER use 'is' to compare integers or strings

0.1 + 0.2 == 0.3          # False! (floating point precision)
0.1 + 0.2                  # 0.30000000000000004
 
import math
math.isclose(0.1 + 0.2, 0.3)   # True ✅

# ❌ O(n²) — creates new string object every iteration
result = ""
for char in data:
    result += char
 
# ✅ O(n) — collect then join once
parts = []
for char in data:
    parts.append(char)
result = ''.join(parts)

isinstance(True, int)    # True
True + True              # 2
sum([True, False, True]) # 2 — counts True values!
 
# Useful pattern: count True values in list
booleans = [True, False, True, True]
sum(booleans)            # 3

import copy
 
original = [[1, 2], [3, 4]]
shallow  = original.copy()     # or original[:]
shallow[0].append(99)
print(original)                # [[1, 2, 99], [3, 4]] — modified!
 
deep = copy.deepcopy(original)
deep[0].append(100)
print(original)                # unchanged ✅

# ── Two Sum ───────────────────────────────────────────────────
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if target - num in seen:
            return [seen[target - num], i]
        seen[num] = i
    # Time: O(n), Space: O(n)
 
# ── Sliding Window — Longest No-Repeat Substring ──────────────
def longest_no_repeat(s):
    char_idx = {}
    left = max_len = 0
    for right, ch in enumerate(s):
        if ch in char_idx and char_idx[ch] >= left:
            left = char_idx[ch] + 1
        char_idx[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len
    # Time: O(n), Space: O(1)
 
# ── Binary Search ─────────────────────────────────────────────
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2   # avoids overflow
        if arr[mid] == target: return mid
        elif arr[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1
 
# ── BFS Shortest Path ─────────────────────────────────────────
from collections import deque
def bfs(graph, start, end):
    queue = deque([(start, [start])])
    visited = {start}
    while queue:
        node, path = queue.popleft()
        if node == end: return path
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                queue.append((nb, path + [nb]))
    return []
 
# ── Backtracking — All Subsets ────────────────────────────────
def subsets(nums):
    result = []
    def bt(start, curr):
        result.append(curr[:])             # copy — not reference!
        for i in range(start, len(nums)):
            curr.append(nums[i])
            bt(i + 1, curr)
            curr.pop()
    bt(0, [])
    return result
 
# ── DP — Coin Change ──────────────────────────────────────────
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1
 
# ── LRU Cache ─────────────────────────────────────────────────
from collections import OrderedDict
class LRUCache:
    def __init__(self, cap):
        self.cache = OrderedDict()
        self.cap = cap
    def get(self, key):
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key, val):
        if key in self.cache: self.cache.move_to_end(key)
        self.cache[key] = val
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)  # evict LRU (first item)
 
# ── Kadane's Algorithm — Max Subarray ─────────────────────────
def max_subarray(nums):
    max_sum = curr = nums[0]
    for n in nums[1:]:
        curr = max(n, curr + n)
        max_sum = max(max_sum, curr)
    return max_sum
    # Time: O(n), Space: O(1)
 
# ── Merge Intervals ───────────────────────────────────────────
def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged
 
# ── Reverse Linked List ───────────────────────────────────────
def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev
 
# ── Tree Max Depth ────────────────────────────────────────────
def max_depth(root):
    if not root: return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# ── Union Find ────────────────────────────────────────────────
class UF:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        if self.p[x] != x: self.p[x] = self.find(self.p[x])  # path compression
        return self.p[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        self.p[px] = py
        return True
 
# ── Trie ──────────────────────────────────────────────────────
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
 
class Trie:
    def __init__(self): self.root = TrieNode()
    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True
 
# ── Monotonic Stack — Next Greater Element ────────────────────
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                             # stack of indices
    for i, val in enumerate(nums):
        while stack and nums[stack[-1]] < val:
            result[stack.pop()] = val
        stack.append(i)
    return result
 
# ── Prefix Sum — Subarray Sum = K ────────────────────────────
def subarray_sum_k(nums, k):
    count = prefix = 0
    freq = {0: 1}                          # empty prefix seen once
    for num in nums:
        prefix += num
        count += freq.get(prefix - k, 0)
        freq[prefix] = freq.get(prefix, 0) + 1
    return count
 
# ── Cycle Detection — Fast & Slow ────────────────────────────
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow == fast: return True
    return False
 
# ── Topological Sort — Kahn's Algorithm ──────────────────────
from collections import deque
def topo_sort(n, edges):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1
    queue = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nb in graph[node]:
            indegree[nb] -= 1
            if indegree[nb] == 0: queue.append(nb)
    return order if len(order) == n else []   # empty list = cycle exists

# Stack (LIFO) — efficient with list
stack = []
stack.append(x)     # push  O(1)
stack.pop()         # pop   O(1)
stack[-1]           # peek  O(1)
 
# Queue (FIFO) — NEVER use list.pop(0)
from collections import deque
q = deque()
q.append(x)         # enqueue  O(1)
q.popleft()         # dequeue  O(1)
# list.pop(0) is O(n) — every element shifts left
 
# Slicing
lst[2:5]            # [2,3,4] — O(b-a)
lst[::-1]           # reverse  — creates NEW list
lst[-3:]            # last 3 elements
 
# ⚠️ Traps
grid = [[0]*3]*3            # ❌ shared rows
grid = [[0]*3 for _ in range(3)]  # ✅ independent rows
 
result = [3,1,2].sort()     # ❌ result = None
result = sorted([3,1,2])    # ✅ returns new list

# Must-know patterns
d.get(k, default)                        # never KeyError
d.setdefault(k, []).append(v)            # group-by pattern
Counter(lst).most_common(k)             # top k frequent
 
# defaultdict
from collections import defaultdict
adj = defaultdict(list)                  # graph adjacency list
freq = defaultdict(int)                  # frequency counter
 
# ⚠️ Traps
{True: 'a', 1: 'b'}    # {True: 'b'} — True == 1 == same key!
d = {}                  # empty dict, NOT empty set — use set() for set
 
# Modify while iterating
for k in list(d.keys()):  # ✅ copy keys first
    if condition: del d[k]

empty = set()            # NOT {} — that's an empty dict!
 
s.add(x)                 # O(1) avg
s.discard(x)             # O(1), no error if missing
s.remove(x)              # O(1), KeyError if missing
x in s                   # O(1) — the main reason to use set
 
s1 & s2                  # intersection
s1 | s2                  # union
s1 - s2                  # difference (in s1, not s2)
s1 ^ s2                  # symmetric difference
 
# ⚠️ Only hashable types — no lists or dicts in sets
visited = set()
visited.add((r, c))      # ✅ tuples are hashable
# visited.add([r, c])    # ❌ TypeError

from collections import deque
 
d = deque([1, 2, 3])
d.append(4)              # right O(1)
d.appendleft(0)          # left  O(1)
d.pop()                  # right O(1)
d.popleft()              # left  O(1) ← the whole point
 
d = deque(maxlen=3)      # circular buffer — auto-drops oldest
d.append(1); d.append(2); d.append(3)
d.append(4)              # deque([2,3,4]) — 1 dropped
 
# ⚠️ Random access d[i] is O(n) — use list if you need indexing

import heapq
 
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heap[0]                  # 1 — peek min, O(1)
heapq.heappop(heap)      # 1 — remove min, O(log n)
 
nums = [5, 3, 8, 1, 2]
heapq.heapify(nums)      # O(n) — in-place, modifies original!
 
# Max-heap: negate values
heapq.heappush(h, -val)
largest = -heapq.heappop(h)
 
# Priority queue with tiebreaker (avoids comparison errors on equal priority)
import itertools
counter = itertools.count()
heapq.heappush(pq, (priority, next(counter), item))
 
# ⚠️ heapify modifies the list in-place
# ⚠️ No decrease-key — push new entry and skip stale ones in Dijkstra

lst = [1, 2, 3]
 
# What a for loop actually does:
_it = iter(lst)             # calls lst.__iter__()
while True:
    try:
        x = next(_it)       # calls _it.__next__()
        print(x)
    except StopIteration:
        break
 
# Test: is it an iterator or just iterable?
lst = [1, 2, 3]
hasattr(lst, '__iter__')    # True  — iterable
hasattr(lst, '__next__')    # False — NOT an iterator
 
it = iter(lst)
hasattr(it, '__iter__')     # True  — also iterable
hasattr(it, '__next__')     # True  — iterator
 
# Iterators are one-use
it = iter([1, 2, 3])
list(it)                    # [1, 2, 3]
list(it)                    # [] — exhausted!
 
# Iterables are reusable
lst = [1, 2, 3]
list(lst)                   # [1, 2, 3]
list(lst)                   # [1, 2, 3] — fresh iterator each time

# Generator function — uses yield instead of return
def count_up(n):
    i = 1
    while i <= n:
        yield i         # PAUSE here, return value to caller
        i += 1          # RESUME here on next next() call
 
gen = count_up(3)
next(gen)               # 1
next(gen)               # 2
next(gen)               # 3
# next(gen)             # StopIteration
 
# Generator expression — lazy list comprehension
squares = (x**2 for x in range(1_000_000))   # no memory used yet!
next(squares)           # 0 — computed on demand
 
# Memory comparison
import sys
sys.getsizeof([x**2 for x in range(10000)])   # ~87,624 bytes
sys.getsizeof((x**2 for x in range(10000)))   # ~112 bytes
 
# yield from — delegate to sub-generator
def flatten(nested):
    for item in nested:
        if isinstance(item, (list, tuple)):
            yield from flatten(item)
        else:
            yield item
 
list(flatten([1, [2, [3, 4]], 5]))   # [1, 2, 3, 4, 5]

def read_large_file(path):
    with open(path) as f:
        for line in f:
            yield line.strip()
 
for line in read_large_file('10gb.log'):
    if 'ERROR' in line:
        print(line)        # only one line in memory at a time

import functools
 
def my_decorator(func):
    @functools.wraps(func)          # preserves __name__, __doc__
    def wrapper(*args, **kwargs):
        print("before")
        result = func(*args, **kwargs)
        print("after")
        return result               # always return!
    return wrapper
 
@my_decorator                       # equivalent to: say_hi = my_decorator(say_hi)
def say_hi(name):
    print(f"Hi {name}!")
 
say_hi("Alice")
# before
# Hi Alice!
# after

def retry(max_attempts=3, delay=1.0):
    def decorator(func):
        @functools.wraps(func)
        def wrapper(*args, **kwargs):
            for attempt in range(1, max_attempts + 1):
                try:
                    return func(*args, **kwargs)
                except Exception as e:
                    if attempt == max_attempts: raise
                    print(f"Attempt {attempt} failed. Retrying...")
                    import time; time.sleep(delay)
        return wrapper
    return decorator
 
@retry(max_attempts=3, delay=0.5)
def call_api(url):
    ...

class Circle:
    def __init__(self, radius):
        self._radius = radius
 
    @property
    def radius(self):               # getter — access as attribute
        return self._radius
 
    @radius.setter
    def radius(self, value):        # setter — validates on assignment
        if value < 0: raise ValueError("Negative radius")
        self._radius = value
 
    @property
    def area(self):                 # read-only computed property
        import math
        return math.pi * self._radius ** 2
 
c = Circle(5)
c.radius         # 5   — calls getter
c.radius = 10   # calls setter (with validation)
c.area           # 314.159...
# c.area = 5    # AttributeError — no setter defined
 
 
class Pizza:
    def __init__(self, ingredients):
        self.ingredients = ingredients
 
    @classmethod
    def margherita(cls):            # factory method — alternative constructor
        return cls(['mozzarella', 'tomatoes'])
 
    @staticmethod
    def is_vegetarian(ingredients): # utility — no self or cls needed
        return 'pepperoni' not in ingredients
 
p = Pizza.margherita()              # no need to call __init__ directly
 
 
import functools
 
@functools.cache                    # unlimited memoization (Python 3.9+)
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
 
fib(50)                             # instant — O(n) with cache vs O(2^n) without
 
fib.cache_info()                    # CacheInfo(hits=48, misses=51, ...)
fib.cache_clear()                   # bust the cache
 
 
from dataclasses import dataclass, field
 
@dataclass
class Employee:
    name:   str
    dept:   str
    salary: float
    skills: list = field(default_factory=list)  # correct mutable default
 
# Auto-generates: __init__, __repr__, __eq__
e1 = Employee("Alice", "Eng", 120_000)
e2 = Employee("Alice", "Eng", 120_000)
e1 == e2    # True — compares by value
 
@dataclass(frozen=True)             # immutable — can be used as dict key
class Point:
    x: float
    y: float

@outer   # applied second (outermost layer)
@inner   # applied first  (innermost layer)
def func(): pass
# Equivalent to: func = outer(inner(func))
# When called: outer's wrapper runs first → calls inner's wrapper → calls func

# Pattern A — Converging (opposite ends)
def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target: return [left, right]
        elif s < target: left += 1
        else: right -= 1
    return []
 
# Pattern B — Fast & Slow (same direction)
def remove_duplicates(nums):
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
 
# Pattern C — Floyd's Cycle Detection
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast: return True
    return False

# Fixed size
def max_sum_subarray(nums, k):
    window = sum(nums[:k])
    max_sum = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i-k]
        max_sum = max(max_sum, window)
    return max_sum
 
# Variable size
def min_subarray_len(target, nums):
    left = curr = 0
    min_len = float('inf')
    for right in range(len(nums)):
        curr += nums[right]
        while curr >= target:
            min_len = min(min_len, right - left + 1)
            curr -= nums[left]
            left += 1
    return min_len if min_len != float('inf') else 0

# Classic
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1
 
# Binary search on ANSWER SPACE — "minimize the maximum"
def ship_within_days(weights, days):
    def can_ship(capacity):
        day_count, load = 1, 0
        for w in weights:
            if load + w > capacity:
                day_count += 1
                load = w
            else:
                load += w
        return day_count <= days
 
    left, right = max(weights), sum(weights)
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid): right = mid
        else: left = mid + 1
    return left

from collections import deque
 
# BFS — level-by-level (shortest path, level order)
def bfs_levels(root):
    if not root: return []
    result, queue = [], deque([root])
    while queue:
        level = []
        for _ in range(len(queue)):       # process entire level
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result
 
# DFS — grid flood fill
def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0
    def dfs(r, c):
        if r<0 or r>=rows or c<0 or c>=cols or grid[r][c]!='1': return
        grid[r][c] = '#'                  # mark visited
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r+dr, c+dc)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count

# Universal template
def backtrack(start, current, result, choices):
    result.append(current[:])             # ← copy, not reference!
    for i in range(start, len(choices)):
        current.append(choices[i])        # choose
        backtrack(i + 1, current, result, choices)
        current.pop()                     # undo
 
# Combination sum (can reuse elements)
def combination_sum(candidates, target):
    result = []
    candidates.sort()
    def bt(start, curr, remaining):
        if remaining == 0:
            result.append(curr[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining: break  # pruning
            curr.append(candidates[i])
            bt(i, curr, remaining - candidates[i])  # i not i+1 = reuse allowed
            curr.pop()
    bt(0, [], target)
    return result

# Top-down (memoization)
import functools
 
@functools.cache
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)
 
# Bottom-up (tabulation)
def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1
 
# LCS — 2D DP
def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
 
# Knapsack (iterate weight BACKWARDS for 0/1 variant)
def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for i in range(len(weights)):
        for w in range(capacity, weights[i]-1, -1):   # ← backwards!
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

# Next greater element — decreasing stack
def next_greater(nums):
    result = [-1] * len(nums)
    stack = []
    for i, val in enumerate(nums):
        while stack and nums[stack[-1]] < val:
            result[stack.pop()] = val     # val is next greater for popped index
        stack.append(i)
    return result
    # Time: O(n) — each element pushed/popped at most once
 
# Sliding window max — monotonic deque
from collections import deque
def sliding_window_max(nums, k):
    result, dq = [], deque()
    for i in range(len(nums)):
        while dq and dq[0] < i - k + 1: dq.popleft()   # out of window
        while dq and nums[dq[-1]] < nums[i]: dq.pop()   # smaller, useless
        dq.append(i)
        if i >= k - 1: result.append(nums[dq[0]])
    return result

from collections import Counter, defaultdict, deque, OrderedDict
from itertools import combinations, permutations, product, accumulate, chain, islice
import heapq, bisect, math, functools, sys
 
sys.setrecursionlimit(10**6)    # set this before deep recursion problems