Interval & Math

Sort-then-merge is the standard O(n log n) approach to interval union.

a.sort()
res = [a[0]]
for s, e in a[1:]:
    if s <= res[-1][1]:
        res[-1][1] = max(res[-1][1], e)
    else:
        res.append([s, e])

Two intervals overlap iff neither ends before the other starts. Critical for scheduling.

def overlaps(a, b):
    return a[0] < b[1] and b[0] < a[1]

Sorting by end time is the greedy strategy for interval scheduling and activity selection.

intervals.sort(key=lambda x: x[1])

Transpose + reverse-rows rotates 90 degrees clockwise in-place. Classic matrix manipulation.

n = len(m)
for i in range(n):
    for j in range(i+1, n):
        m[i][j], m[j][i] = m[j][i], m[i][j]
for row in m:
    row.reverse()

Spiral traversal uses shrinking boundaries: top, bottom, left, right.

res = []
t, b, l, r = 0, len(m)-1, 0, len(m[0])-1
while t <= b and l <= r:
    for c in range(l, r+1): res.append(m[t][c])
    t += 1
    for c in range(t, b+1): res.append(m[c][r])
    r -= 1

Using first row/col as markers gives O(1) extra space for zero-setting.

row0 = any(m[0][j] == 0 for j in range(n))
col0 = any(m[i][0] == 0 for i in range(r))
for i in range(1, r):
    for j in range(1, n):
        if m[i][j] == 0:
            m[i][0] = m[0][j] = 0

Digit-square-sum with cycle detection (fast/slow or set) determines happiness.

def digit_sq_sum(n):
    s = 0
    while n:
        n, d = divmod(n, 10)
        s += d * d
    return s

Iterative binary exponentiation handles negative exponents. Same as pow(x, n).

def power(x, n):
    res = 1
    if n < 0: x, n = 1/x, -n
    while n:
        if n & 1: res *= x
        x *= x
        n >>= 1
    return res

The Euclidean algorithm is fundamental to number theory. O(log min(a,b)) complexity.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

Single-bit check via n & (n-1) == 0. Fastest power-of-two test.

n > 0 and n & (n - 1) == 0

XOR cancellation finds the element appearing an odd number of times. O(n) time, O(1) space — no hash map needed.

result = 0
for x in nums:
    result ^= x
# pairs cancel: a ^ a = 0, only unique remains

Powers of two have exactly one set bit. n & (n-1) clears the lowest set bit — if the result is zero, only one bit was set.

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

XOR marks differing bits, then Brian Kernighan's trick counts them in O(k) where k is the number of set bits.

xor = x ^ y
count = 0
while xor:
    xor &= xor - 1  # clear lowest set bit
    count += 1

Sort by start, then check if each interval starts before the previous one ends. Foundation for meeting rooms.

intervals.sort()
for i in range(1, len(intervals)):
    if intervals[i][0] < intervals[i-1][1]:
        return True  # overlap
return False

Heap tracks room end times. If the earliest-ending room is free, reuse it; otherwise allocate a new one.

import heapq
intervals.sort()
rooms = []  # min-heap of end times
for start, end in intervals:
    if rooms and rooms[0] <= start:
        heapq.heappop(rooms)  # reuse room
    heapq.heappush(rooms, end)
return len(rooms)

Sweep line converts intervals to +1/-1 events. Running sum gives concurrent count at any point. Alternative to heap approach.

events = []
for start, end in intervals:
    events.append((start, 1))   # open
    events.append((end, -1))    # close
events.sort()
cur = best = 0
for _, delta in events:
    cur += delta
    best = max(best, cur)