Python Tricks for Competitive Programming: The Matrix of Speed

The Quest Begins (The “Why”)

I still remember the first time I sat down for a Codeforces round, heart pounding like I was about to face the final boss in Dark Souls. The problem was simple: given an array, answer a bunch of range‑sum queries. I wrote a straightforward loop, summed each slice, and watched my solution choke on the largest test case. My rating plummeted, and I felt like I’d just spent an hour polishing a sword that turned out to be a butter knife.

That moment sparked a question: What hidden weapons does Python have that most of us never pull out of the inventory? I dove into the docs, experimented in the REPL, and uncovered a few tricks that felt like discovering a secret cheat code. Today I’m sharing three of those gems—features that look innocent at first glance but can turn a TLE (Time Limit Exceeded) into an AC (Accepted) in a blink.

The Revelation (The Insight)

1. Binary Search on Custom Objects with bisect

Most tutorials show bisect_left(arr, x) working on a plain list of numbers. In competitive programming we often need to search on objects—say, a list of points sorted by their x coordinate. The naïve approach is to extract the keys into a separate list, search, then map back. That’s extra O(N) memory and extra code.

The gotcha? If you try bisect_left(points, target_x) on a list of custom objects without defining __lt__, Python raises a TypeError: '<' not supported between instances of 'Point' and 'int'. The fix is simple: make the objects comparable, or search on a list of tuples where the first element is the key.

Why it matters: a true O(log N) search keeps your solution fast even when N = 2·10⁵ and you have dozens of queries.

2. Running Aggregates with itertools.accumulate

We all know how to compute prefix sums with a for‑loop. But what about prefix XORs, prefix products modulo a prime, or even a running maximum? Writing a loop each time is tedious and error‑prone.

Enter itertools.accumulate. It takes an iterable and a binary function (default is addition) and yields the running results. The gotcha? If you forget to convert the iterator to a list (or consume it twice), you’ll get an empty result the second time—because iterators are exhausted after one pass.

Why it matters: a one‑liner replaces boilerplate, reduces bug surface, and reads like mathematical notation.

3. O(1) End Operations with collections.deque

Lists are great, but pop(0) or insert(0, x) are O(N) because every element must shift. In problems that need a sliding window, a queue for BFS, or a palindrome check, those linear shifts become the bottleneck.

The gotcha? If you treat a deque like a list and call index(x), you still get O(N) search—deque only shines at the ends. But for pure push/pop at both sides, it’s unbeatable.

Why it matters: swapping a list for a deque can cut your runtime from O(N²) to O(N) in scenarios like the classic “minimum in every subarray of size K” problem.

Wielding the Power (Code & Examples)

1. Binary Search on Points

Before – Linear Scan (O(NQ))

# points = [(x, y), ...] sorted by x
def count_left_of_x(points, x):
    cnt = 0
    for px, _ in points:
        if px < x:
            cnt += 1
        else:
            break
    return cnt

After – bisect_left on a key list (O(log N per query))

from bisect import bisect_left

# Prepare a list of just the x‑coordinates
xs = [p[0] for p in points]   # O(N) once

def count_left_of_x_fast(points, xs, x):
    # bisect_left returns the insertion point -> number of elements < x
    return bisect_left(xs, x)

# Usage
print(count_left_of_x_fast(points, xs, 10))

Gotcha: If you forget to build xs and call bisect_left(points, x), you’ll hit the TypeError mentioned earlier.

2. Prefix XOR with accumulate

Before – Manual Loop

def prefix_xor(arr):
    res = []
    cur = 0
    for v in arr:
        cur ^= v
        res.append(cur)
    return res

After – One‑liner with accumulate

from itertools import accumulate
import operator

def prefix_xor_fast(arr):
    return list(accumulate(arr, operator.xor))

# Example
print(prefix_xor_fast([5, 1, 7, 3]))  # -> [5, 4, 3, 0]

Gotcha: Using accumulate(arr) without specifying operator.xor defaults to addition, giving you a prefix sum instead of XOR.

3. Sliding Window Minimum with deque

Before – Brute Force (O(N·K))

def sliding_min_brute(arr, k):
    return [min(arr[i:i+k]) for i in range(len(arr)-k+1)]

After – Monotonic Queue (O(N))

from collections import deque

def sliding_min_fast(arr, k):
    dq = deque()          # stores indices, values increasing
    result = []
    for i, v in enumerate(arr):
        # Remove indices that are out of the window
        if dq and dq[0] <= i - k:
            dq.popleft()
        # Maintain monotonicity: pop larger elements from the right
        while dq and arr[dq[-1]] >= v:
            dq.pop()
        dq.append(i)
        # The front holds the minimum for the current window
        if i >= k - 1:
            result.append(arr[dq[0]])
    return result

# Example
print(sliding_min_fast([2, 1, 3, 4, 6, 3, 8, 9, 10, 12, 56], 4))
# -> [1, 1, 3, 3, 3, 3, 8, 9, 10]

Gotcha: If you accidentally use dq.index(min_val) to fetch the minimum, you lose the O(1) advantage—deque only guarantees O(1) at the ends.

Why This New Power Matters

Mastering these tricks does more than shave a few milliseconds off your runtime; it reshapes how you think about problems.

• Binary search on custom data teaches you to leverage ordering without duplicating structures—a skill that translates to database indexing, GIS queries, and more.
• accumulate turns imperative loops into declarative expressions, making your code read like math and reducing the chance of off‑by‑one errors.
• deque reinforces the importance of choosing the right abstract data type; the same mindset helps you pick heaps, tries, or segment trees when the problem scales.

When you start seeing the language as a toolbox of specialized instruments rather than just a syntax, you stop fighting the interpreter and start letting it work for you. That shift is what turns a competent coder into a problem‑solving ninja—ready to face any boss round, whether it’s on Codeforces, LeetCode, or a hackathon marathon.

Your Turn

Pick one of the three tricks above, implement it in a problem you’ve been stuck on, and notice the difference. Then, share your before/after code in the comments—let’s learn from each other’s quests!

Happy coding, and may your submissions always be AC! 🚀