Python Tricks

from collections import Counter

# Basic frequency counting
nums = [1, 2, 2, 3, 3, 3]
count = Counter(nums)          # Counter({3: 3, 2: 2, 1: 1})

# Top k frequent
count.most_common(2)           # [(3, 3), (2, 2)]

# Arithmetic operations
a = Counter("aabbc")
b = Counter("abc")
a - b                          # Counter({'a': 1, 'b': 1})
a + b                          # Counter({'a': 3, 'b': 3, 'c': 2})
a & b                          # Intersection: Counter({'a': 1, 'b': 1, 'c': 1})
a | b                          # Union: Counter({'a': 2, 'b': 2, 'c': 1})

# Check if anagram
def is_anagram(s, t):
    return Counter(s) == Counter(t)

# Top K Frequent Elements (LC 347)
def topKFrequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

from collections import defaultdict

# Auto-initialize with default value
graph = defaultdict(list)       # missing key -> []
graph[0].append(1)              # no KeyError

counts = defaultdict(int)       # missing key -> 0
counts['a'] += 1                # no need to check existence

groups = defaultdict(set)       # missing key -> set()

# Building an adjacency list
def build_graph(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    return graph

# Group Anagrams (LC 49)
def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))    # or use Counter -> tuple
        groups[key].append(s)
    return list(groups.values())

from collections import deque

# O(1) operations on both ends
dq = deque()
dq.append(1)         # right: [1]
dq.appendleft(0)     # left:  [0, 1]
dq.pop()             # right: returns 1, deque is [0]
dq.popleft()         # left:  returns 0, deque is []

# BFS template
def bfs(graph, start):
    queue = deque([start])
    visited = {start}
    while queue:
        node = queue.popleft()       # O(1) vs list.pop(0) which is O(n)!
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# Sliding window maximum (LC 239)
def maxSlidingWindow(nums, k):
    dq = deque()       # stores indices, front = max
    result = []
    for i, num in enumerate(nums):
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:           # remove out-of-window
            dq.popleft()
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

import heapq

# Basic operations
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappop(heap)             # returns 1 (smallest)

# Heapify existing list: O(n)
nums = [5, 3, 1, 4, 2]
heapq.heapify(nums)             # nums is now a min-heap

# Peek without popping
smallest = heap[0]

# MAX heap trick: negate all values
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
biggest = -heapq.heappop(max_heap)   # returns 5

# nlargest / nsmallest shortcuts
heapq.nlargest(3, nums)         # top 3 largest
heapq.nsmallest(3, nums)        # top 3 smallest

# Kth Largest Element (LC 215)
def findKthLargest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for num in nums[k:]:
        if num > heap[0]:
            heapq.heapreplace(heap, num)  # pop + push in one operation
    return heap[0]

# Merge K Sorted Lists (LC 23)
def mergeKLists(lists):
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))

    dummy = curr = ListNode(0)
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

# Tuples are compared element by element
# (priority, tiebreaker, value)
heap = []
heapq.heappush(heap, (2, 0, "low"))
heapq.heappush(heap, (1, 1, "high"))
heapq.heappop(heap)   # (1, 1, "high") - smallest first element

import bisect

arr = [1, 3, 5, 7, 9]

# bisect_left: leftmost position to insert (first element >= target)
bisect.bisect_left(arr, 5)     # 2  (index of 5)
bisect.bisect_left(arr, 4)     # 2  (would go before 5)

# bisect_right: rightmost position to insert (first element > target)
bisect.bisect_right(arr, 5)    # 3  (after 5)

# insort: insert while maintaining sort order
bisect.insort(arr, 4)          # arr = [1, 3, 4, 5, 7, 9]

# Count elements in range [lo, hi]
def count_in_range(arr, lo, hi):
    left = bisect.bisect_left(arr, lo)
    right = bisect.bisect_right(arr, hi)
    return right - left

# Binary search for exact match
def binary_search(arr, target):
    i = bisect.bisect_left(arr, target)
    return i < len(arr) and arr[i] == target

from itertools import combinations, permutations, product, accumulate, groupby

# Combinations: choose k from n (order doesn't matter)
list(combinations([1,2,3], 2))       # [(1,2), (1,3), (2,3)]

# Permutations: arrange k from n (order matters)
list(permutations([1,2,3], 2))       # [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]

# Product: cartesian product (nested loops)
list(product([0,1], repeat=3))       # all 3-bit binary numbers
# [(0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1)]

# Accumulate: prefix sums (and more)
list(accumulate([1,2,3,4]))          # [1, 3, 6, 10]
# With custom function
list(accumulate([3,1,4,1], max))     # [3, 3, 4, 4] running max

# Groupby: group consecutive identical elements
data = sorted([('a',1),('b',2),('a',3)], key=lambda x: x[0])
for key, group in groupby(data, key=lambda x: x[0]):
    print(key, list(group))
# a [('a',1), ('a',3)]
# b [('b',2)]

# Generate all subsets using combinations
def subsets(nums):
    result = []
    for k in range(len(nums) + 1):
        result.extend(combinations(nums, k))
    return result

# Prefix sum array for range queries
from itertools import accumulate
prefix = list(accumulate(nums, initial=0))
# Sum of nums[i:j] = prefix[j] - prefix[i]

from functools import lru_cache

# Fibonacci - DP with zero effort
@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

# Grid DP: Unique Paths (LC 62)
@lru_cache(maxsize=None)
def uniquePaths(m, n):
    if m == 1 or n == 1:
        return 1
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

# Longest Common Subsequence (LC 1143)
def longestCommonSubsequence(text1, text2):
    @lru_cache(maxsize=None)
    def dp(i, j):
        if i == len(text1) or j == len(text2):
            return 0
        if text1[i] == text2[j]:
            return 1 + dp(i + 1, j + 1)
        return max(dp(i + 1, j), dp(i, j + 1))
    return dp(0, 0)

from functools import reduce

# Product of all elements
product = reduce(lambda a, b: a * b, [1, 2, 3, 4])  # 24

# Flatten nested list
flat = reduce(lambda a, b: a + b, [[1,2], [3,4], [5]])  # [1,2,3,4,5]
# Better: [x for sublist in nested for x in sublist]

# WRONG - all rows share the same list object!
matrix = [[0] * 3] * 3
matrix[0][0] = 1
# matrix is now [[1,0,0], [1,0,0], [1,0,0]]  <-- ALL rows changed

# CORRECT - each row is an independent list
matrix = [[0] * 3 for _ in range(3)]
matrix[0][0] = 1
# matrix is now [[1,0,0], [0,0,0], [0,0,0]]  <-- only row 0 changed

# Swap variables
a, b = b, a

# Infinity
pos_inf = float('inf')
neg_inf = float('-inf')

# Flatten 2D list
flat = [x for row in matrix for x in row]

# Conditional expression
x = a if condition else b

# Check all / any
all(x > 0 for x in nums)      # True if all positive
any(x > 0 for x in nums)      # True if at least one positive

# Dictionary comprehension
squares = {x: x**2 for x in range(5)}

# Set operations
a = {1, 2, 3}
b = {2, 3, 4}
a | b    # union:        {1, 2, 3, 4}
a & b    # intersection: {2, 3}
a - b    # difference:   {1}
a ^ b    # symmetric:    {1, 4}

# Unpack with *
first, *middle, last = [1, 2, 3, 4, 5]
# first=1, middle=[2,3,4], last=5

# Walrus operator (Python 3.8+)
while (line := input()) != "quit":
    process(line)

# Count digits
from math import log10, floor
digits = floor(log10(n)) + 1 if n > 0 else 1

# Reverse anything
"hello"[::-1]           # "olleh"
[1,2,3][::-1]           # [3, 2, 1]

# Divmod
quotient, remainder = divmod(17, 5)   # (3, 2)

# Multiple assignment
x = y = z = 0

# Chained comparison
if 0 <= x < n and 0 <= y < m:    # bounds check
    pass

# Math
abs(-5)                    # 5
max(a, b, c)               # largest
min(a, b, c)               # smallest
pow(2, 10)                 # 1024
pow(2, 10, 1000)           # 24 (modular exponentiation!)
sum(iterable)              # sum all elements
divmod(17, 5)              # (3, 2)

# Type conversion
int("42")                  # 42
str(42)                    # "42"
list("abc")                # ['a', 'b', 'c']
set([1,1,2])               # {1, 2}
tuple([1,2])               # (1, 2)
ord('a')                   # 97
chr(97)                    # 'a'

# Boolean checks
isinstance(x, int)         # type check
bool([])                   # False (empty collections are falsy)
bool([0])                  # True  (non-empty is truthy)

# Useful for interviews
float('inf')               # positive infinity
float('-inf')              # negative infinity

# WRONG
def append_to(element, target=[]):
    target.append(element)
    return target

append_to(1)   # [1]
append_to(2)   # [1, 2]  <-- BUG! Default list persists between calls

# CORRECT
def append_to(element, target=None):
    if target is None:
        target = []
    target.append(element)
    return target

# Creates 3 references to the SAME inner list
bad = [[0] * 3] * 3

# Creates 3 independent inner lists
good = [[0] * 3 for _ in range(3)]

# This also applies to other mutables
bad_dict = [{}] * 3        # 3 refs to same dict
good_dict = [{} for _ in range(3)]

# Python caches integers from -5 to 256
a = 256
b = 256
a is b    # True (cached)

a = 257
b = 257
a is b    # False (not cached)

# ALWAYS use == for value comparison, not 'is'

import copy

original = [[1, 2], [3, 4]]

shallow = original.copy()            # or list(original)
shallow[0][0] = 99
# original is now [[99, 2], [3, 4]]  <-- inner lists are shared!

original = [[1, 2], [3, 4]]
deep = copy.deepcopy(original)
deep[0][0] = 99
# original is still [[1, 2], [3, 4]]  <-- fully independent