The Matrix of Python: Tricks for Competitive Programming You Didn't Know

The Quest Begins (The “Why”)

I still remember the first time I tried to solve a problem that asked for the maximum sub‑array sum in a list of 200 000 integers. I wrote a naive double‑loop, watched the timer blow past the limit, and felt like I was trying to defeat a final boss with a wooden sword. After a few frustrating minutes of scrolling through editorial solutions, I kept seeing the same pattern: people were using a couple of Python tricks that made their code look almost… magical. I was curious, a little annoyed, and definitely motivated to uncover those hidden spells.

If you’ve ever stared at a timeout error and wondered “there has to be a better way”, you’re not alone. Competitive programming isn’t just about knowing algorithms; it’s about squeezing every ounce of speed out of the language you’re using. And Python, despite its reputation for being “slow”, has a few under‑utilized features that can turn a sluggish solution into a blazing‑fast one. Let’s go on a little treasure hunt and see what we can pull out of the language’s pocket.

The Revelation (The Insight)

1. The Walrus Operator (:=) – Inline Assignment

Most of us learned Python before 3.8, so the walrus operator still feels like a newcomer. It lets you assign a value inside an expression, which sounds trivial until you realize how many loops and comprehensions become one‑liners.

Gotcha: If you forget that the walrus returns the assigned value (not a boolean), you might end up with unexpected truthiness. For example, while (n := get_next()) works because get_next() returns the next item, and the loop stops when it returns a falsy value (like 0 or None).

Why it matters: In competitive programming you often need to read input until a sentinel value appears, or you want to compute a value and use it immediately in a condition. The walrus saves you an extra line and, more importantly, keeps the logic tight—less code means fewer places for bugs to hide.

2. itertools.accumulate – Prefix Sums on Steroids

When you need a running total (prefix sums) you might write something like:

pref = [0]
for x in arr:
    pref.append(pref[-1] + x)

It works, but it’s a bit noisy. itertools.accumulate does exactly that, and you can even plug in a custom function (like max for a running maximum).

Gotcha: The iterator returned by accumulate is lazy; if you accidentally treat it as a list and then try to index it multiple times, you’ll exhaust it. Wrap it in list() if you need random access, or iterate once.

Why it matters: Many DP problems reduce to prefix sums (range sum queries, cumulative frequency, etc.). Turning a three‑line loop into a single readable line not only saves typing time during a contest but also makes the intent crystal‑clear to anyone reading your code later.

3. bisect – Binary Search Without Reinventing the Wheel

Searching for the first element ≥ x in a sorted list is a classic task. Writing your own binary search is easy to get wrong (off‑by‑one errors are the usual suspects). The bisect module supplies bisect_left and bisect_right that do exactly that, in C speed.

Gotcha: Remember that bisect works on sorted sequences only. If you pass an unsorted list you’ll get nonsense results, and the module won’t warn you. Also, the functions return an index; if you need the actual element you have to index yourself (arr[idx]).

Why it matters: In problems involving order statistics, coordinate compression, or sweep line algorithms, you’ll be doing dozens of binary searches per test case. Using bisect cuts the constant factor dramatically, often turning a TLE into an AC.

Wielding the Power (Code & Examples)

Let’s see each trick in action, first with the “struggle” version and then the “victory” version.

Example 1 – Reading Until a Sentinel with Walrus

Struggle:

def read_until_zero():
    nums = []
    while True:
        line = input()
        if line == '0':
            break
        nums.append(int(line))
    return nums

Victory (walrus):

def read_until_zero():
    nums = []
    while (line := input()) != '0':
        nums.append(int(line))
    return nums

Notice how the loop condition does the input read and the check in one line. No extra break, no temporary variable hanging around. In a contest where you’re reading thousands of lines, that tiny reduction adds up.

Example 2 – Prefix Sums with accumulate

Struggle:

def prefix_sums(arr):
    pref = [0]
    for v in arr:
        pref.append(pref[-1] + v)
    return pref

Victory (accumulate):

from itertools import accumulate

def prefix_sums(arr):
    # accumulate returns an iterator; we prepend 0 for 1‑based indexing
    return [0] + list(accumulate(arr))

If you need a running maximum instead of a sum, just swap the function:

running_max = list(accumulate(arr, max))

Example 3 – Binary Search with bisect

Struggle (hand‑rolled binary search):

def lower_bound(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

Victory (bisect):

from bisect import bisect_left

def lower_bound(arr, x):
    return bisect_left(arr, x)

That’s it—one import, one function call, and you’re guaranteed to get the correct index every time, thanks to the battle‑tested CPython implementation.

Why This New Power Matters

Mastering these little‑known features does more than shave a few milliseconds off your runtime; it changes how you think about solving problems.

• Readability: When your code expresses intent directly (e.g., “take the running maximum”), reviewers and future you can grasp the algorithm at a glance. Less mental translation means fewer bugs.
• Speed: Built‑ins like accumulate and bisect run in C loops, which are often an order of magnitude faster than pure Python loops. In a tight contest, that’s the difference between a solution that passes and one that times out.
• Confidence: Knowing you have a reliable toolbox lets you focus on the algorithmic challenge rather than fighting language quirks. You start to see patterns (“this is a prefix sum problem”, “I need a lower bound”) and reach for the right tool instantly.

In short, these tricks turn Python from a “slow but readable” language into a silent partner that can keep up with C++ when you need it to.

Your Turn – A Mini‑Quest

I challenge you to take a problem you’ve solved before with a manual loop for prefix sums or a hand‑written binary search, and rewrite it using one of the tricks above. Share your before/after snippets in the comments, or tweet them with the hashtag #PythonCPTricks. Let’s see who can shave the most milliseconds off their runtime!

Happy coding, and may your bugs be few and your ACs many. 🚀