How to Reduce Time Complexity: 7 Techniques That Work
8 min read
To reduce time complexity, find the work your code repeats and stop repeating it. Almost every fix is one of seven moves: remember what you have seen in a hash map, sort and walk two pointers, precompute prefix sums, slide a window, binary search the answer, cache subproblems, or keep a monotonic stack. This guide shows each one with working code.
If you have ever watched an online assessment reject a correct solution with "Time Limit Exceeded", you already know why this matters. The logic was fine. The algorithm did too much work. Interviewers push on the same point with one question: "Can you do better?" The techniques below are how you answer it.
Key takeaways
- Read the input limits before you write code. They tell you which complexity will pass.
- Most slow solutions redo a lookup, a sum or a scan inside a loop. Remove the repetition and the complexity drops.
- Faster usually costs memory. A hash map turns O(n²) into O(n) by storing up to n items.
- Sorting costs O(n log n), so it only helps when it removes something slower than that.
- Match the shape of the problem to the technique: pairs, ranges, windows, "minimum that works", overlapping subproblems or "next bigger".
How do you know which time complexity you need?
Look at the largest input the problem allows and work backwards. A common rule of thumb for competitive programming judges is that C++ manages roughly 10^8 simple operations per second. Divide that budget by your input size and you get the complexity you can afford.
| Largest n | Complexity that usually passes | Typical approach |
|---|---|---|
| up to 12 | O(n!) | Try every permutation |
| up to 25 | O(2^n) | Try every subset |
| up to 500 | O(n³) | Three nested loops, interval DP |
| up to 5,000 | O(n²) | Two nested loops, 2D DP |
| up to 10^6 | O(n log n) or O(n) | Sorting, hash maps, two pointers, prefix sums |
| above 10^9 | O(log n) or O(1) | Binary search, maths |
Treat this as a starting point, not a law. Python runs loop-heavy code much slower than C++, so in Python aim one row lower and lean on built-in functions, which run in C.
1. Replace a nested search with a hash map
Use it when you search for a matching element for every element, such as "find two numbers that add up to a target".
The brute force checks every pair. That is n × (n − 1) / 2 comparisons, so O(n²):
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []The inner loop exists only to answer one question: "have I seen target - nums[i] before?" A hash map answers that in O(1) on average, so one pass is enough:
def two_sum(nums, target):
seen = {} # value -> index where we saw it
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum([3, 2, 4], 6)) # [1, 2]#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
vector<int> twoSum(const vector<int>& nums, int target) {
unordered_map<int, int> seen; // value -> index where we saw it
for (int i = 0; i < (int)nums.size(); i++) {
auto it = seen.find(target - nums[i]);
if (it != seen.end()) return {it->second, i};
seen[nums[i]] = i;
}
return {};
}
int main() {
vector<int> r = twoSum({2, 7, 11, 15}, 9);
cout << r[0] << " " << r[1] << "\n"; // 0 1
}import java.util.*;
public class Main {
static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>(); // value -> index
for (int i = 0; i < nums.length; i++) {
Integer j = seen.get(target - nums[i]);
if (j != null) return new int[]{j, i};
seen.put(nums[i], i);
}
return new int[0];
}
public static void main(String[] args) {
System.out.println(Arrays.toString(twoSum(new int[]{2, 7, 11, 15}, 9))); // [0, 1]
}
}How big is the difference? In a quick Python test on random input with no valid pair (the worst case), 5,000 numbers took 0.54 seconds with nested loops and 0.7 milliseconds with the hash map. At 20,000 numbers it was 9.15 seconds against 3.2 milliseconds. Four times the input made the nested version about 17 times slower, which is what quadratic growth looks like.
Cost: O(n) time, O(n) extra space.
2. Sort, then walk two pointers
Use it when the order of elements doesn't matter and you need pairs or triples that meet a condition, and you would rather not spend O(n) memory on a hash map.
After sorting, put one pointer at each end. If the sum is too small, move the left pointer right; if it is too big, move the right pointer left. Each step throws away one element for good, so the walk is O(n).
def has_pair_with_sum(nums, target):
nums = sorted(nums)
lo, hi = 0, len(nums) - 1
while lo < hi:
total = nums[lo] + nums[hi]
if total == target:
return True
if total < target:
lo += 1 # need a bigger sum
else:
hi -= 1 # need a smaller sum
return False
print(has_pair_with_sum([8, 3, 5, 1, 9], 12)) # True (3 + 9)
print(has_pair_with_sum([8, 3, 5, 1, 9], 7)) # FalseThe same idea turns 3Sum from O(n³) into O(n²): fix one number, then run the two-pointer walk on the rest.
Cost: O(n log n) because of the sort, O(1) extra space if you sort in place.
3. Precompute prefix sums for range queries
Use it when you answer many "sum of elements from l to r" questions on an array that doesn't change.
Adding up each range from scratch costs O(n) per query. Instead, build prefix[i], the sum of the first i elements, once. Every range sum then becomes one subtraction.
def range_sums(nums, queries):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return [prefix[r + 1] - prefix[l] for l, r in queries]
print(range_sums([3, 1, 4, 1, 5, 9], [(0, 2), (2, 5), (4, 4)])) # [8, 19, 5]With n elements and q queries you go from O(n · q) to O(n + q). The same trick works in 2D for sums over sub-rectangles of a grid.
4. Slide a window instead of restarting it
Use it when the answer is a contiguous subarray or substring: the longest, the shortest, or one with a fixed size.
The slow version restarts its scan from every starting index. A sliding window keeps a running state and only moves its edges forward, so every element enters and leaves the window at most once. Here is the classic "longest substring without repeating characters":
def longest_unique_substring(s):
last_seen = {}
start = best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1 # jump past the repeat
last_seen[ch] = i
best = max(best, i - start + 1)
return best
print(longest_unique_substring("abcabcbb")) # 3 ("abc")
print(longest_unique_substring("pwwkew")) # 3 ("wke")int longestUniqueSubstring(const string& s) {
unordered_map<char, int> lastSeen;
int start = 0, best = 0;
for (int i = 0; i < (int)s.size(); i++) {
auto it = lastSeen.find(s[i]);
if (it != lastSeen.end() && it->second >= start) start = it->second + 1;
lastSeen[s[i]] = i;
best = max(best, i - start + 1);
}
return best;
}static int longestUniqueSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int start = 0, best = 0;
for (int i = 0; i < s.length(); i++) {
Integer prev = lastSeen.get(s.charAt(i));
if (prev != null && prev >= start) start = prev + 1;
lastSeen.put(s.charAt(i), i);
best = Math.max(best, i - start + 1);
}
return best;
}Cost: O(n) time instead of O(n²) or worse.
5. Binary search the answer
Use it when the question asks for the minimum (or maximum) value that satisfies a condition, and if one value works, every larger value works too.
You don't need a sorted array for this. You need that yes/no condition to be monotonic. Take "Capacity To Ship Packages Within D Days": the smallest ship capacity that moves all packages, in order, within days days. If capacity c works, c + 1 works too, so binary search between the heaviest package and the total weight:
def min_capacity(weights, days):
def days_needed(cap):
used, load = 1, 0
for w in weights:
if load + w > cap:
used += 1
load = 0
load += w
return used
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if days_needed(mid) <= days:
hi = mid # mid works, try smaller
else:
lo = mid + 1 # mid is too small
return lo
print(min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)) # 15Trying every capacity costs O(n · S), where S is the total weight. Binary search cuts that to O(n log S).
6. Cache subproblems with memoization or DP
Use it when a recursive solution solves the same subproblem again and again.
The minimum number of coins for an amount, tried naively, explores the same remainders over and over, and the work grows exponentially. Store each answer the first time you compute it and the total work becomes amount × number of coins.
from functools import lru_cache
def min_coins(coins, amount):
@lru_cache(maxsize=None)
def best(rem):
if rem == 0:
return 0
if rem < 0:
return float("inf")
return 1 + min(best(rem - c) for c in coins)
answer = best(amount)
return -1 if answer == float("inf") else answer
print(min_coins((1, 2, 5), 11)) # 3 (5 + 5 + 1)
print(min_coins((2,), 3)) # -1Python's default recursion limit is about 1,000 calls deep, so for large amounts write the same idea bottom-up. That is the version to show in C++ and Java anyway:
int minCoins(const vector<int>& coins, int amount) {
const int INF = INT_MAX / 2;
vector<int> dp(amount + 1, INF); // dp[x] = fewest coins that make x
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x) dp[x] = min(dp[x], dp[x - c] + 1);
return dp[amount] >= INF ? -1 : dp[amount];
}static int minCoins(int[] coins, int amount) {
int[] dp = new int[amount + 1]; // dp[x] = fewest coins that make x
Arrays.fill(dp, Integer.MAX_VALUE / 2);
dp[0] = 0;
for (int x = 1; x <= amount; x++)
for (int c : coins)
if (c <= x) dp[x] = Math.min(dp[x], dp[x - c] + 1);
return dp[amount] >= Integer.MAX_VALUE / 2 ? -1 : dp[amount];
}Memoization is caching applied to a function. The same instinct, at the scale of whole systems, is what caching in system design is about.
7. Keep a monotonic stack
Use it when each element needs the next (or previous) element that is bigger or smaller than it.
The brute force scans to the right from every element, which is O(n²). A stack of indices that are still waiting for an answer fixes this. When a bigger number arrives, it resolves every smaller waiting number at once:
def next_greater(nums):
result = [-1] * len(nums)
stack = [] # indices still waiting for a bigger number
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
result[stack.pop()] = x
stack.append(i)
return result
print(next_greater([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]Each index is pushed once and popped at most once, so the whole thing is O(n). The same pattern solves stock span, daily temperatures and the largest rectangle in a histogram.
Which technique should you try first?
Match the wording of the problem to a pattern:
| If the problem says… | Try | Typical gain |
|---|---|---|
| "find a pair / complement / duplicate" | Hash map | O(n²) → O(n) |
| "pairs or triples with a sum", order irrelevant | Sort + two pointers | O(n³) → O(n²) for 3Sum |
| "sum of a range", many queries | Prefix sums | O(n · q) → O(n + q) |
| "longest / shortest substring or subarray" | Sliding window | O(n²) → O(n) |
| "minimum capacity / speed / time that works" | Binary search on the answer | O(n · S) → O(n log S) |
| "number of ways", "minimum cost", repeated recursion | Memoization or DP | exponential → polynomial |
| "next greater / smaller element" | Monotonic stack | O(n²) → O(n) |
| "k largest / smallest" | Heap of size k | O(n log n) → O(n log k) |
Common mistakes when optimising
- Optimising before it works. Get a correct brute force first. It doubles as a checker: run both on small random inputs and compare.
- Ignoring memory. A hash map or DP table can push you past the memory limit. Check it the same way you check time.
- Forgetting the cost of sorting. Sorting inside a loop quietly turns O(n) into O(n² log n).
- Using
inon a Python list inside a loop.x in some_listis O(n). Turn the list into a set first. - Trusting hash maps blindly. O(1) is the average. Crafted inputs can trigger collisions, so on contest platforms a sorted array with binary search is sometimes the safer choice.
Practice problems for each technique
Do these in order and say the complexity out loud before you code:
- Two Sum (LeetCode 1): hash map
- 3Sum (LeetCode 15): sort and two pointers
- Range Sum Query: Immutable (LeetCode 303): prefix sums
- Longest Substring Without Repeating Characters (LeetCode 3): sliding window
- Koko Eating Bananas (LeetCode 875): binary search on the answer
- Coin Change (LeetCode 322): DP
- Next Greater Element I (LeetCode 496): monotonic stack
Spotting which of these patterns a new problem is hiding is a skill you build with feedback, not just volume. Complexity analysis and these core patterns make up the first module (weeks 1 to 4) of the DSA, System Design & AI Bootcamp, which is taught live by practising engineers. If you prefer to work through it on your own, start with the ProPeers roadmaps.
Frequently asked questions
What is the fastest way to reduce time complexity?
Look for work your code repeats inside a loop. If you search for something inside a loop, a hash map usually removes that inner loop and turns O(n²) into O(n). If you add up the same ranges again and again, prefix sums do the same for range queries.
Is O(n log n) better than O(n)?
No. O(n) grows more slowly than O(n log n), so for large inputs O(n) is faster. O(n log n) is still fast enough for inputs of around a million elements on most online judges.
Does reducing time complexity always increase space complexity?
Often, but not always. Hash maps and DP tables trade memory for speed, while two pointers, sliding windows and binary search usually need only O(1) extra space.
Why does my correct solution get Time Limit Exceeded?
Its time complexity is too high for the input size. An O(n²) loop over 100,000 elements is about 10 billion operations, far more than a judge allows in a second or two. Compare the largest input in the constraints with the complexity you need.
How do I work out the time complexity of my code?
Count how many times the innermost operation runs as the input grows. Nested loops multiply, loops one after another add, and halving the input at every step adds a log factor. Keep only the fastest-growing term.