15. DSA Idioms & Gotchas

Essential Idioms

# ── Swap ─────────────────────────────────────────────────────────
a, b = b, a
arr[i], arr[j] = arr[j], arr[i]

# ── Infinity ─────────────────────────────────────────────────────
INF     = float("inf")
NEG_INF = float("-inf")
# Or use math.inf / -math.inf
dist = [math.inf] * n
best = -math.inf

# ── Recursion limit ───────────────────────────────────────────────
import sys
sys.setrecursionlimit(300_000)  # put at top of solution for deep DFS/trees

# ── Fast I/O (competitive programming) ───────────────────────────
import sys
input = sys.stdin.readline     # ~5x faster for large inputs

n         = int(input())
a, b      = map(int, input().split())
arr       = list(map(int, input().split()))
grid      = [list(map(int, input().split())) for _ in range(n)]
lines     = [input().strip() for _ in range(n)]  # read n raw lines
print(*arr)                    # print list without brackets: "1 2 3"
print('\n'.join(map(str, arr)))# one per line

from sys import stdout
stdout.write(str(result) + "\n")   # faster than print() for many outputs

# ── Circular index ────────────────────────────────────────────────
(i + 1) % n       # next index with wrap-around
(i - 1) % n       # previous index with wrap-around (Python: -1%n = n-1)

# ── Safe dict increment ───────────────────────────────────────────
d[key] = d.get(key, 0) + 1    # or use defaultdict(int)

# ── None as sentinel ──────────────────────────────────────────────
result = None
for x in arr:
    if condition(x):
        result = x
        break
if result is None:
    print("not found")

# ── Discard with _ ────────────────────────────────────────────────
for _, v in d.items():     # only care about values
    process(v)
for _ in range(k):         # repeat k times, don't need the index
    do_something()

# ── Dedup while preserving order ─────────────────────────────────
seen = set()
result = [x for x in arr if not (x in seen or seen.add(x))]

# ── Flatten one level ─────────────────────────────────────────────
flat = [x for row in matrix for x in row]
flat = list(chain.from_iterable(matrix))
flat = sum([[1,2],[3,4],[5]], [])     # [1,2,3,4,5] — flatten via sum (small lists only)

# ── Rotate list left by k ─────────────────────────────────────────
arr = arr[k:] + arr[:k]

# ── Check all equal / count distinct ──────────────────────────────
all_equal    = len(set(arr)) == 1
num_distinct = len(set(arr))

# ── Coordinate compress ───────────────────────────────────────────
rank = {v: i for i, v in enumerate(sorted(set(arr)))}
compressed = [rank[v] for v in arr]

# ── BFS template ──────────────────────────────────────────────────
from collections import deque
def bfs(graph, start):
    visited, q = {start}, deque([start])
    while q:
        node = q.popleft()
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb); q.append(nb)

# ── DFS with nonlocal ─────────────────────────────────────────────
def max_depth(root):
    result = 0
    def dfs(node, depth):
        nonlocal result
        if not node: return
        result = max(result, depth)
        dfs(node.left, depth+1); dfs(node.right, depth+1)
    dfs(root, 1); return result

Common Gotchas

# ❌ 1. Wrong 2D array init — all rows share same object
grid = [[0]*3]*3            # WRONG
grid[0][0] = 1              # changes ALL rows!
# ✅
grid = [[0]*3 for _ in range(3)]

# For arbitrary nested structures (not just uniform grids), a shallow
# copy still shares inner objects — use copy.deepcopy to fully clone:
import copy
original = [[1, 2], [3, 4]]
shallow  = original.copy()          # or original[:] — inner lists still shared!
shallow[0].append(99)               # mutates original[0] too!
deep     = copy.deepcopy(original)  # fully independent clone
deep[0].append(99)                  # original is untouched

# ❌ 2. list as default argument — shared across all calls
def bad(arr=[]):            # WRONG — arr persists between calls
    arr.append(1); return arr
# ✅
def good(arr=None):
    if arr is None: arr = []
    arr.append(1); return arr

# ❌ 3. O(n) queue using list.pop(0)
queue = []; queue.pop(0)    # O(n) — SLOW
# ✅
from collections import deque
q = deque(); q.popleft()    # O(1)

# ❌ 4. O(n²) string concatenation in loop
result = ""
for c in chars: result += c  # rebuilds string each iteration
# ✅
result = "".join(chars)       # O(n)

# ❌ 5. is vs == for value comparison
a = [1,2,3]; b = [1,2,3]
a is b       # False — different objects
a == b       # True  — same value
# Use 'is' only for singletons: None, True, False
if x is None: ...  # correct
if x is not None: ...

# ❌ 6. Forgetting backtrack snapshot
result.append(path)    # WRONG — mutable reference, will be empty at end
result.append(path[:]) # CORRECT — snapshot copy

# ❌ 7. Modifying a list while iterating
for x in arr:
    if x < 0: arr.remove(x)  # skips elements!
# ✅
arr = [x for x in arr if x >= 0]

# ❌ 8. float("inf") comparison surprise
float("inf") == float("inf")   # True
float("nan") == float("nan")   # False (NaN is not equal to itself)
import math
math.isnan(float("nan"))       # True — correct way to check

# ❌ 9. Integer division in Python 2 style
5 / 2    # 2.5 in Python 3 (not 2!)
5 // 2   # 2   — use // for floor division

# ✅ 10. Negative modulo — Python's is useful!
(i - 1) % n   # previous circular index — always in [0, n-1]

---