Skip to content
Essay · Complexity

Why does my solution get time limit exceeded?

Why does my solution get time limit exceeded when the logic is right? Because the growth rate does not fit the input limit. Here is how to estimate operations, spot hidden O(n) costs, and fix it with real numbers.

By Vishy11 min readPublished · 26 Oct 2026

Why does my solution get time limit exceeded when the logic is correct? Almost always because the growth rate of the algorithm does not fit the input limit. Divide the judge's budget of roughly 10^8 simple operations by your cost formula, and if it does not fit, change the algorithm, not the code.

That sounds blunt, but it matches what I see when people ask for help with a TLE. They paste a working solution, they have already tried swapping a for loop for a comprehension, and they are confused that nothing moved. The program was never slow in the way they imagined. It was doing twenty billion steps in a world that allows a few hundred million. No amount of polish closes a gap of that size, and the quickest way out is to learn to see the gap before you submit.

What does time limit exceeded actually tell you?

It tells you one thing: on at least one test, your program had not finished when the judge's clock ran out, typically after 1 to 2 seconds. It says nothing about whether your answer is correct, and it does not tell you why the clock ran out.

There are really only three causes. The first is the wrong growth rate, which is the overwhelming majority. The second is a hidden cost, where a line that looks constant-time is secretly linear. The third is a bug that never terminates, such as a loop whose counter does not advance on some input, or recursion that does not shrink the problem. A verdict of TLE cannot distinguish these, so you have to.

Here is the framing I use. Think of the time limit as a fuel tank holding about 10^8 units, and your algorithm as an engine with a burn rate that depends on the input size n. A tank is not a promise that you will arrive; it is a fixed amount of fuel, and the only question is whether the route you chose costs less than the tank. Small tests are short trips, so everything passes. The judge's largest test is the long haul, and TLE means the tank ran dry somewhere on it. Nobody fixes that by driving more gently. You fix it by choosing a different route.

Judges also build their tests to be hostile. Expect sorted arrays, arrays where every element is equal, strings of a single repeated letter, and trees that are one long chain. If your solution is quick on random data and times out on test 47, test 47 is usually one of these shapes.

How many operations can a program do in one second?

Roughly 10^8 to 5*10^8 simple operations in C++ or Java, and about 10^7 loop iterations in pure Python. Treat these as order-of-magnitude figures, not guarantees, because the word simple is doing a lot of work.

A simple operation is an integer add, a comparison, or an array read. Those cost around a nanosecond or two in a compiled language when the data sits in cache. A hash map insertion is not simple: it hashes, probes, may resize, and touches memory unpredictably, so it costs perhaps 20 to 100 times more than an add. If your inner loop does one hash insertion per step, the budget is closer to 10^7 than 10^8, even in C++. This is the same reasoning behind why a hash map can be slower than you expect, and the details of probing and resizing are in load factor and collisions.

Python adds its own multiplier. A loop like for i in range(n): total += a[i] runs somewhere around 10^7 iterations per second, because each iteration goes through the interpreter. That is why a solution that is fine at 10^6 elements in Python can die at 10^7 while the identical algorithm in C++ finishes with room to spare. Some judges grant Python a longer limit, but you should not count on it.

So when you estimate, do two things. Count the dominant loop's iterations as a function of n. Then weight them: a few nanoseconds for array arithmetic, tens of nanoseconds for hashing or allocation, and a much bigger factor if you are in an interpreter.

How do you turn the input limit into a target complexity?

Read the maximum n, compute what each complexity class produces at that n, and choose the slowest class that stays under about 10^8 (or 10^7 in Python). The constraint line is not decoration; it is the problem setter telling you what the intended solution costs.

Maximum nLargest workable complexityOperations at that nTypical technique
10 to 12O(n!)about 4.8*10^8 at n = 12Brute-force permutations
20 to 25O(2^n)about 3.4*10^7 at n = 25Subsets, bitmask search
200 to 500O(n^3)1.25*10^8 at n = 500Triple loops, Floyd-Warshall
5,000O(n^2)2.5*10^7Pairwise loops, 2D dynamic programming
100,000 to 200,000O(n log n)about 3.6*10^6 at n = 200,000Sorting, heaps, binary search, divide and conquer
10^6 to 10^7O(n)10^6 to 10^7Hash maps, prefix sums, sliding window, two pointers
up to 10^18O(log n)about 60Binary search on the answer, fast exponentiation

Notice what the table says about the distinctions people agonise over. At n = 200,000, O(n log n) costs about 3.6 million steps, which is trivial. The gap that matters is between O(n^2) and everything below it. Whether your solution is n or n log n almost never decides a TLE; if you want the longer argument for why, see O(log n) vs O(n log n). What decides it is the jump from a quadratic to a near-linear algorithm.

Two refinements are worth knowing. First, check whether the limit is per test or summed over tests. If the statement says the total n across all test cases is at most 2*10^5, an O(n^2) per test can still be fine when tests are tiny, but it is deadly if one test holds everything. Second, a second parameter such as k or the number of queries q changes the arithmetic: a solution costing O(n*q) with both at 2*10^5 is 4*10^10, the same disaster as n squared.

Why does a correct subarray-sum solution time out?

Because it checks every pair of endpoints, which is about n squared over two pairs, and at n = 200,000 that is 2*10^10 checks. Here is the problem in my own words: given an array of n integers and a target k, count the contiguous stretches whose elements add up to exactly k. The array can hold up to 200,000 values, positive or negative.

The natural first attempt fixes a start and extends the end, keeping a running sum so each extension costs one add and one comparison:

def count_slow(a, k):
    n = len(a)
    count = 0
    for i in range(n):
        running = 0
        for j in range(i, n):
            running += a[j]
            if running == k:
                count += 1
    return count

def count_fast(a, k):
    seen = {0: 1}
    prefix = 0
    count = 0
    for x in a:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

The slow version is correct. Now count its cost. The inner loop runs n, then n minus 1, then n minus 2, and so on, which sums to n(n+1)/2. With n = 200,000 that is about 2*10^10 iterations. In C++ at 5*10^8 simple operations per second, that is roughly 40 seconds. In Python at 10^7 per second, it is about 2,000 seconds, over half an hour. Against a 2-second limit, you miss by 20 times in C++ and by 1,000 times in Python. Even a heroic constant-factor effort buys you perhaps 3 times. You need a factor of ten thousand or more, and only a different algorithm provides that.

The fast version rests on one observation: the sum of a stretch from i to j equals the prefix at j minus the prefix just before i. So instead of searching for a start, you ask how many earlier prefixes equal the current prefix minus k, and a hash map answers that in one lookup. The loop runs 200,000 times with two dictionary operations each. At around a microsecond per iteration in Python, that is about 0.2 seconds. From 2*10^10 steps to 2*10^5 is a factor of 10^5, and no micro-optimisation does that. The technique is covered in prefix sums, and the full problem is Subarray Sum Equals K.

The lesson I draw is that the budget calculation takes thirty seconds and would have told you before writing a line that the double loop could not pass. Most of my own wasted debugging hours came from skipping that arithmetic.

Which hidden costs make a correct-looking solution time out?

Operations that look constant-time but scan or copy the whole structure: removing from the front of a list, searching a list with in, slicing, and repeated string building. You can write a loop with a single visible level and still be quadratic, because the second loop is inside a library call.

  • Popping from the front of a Python list. queue.pop(0) shifts every remaining element. Draining a queue of 100,000 items this way moves about n(n-1)/2, or 5*10^9, elements. The shifts are fast memory moves, but that is still several seconds. A collections.deque makes each pop constant time.
  • Membership tests on a list. if x in seen_list inside a loop of 100,000 iterations does up to 5*10^9 comparisons in total. Changing the list to a set turns each test into an expected constant-time lookup. Hash-based structures are the subject of the hash maps topic.
  • Slicing and copying. A recursive function that passes arr[1:] copies the remainder at every level, so depth n costs n squared over two element copies. Pass indices instead.
  • String concatenation in a loop. In Java, s += c over 100,000 characters copies about 5*10^9 characters in total. Use a builder, or in Python collect pieces in a list and join once.
  • Sorting inside a loop. Sorting 1,000 elements costs about 10,000 steps, which sounds harmless until you do it 100,000 times and reach 10^9. If the data changes by one element at a time, a heap or a sorted structure is the better tool.

The way to catch these is to read your own code once with a single question: for each line inside a loop, what does it cost as n grows? Anything you cannot answer is where to look. Complexity is a property of the whole call, including what the library does for you, an idea I develop in complexity is a contract.

When is the constant factor the real problem?

When your algorithm already matches the intended complexity and you are still over the limit by a small factor, roughly 1.5 to 5 times. In that narrow window, constants matter, and only in that window.

The usual suspects, in the order I check them:

  • Input and output. Reading 10^6 numbers with a line-by-line input() call in Python can take most of a second. Reading everything at once through the buffered standard input is several times faster. The same applies to printing: build one string and write it once.
  • Allocation in the inner loop. Creating a tuple, list, or object on every iteration costs far more than arithmetic. A dictionary keyed by tuples is considerably slower than a flat array indexed by an integer you compute.
  • Memoisation overhead. A cached recursive function pays for a hash lookup and a function call on each state. A bottom-up table over the same states often runs several times faster, which is part of the trade-off in memoisation versus tabulation. The call overhead question more generally is covered in is recursion slower than iteration.
  • Cache behaviour. Walking a 2D grid row by row is friendlier to memory than column by column. On a 5,000 by 5,000 grid, the difference can be a factor of several.

I want to be clear about the order. I have watched people spend an hour converting a quadratic solution to use faster I/O. It never passed, because it was off by a factor of 1,000, not 3. Constants are the last lever, and you pull it only after the growth rate is right.

What should you do in the first five minutes after a TLE?

Compute the budget before touching the code: write down the maximum n, work out the iteration count of your dominant loop, and compare it to 10^8. That single comparison tells you which of the three causes you are facing.

  1. Write the largest n and the time limit at the top of your notes.
  2. Express the cost of your slowest loop as a formula in n, including the library calls inside it.
  3. If the result is above about 10^8 (10^7 for Python), the algorithm is wrong for this problem. Look for repeated work you can store: a running prefix, a hash map of what you have seen, a sort followed by two pointers, a heap for the best remaining candidate.
  4. If the result is under budget but the run is still slow, hunt for hidden linear costs from the list above.
  5. If the algorithm and the library calls are both clean and you are within a few times of the limit, tune constants: I/O, allocation, table layout.
  6. Build the worst case yourself: sorted input, all-equal input, a chain-shaped tree, then time it at the full n. A solution you have never run at maximum size is a solution you have not tested.

If the program never finishes even on tiny inputs, skip all of this and look for the non-terminating loop or the recursion that does not shrink. That is a bug, not a performance problem.

Frequently asked questions

Can a correct solution still get time limit exceeded?

Yes, and it is the normal case. Correctness and speed are separate properties, and judges check the second one on inputs deliberately sized to break quadratic and exponential approaches. A brute force that passes every small test is often exactly the solution the problem was designed to reject.

Is Python too slow for coding problems?

Not for interviews, where you are judged on the algorithm and its complexity, and interviewers rarely run your code at scale. On online judges Python has roughly a 10 to 50 times higher constant than C++, so you have less slack and must reach the intended complexity cleanly. A near-linear Python solution passes comfortably, while a quadratic one fails at any language.

How can I estimate runtime without running the code?

Count the iterations of the innermost loop as a formula in n, substitute the maximum n, and compare the result to 10^8 for compiled languages or 10^7 for Python. Weight expensive operations such as hashing or allocation as ten to a hundred simple steps each. If your estimate lands within a factor of two of the limit, run it and measure.

To practise this, take the worked example above and write both versions yourself, then time them at n = 200,000 and compare the numbers with the estimates here, starting from the problem page for Subarray Sum Equals K.