Fixing TLE: Reading Constraints and Cutting Time Complexity in Coding Interviews

Most “time limit exceeded” verdicts are not about clever algorithms you have never heard of. They come from two habits: not reading the constraints before writing code, and doing the same work over and over inside a loop. This article walks through how to turn the input limits into a target complexity, and then the handful of rewrites that remove most repeated work.

Start from the constraints, not the code

Before writing anything, underline the sizes in the statement: N, the number of queries Q, string lengths, value ranges. Multiply out what your first idea would cost. A common rule of thumb is that a compiled language does on the order of 10^8 simple operations per second, and CPython considerably fewer. That is only a rough guide, since memory access patterns and constant factors matter, but it is enough to rule ideas in or out.

Input size (roughly)	Usually fits	Usually does not
N ≤ 10–11	O(N!) — all permutations	—
N ≤ 20–25	O(2^N) or O(2^N · N) — all subsets, bitmask DP	O(N!)
N ≤ 500	O(N³)	O(N⁴)
N ≤ 5,000	O(N²)	O(N³)
N ≤ 2×10⁵	O(N log N)	O(N²)
N ≤ 10⁷	O(N) with a tight loop	O(N log N) in a slow language

Read the table in reverse too: if N is at most 20, the problem setter is probably inviting a subset enumeration, and if N is 2×10⁵, a quadratic solution was deliberately excluded. Constraints are a hint about the intended solution.

Queries change the arithmetic. With N = 10⁵ and Q = 10⁵, “scan the array per query” is O(N·Q) = 10¹⁰ even though each individual query looks linear and harmless.

Pattern 1: you are checking every pair

Two nested loops over the same array are the most common source of O(N²). The question to ask is: for a fixed i, what am I searching for among the j values? If the answer is “a specific value”, a hash map finds it in average O(1). If it is “something ordered”, sorting plus two pointers or binary search does it in O(log N) or amortized O(1).

def two_sum_naive(a, t):          # O(N^2)
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
            if a[i] + a[j] == t:
                return i, j
    return None

def two_sum_hash(a, t):           # O(N) average
    seen = {}
    for i, x in enumerate(a):
        if t - x in seen:
            return seen[t - x], i
        seen[x] = i
    return None

def two_sum_sorted(a, t):         # O(N log N), no hashing
    idx = sorted(range(len(a)), key=lambda k: a[k])
    i, j = 0, len(a) - 1
    while i < j:
        s = a[idx[i]] + a[idx[j]]
        if s == t:
            return tuple(sorted((idx[i], idx[j])))
        if s < t:
            i += 1
        else:
            j -= 1
    return None

a = [3, 8, -2, 7, 5]
print(two_sum_naive(a, 5), two_sum_sorted(a, 5), two_sum_hash(a, 5))
# (2, 3) (2, 3) (2, 3)

Note that the sorted version sorts indices rather than values, so it can still report original positions. Two pointers only work because the array is sorted: moving i right can only increase the sum, and moving j left can only decrease it, so each step safely discards one candidate.

Pattern 2: you recompute the same range

If a loop body contains sum(arr[l:r]), min(...) over a window, or a count over a sub-range, you are probably recomputing overlapping work. Two tools cover most cases.

Sliding window for a fixed-length (or monotonically moving) window: update the running value with what enters and what leaves.

def max_window_sum_naive(arr, k):   # O(N*k)
    best = float("-inf")
    for i in range(len(arr) - k + 1):
        best = max(best, sum(arr[i:i + k]))
    return best

def max_window_sum(arr, k):         # O(N)
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        best = max(best, window)
    return best

print(max_window_sum([-5, -1, -3, -2, -4], 2))   # -4

A detail that bites people: initializing best = 0 looks fine on the examples but returns 0 for an all-negative array. Initialize from the first window or negative infinity.

Prefix sums for arbitrary range-sum queries on a static array: prefix[i] holds the sum of the first i elements, and any range is a subtraction.

from itertools import accumulate

def range_sums(arr, queries):
    prefix = [0, *accumulate(arr)]
    return [prefix[r + 1] - prefix[l] for l, r in queries]

print(range_sums([2, 4, 1, 3, 5], [(0, 2), (1, 4), (3, 3)]))   # [7, 13, 3]

Prefix sums only work while the array does not change. If elements are updated between queries, a Fenwick tree or segment tree gives O(log N) per update and per query. Range minimum does not subtract the way sums do, so for static arrays use a sparse table, and for sliding windows use a monotonic deque.

Pattern 3: you search linearly for existence, frequency or rank

“Is x present?”, “how many times does x appear?” and “how many values are at most x?” all have better answers than a scan per question.

from collections import Counter
import bisect

freq = Counter([4, 1, 4, 2, 4, 1])     # built once, O(N)
print(freq[4], freq[9])                # 3 0  -- missing keys count as 0

def count_less_equal(arr, queries):
    s = sorted(arr)                    # O(N log N) once
    return [bisect.bisect_right(s, q) for q in queries]   # O(log N) each

print(count_less_equal([5, 1, 4, 1, 3], [0, 1, 4, 10]))   # [0, 2, 4, 5]

The hash map is faster on average, but it only answers equality questions. As soon as the question involves order (“the next larger value”, “values in [lo, hi]”), sorted data with binary search, or an ordered structure such as C++ std::map, is the right tool. See binary search patterns for the lower/upper bound variants.

“Average O(1)” deserves one caveat. A hash table degrades to a linear scan when many keys land in the same bucket, and for integer keys that can be arranged on purpose. C++‘s std::unordered_map<long long, int> with the default hash maps an integer to itself in libstdc++, so a test full of multiples of the bucket count turns every lookup into a walk through one long chain. On competitive programming judges with open hacking, such inputs are a known way to make hash-based solutions time out. The usual defences are a randomized hash (a splitmix64-style mixer seeded from the clock, passed as the map’s third template argument), reserve() to avoid repeated rehashing, or simply the sorted-array approach, whose O(log N) cost has no bad case. Python’s dict hashes small integers to themselves too, but string hashing is randomized per process, and in practice this attack is far more common against C++ solutions.

Memory is the other half of the trade-off. A set or dict of 10⁶ Python integers takes tens of megabytes, where a sorted array or list of the same values is much smaller. When the limit is 256 MB and the structure holds several million entries, the sorted version is sometimes the only one that fits.

Pattern 4: the algorithm is right, but something inside the loop is linear

This is the category I trip over most in Python, and it is easy to miss because the code looks O(N). Each of these is O(N) on its own, so inside a loop they make the whole thing quadratic:

• x in some_list (use a set)
• lst.pop(0) or lst.insert(0, x) (use collections.deque)
• slicing, such as arr[i:], which copies
• s += piece on strings in a loop (collect pieces in a list and "".join once)
• sorting inside a query loop when the data did not change

from collections import deque

queue = deque([1, 2, 3])
queue.append(4)
first = queue.popleft()    # O(1); list.pop(0) shifts every remaining element

I have watched a BFS written with list.pop(0) pass every sample and then time out on the large hidden tests, while the “same” BFS with deque.popleft() was fast. Nothing about the algorithm changed; the queue operation silently went from O(1) to O(N).

Pattern 5: the input and recursion overhead

When the complexity is right and there is no hidden linear step, the remaining Python-specific costs are usually I/O and recursion.

import sys

input = sys.stdin.readline          # much faster than the built-in input() for many lines

# Or read everything at once and split into tokens
data = sys.stdin.buffer.read().split()

Deep recursive DFS hits Python’s default recursion limit (1000) on path-like graphs. sys.setrecursionlimit raises the limit, but very deep recursion can still crash the interpreter by exhausting the C stack, so for large graphs an explicit stack is safer. In C++, the equivalent concern is std::cin without std::ios::sync_with_stdio(false) and cin.tie(nullptr) on large inputs.

When the data structure changes the complexity class

Many optimizations are not tricks but a better container. A quick mapping:

What the loop keeps asking	Structure	Cost per operation
Have I seen key k? How often?	Hash map / set	Average O(1)
Smallest or largest so far, with inserts	Heap	O(log N) push/pop
Next larger key, keys in a range	Balanced tree or sorted array + binary search	O(log N)
Range sum on a static array	Prefix sums	O(1) after O(N) setup
Range sum or min with updates	Fenwick / segment tree	O(log N)
Min/max of a sliding window	Monotonic deque	Amortized O(1)

For graph problems the same idea applies: plain BFS gives shortest paths only when every edge has the same weight; with non-negative weights you need Dijkstra with a heap, O((V + E) log V). Using BFS on weighted edges is a correctness bug, not just a speed issue.

A mistake worth naming: optimizing constants first

The other failure mode I see, and have committed myself, is spending the last twenty minutes of an interview squeezing a quadratic solution, such as swapping lists for arrays, inlining functions and caching lengths, when the constraints said N = 2×10⁵ from the start. Constant-factor work can make a correct-complexity solution pass a tight limit; it never turns 10¹⁰ operations into something that finishes. Write the one-line complexity estimate first, and only tune constants once that estimate fits.

Related Articles

• Algorithm Optimization Case Studies
• Sliding Window Technique: Fixed vs Variable Windows and When to Shrink
• Binary Search Patterns
• Hash Tables
• BFS vs DFS