Algorithm Optimization Case Studies

Introduction

“My logic is correct, but I’m getting Time Limit Exceeded!” In most cases the logic really is correct: the program would print the right answer, just not within the limit. The fix is rarely a clever trick. It is replacing a step that repeats work with one that does it once: sorting instead of scanning, precomputing instead of re-adding, a heap instead of trying every vertex, a DP table instead of enumerating subsets.

The five cases below follow the same format: the slow code, the arithmetic that shows why it cannot pass, the faster version, and the secondary limit that often bites once the complexity is fixed. The rough budget used throughout is about 10⁸ simple operations per second in C++, which is only an order-of-magnitude guide but enough to rule approaches in or out. The time complexity checklist covers the same reasoning from the constraints side.

---

Case 1: Duplicate Removal - O(n²) → O(n log n)

Problem

Remove duplicates from an array and output in sorted order.

• Input: n ≤ 100,000
• Time Limit: 1 second

TLE Code (O(n²))

vector<int> arr(n);
vector<int> result;
for (int i = 0; i < n; i++) {
    bool isDuplicate = false;
    
    // 🚨 Duplicate check: O(n)
    for (int j = 0; j < result.size(); j++) {
        if (arr[i] == result[j]) {
            isDuplicate = true;
            break;
        }
    }
    
    if (!isDuplicate) {
        result.push_back(arr[i]);
    }
}
sort(result.begin(), result.end()); // O(n log n)
// Total: O(n²) + O(n log n) = O(n²)

Time Analysis

With mostly distinct values, result grows to about n elements, and each new element is compared with all of them: roughly n²/2 = 5 × 10⁹ comparisons for n = 100,000. At about 10⁸ per second that is close to a minute, against a one-second limit. The code passes small samples instantly, which is why this bug survives until the large hidden tests.

AC Code (O(n log n))

// Method 1: Using set
set<int> s(arr.begin(), arr.end()); // O(n log n)
vector<int> result(s.begin(), s.end()); // Already sorted
// Method 2: Sort + unique
sort(arr.begin(), arr.end()); // O(n log n)
arr.erase(unique(arr.begin(), arr.end()), arr.end()); // O(n)
// Total: O(n log n)

Result

• TLE Code: on the order of 10¹⁰ elementary steps for n = 100,000.
• AC Code: about n log n ≈ 1.7 × 10⁶ comparisons, comfortably within the limit.
• Why: the inner “have I seen this?” scan is replaced by sorting once, after which equal values are adjacent and unique removes them in one pass.

Both methods have the same complexity, but sort + unique is usually noticeably faster in practice: it works on one contiguous array, while std::set allocates a tree node per element. unordered_set would make the deduplication O(n) on average, but the output must be sorted anyway, so the sort is still needed and the hash set only adds overhead. This is a common pattern: once the output requirement includes an O(n log n) step, making the other steps faster than that buys nothing.

---

Case 2: Range Sum - O(n×q) → O(n+q)

Problem

Answer q queries for the sum of array range [L, R].

• Input: n, q ≤ 100,000
• Time Limit: 1 second

TLE Code (O(n×q))

int arr[100000];
int q;
for (int i = 0; i < q; i++) {
    int L, R;
    cin >> L >> R;
    
    int sum = 0;
    // 🚨 Iterate through range every time: O(n)
    for (int j = L; j <= R; j++) {
        sum += arr[j];
    }
    
    cout << sum << '\n';
}
// Total: O(n × q) = 100,000 × 100,000 = 10 billion

AC Code (O(n+q))

// Prefix Sum preprocessing
int arr[100000];
long long prefix[100001]; // prefix[i] = arr[0] + ... + arr[i-1]
// Preprocessing: O(n)
prefix[0] = 0;
for (int i = 0; i < n; i++) {
    prefix[i+1] = prefix[i] + arr[i];
}
// Query: O(1)
for (int i = 0; i < q; i++) {
    int L, R;
    cin >> L >> R;
    
    long long sum = prefix[R+1] - prefix[L]; // O(1)
    cout << sum << '\n';
}
// Total: O(n + q) = 200,000

Result

• TLE Code: n × q = 10¹⁰ additions, far beyond the limit.
• AC Code: n + q = 2 × 10⁵ operations; each query becomes a single subtraction.
• Why: the prefix array pays the summing cost once, and every query reuses it.

Two details in the fast version matter as much as the algorithm. The prefix array is long long: with values up to 10⁹, a sum over 10⁵ elements reaches 10¹⁴, and an int prefix silently overflows, turning a TLE into a Wrong Answer. The slow version has the same bug in int sum, but it never gets far enough to show it. And with 10⁵ lines of output, I/O becomes the main cost: printing with '\n' instead of endl (which flushes every line) and calling ios::sync_with_stdio(false); cin.tie(nullptr); at the start are what make the O(n + q) version actually fast. See fast C++ I/O.

If the array is updated between queries, prefix sums stop working, since one update would change up to n prefix values. A Fenwick tree or segment tree gives O(log n) per update and per query instead.

---

Case 3: Shortest Path - O(V³) → O((V+E) log V)

Problem

Find the shortest path from starting point s to all vertices in a graph with non-negative edge weights.

• Input: V, E ≤ 100,000
• Time Limit: 2 seconds

TLE Code (O(V³))

// Floyd-Warshall: All pairs shortest path
int dist[1000][1000];
// Initialize
for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
        dist[i][j] = (i == j) ? 0 : INF;
    }
}
// Input edges
for (int i = 0; i < E; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    dist[u][v] = w;
}
// Floyd-Warshall: O(V³)
for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}
// V = 100,000 → V³ = 10¹⁵ → Impossible!

This code fails in three ways at once, which is worth seeing before looking at the fix. The time is V³ = 10¹⁵. The memory is V² entries: the fixed dist[1000][1000] above only fits 1,000 vertices, and a real 100,000 × 100,000 table would need 40 GB. And it solves the wrong problem: it computes all-pairs distances when only one source is asked for. Smaller bugs hide in it too: if INF is INT_MAX, dist[i][k] + dist[k][j] overflows to a negative number and “finds” impossible paths (use something like 1e9 so that two INFs still fit in an int), and dist[u][v] = w overwrites instead of keeping the minimum when there are parallel edges.

AC Code (O((V+E) log V))

// Dijkstra: Single source shortest path
#include <queue>
#include <vector>
vector<pair<int,int>> adj[100000]; // {vertex, weight}
int dist[100000];
void dijkstra(int start) {
    fill(dist, dist + V, INF);
    dist[start] = 0;
    
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start}); // {distance, vertex}
    
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        
        if (d > dist[u]) continue;
        
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}
// Total: O((V + E) log V) ≈ 200,000 × 17 ≈ 3,400,000

Result

• TLE Code: about 10¹⁵ operations and V² memory, impossible within any contest limit.
• AC Code: a few million heap operations, well within the limit.
• Why: Dijkstra only relaxes the edges that exist, and each vertex is finalized once, instead of trying every intermediate vertex for every pair.

The line if (d > dist[u]) continue; is what keeps this version fast. The heap may hold several entries for the same vertex, one for each time its distance improved; without the check, stale entries are expanded again and the running time degrades badly on dense graphs. If distances can exceed about 2 × 10⁹ (for example, 10⁵ edges of weight 10⁹ on a path), dist must be long long. And Dijkstra requires non-negative weights; with negative edges it silently returns wrong distances, and Bellman-Ford or SPFA is needed instead.

---

Case 4: Subset Sum Count - O(2ⁿ) → O(n·K)

Problem

Count the number of subsets of an array (elements 1 ≤ aᵢ ≤ K) that sum to K, modulo 10⁹ + 7.

• Input: n ≤ 1,000, K ≤ 100,000
• Time Limit: 1 second

TLE Code (O(2ⁿ))

int arr[1000];
int count = 0;
// Explore all subsets
void backtrack(int idx, int sum) {
    if (idx == n) {
        if (sum == K) count++;
        return;
    }
    
    // Include
    backtrack(idx + 1, sum + arr[idx]);
    // Exclude
    backtrack(idx + 1, sum);
}
backtrack(0, 0);
// n = 1000 → 2¹⁰⁰⁰ → Impossible!

Pruning helps a little (stop when sum > K), but for n = 1,000 the number of subsets is astronomically beyond any budget. The observation that saves it is that many different subsets reach the same state: “after looking at the first i elements, the sum is j”. There are only n × K such states.

AC Code (O(n·K))

// Dynamic Programming with one rolling row
const int MOD = 1'000'000'007;
vector<int> dp(K + 1, 0);   // dp[j] = ways to make sum j with the elements seen so far
dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = K; j >= arr[i]; j--) {      // downward: each element used at most once
        dp[j] = (dp[j] + dp[j - arr[i]]) % MOD;
    }
}
cout << dp[K];
// Total: O(n × K) = 1,000 × 100,000 = 10^8 simple updates

Result

• TLE Code: 2¹⁰⁰⁰ subsets, impossible to enumerate.
• AC Code: n × K = 10⁸ simple updates. That is near the upper end of what fits in one second, so the inner loop has to stay simple.
• Why: DP computes each (index, sum) state once instead of once per subset that reaches it.

The obvious 2D version, int dp[1001][100001], has the right time complexity and still fails: 1,001 × 100,001 four-byte ints is about 400 MB, far over the usual 256 MB limit, so the verdict becomes Memory Limit Exceeded (or a crash, if the array is local and overflows the stack). Since row i + 1 depends only on row i, one row is enough. The direction of the inner loop is the subtle part: iterating j downward means dp[j - arr[i]] still holds the value from before element i was considered, so each element is used at most once. Iterating upward would count subsets that use the same element several times, which is the answer to a different problem (unbounded coin change).

The modulo is not decoration either. The number of subsets can be as large as 2¹⁰⁰⁰, so without it the counts overflow int after a few dozen elements and the output is garbage. Problems that ask for a count “modulo 10⁹ + 7” are signalling exactly this.

---

Case 5: String Matching - O(n×m) → O(n+m)

Problem

Find all positions where a pattern appears in text.

• Input: Text length n ≤ 1,000,000, Pattern length m ≤ 10,000
• Time Limit: 2 seconds

TLE Code (O(n×m))

string text, pattern;
vector<int> positions;
// Compare at every position
for (int i = 0; i <= n - m; i++) {
    bool match = true;
    
    // 🚨 Compare entire pattern each time: O(m)
    for (int j = 0; j < m; j++) {
        if (text[i+j] != pattern[j]) {
            match = false;
            break;
        }
    }
    
    if (match) {
        positions.push_back(i);
    }
}
// Worst case: O(n × m) = 1,000,000 × 10,000 = 10 billion

On random text this naive loop is fast, because most comparisons fail at the first or second character, which is why it often passes early tests. Test setters know this and include inputs such as aaaa...a with pattern aaa...ab, where every position matches for m − 1 characters before failing. That is the case the worst-case estimate describes.

AC Code (O(n+m))

// KMP Algorithm
vector<int> computeLPS(const string& pattern) {
    int m = pattern.size();
    vector<int> lps(m, 0);
    int len = 0;
    
    for (int i = 1; i < m; i++) {
        while (len > 0 && pattern[i] != pattern[len]) {
            len = lps[len - 1];
        }
        if (pattern[i] == pattern[len]) {
            len++;
        }
        lps[i] = len;
    }
    
    return lps;
}
vector<int> kmpSearch(const string& text, const string& pattern) {
    vector<int> lps = computeLPS(pattern); // O(m)
    vector<int> positions;
    
    int i = 0, j = 0;
    while (i < text.size()) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        
        if (j == pattern.size()) {
            positions.push_back(i - j);
            j = lps[j - 1];
        } else if (i < text.size() && text[i] != pattern[j]) {
            if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return positions;
}
// Total: O(n + m) = 1,010,000

Result

• TLE Code: up to n × m = 10¹⁰ character comparisons in the worst case.
• AC Code: n + m ≈ 1.01 × 10⁶ steps.
• Why: lps[j] is the length of the longest proper prefix of the pattern that is also a suffix of its first j + 1 characters. After a mismatch, KMP continues from that prefix instead of restarting, so the text pointer i never moves backward.

std::string::find in a loop is not a substitute: the standard does not guarantee linear time, and common implementations can still be O(n·m) in the worst case. C++17’s std::boyer_moore_searcher (or boyer_moore_horspool_searcher) with std::search is a library option that is fast in practice. Z-algorithm and rolling hashes (Rabin-Karp) are the other contest-standard alternatives; hashing is easier to adapt to multiple patterns, at the cost of a small collision probability.

---

Complexity Improvement Patterns

Pattern 1: Duplicate Removal → sort/set/unordered_set

// O(n²) → O(n log n) or O(n)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < result.size(); j++) {
        if (arr[i] == result[j]) { /* ... */ }
    }
}
// ↓
set<int> s(arr.begin(), arr.end()); // O(n log n)
// or
unordered_set<int> s(arr.begin(), arr.end()); // O(n) average

Pattern 2: Range Query → Prefix Sum/Segment Tree

// O(n × q) → O(n + q)
for (int i = 0; i < q; i++) {
    int sum = 0;
    for (int j = L; j <= R; j++) {
        sum += arr[j]; // Iterate every time
    }
}
// ↓
// Prefix sum preprocessing
prefix[0] = 0;
for (int i = 0; i < n; i++) {
    prefix[i+1] = prefix[i] + arr[i];
}
// Query: O(1)
long long sum = prefix[R+1] - prefix[L];

Pattern 3: Brute Force → Dynamic Programming

// O(2ⁿ) → O(n × K)
void backtrack(int idx, int sum) {
    if (idx == n) { /* ... */ }
    backtrack(idx + 1, sum + arr[idx]);
    backtrack(idx + 1, sum);
}
// ↓
// DP over (element, sum) states, one rolling row
vector<long long> dp(K + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = K; j >= arr[i]; j--) {
        dp[j] += dp[j - arr[i]];
    }
}

The general signal for this pattern: the brute force explores choices, and the future only depends on a small summary of past choices (here, the current sum). If that summary has few possible values, DP over it replaces exponential enumeration with a table.

Pattern 4: Utilize Sorting

// O(n²) → O(n log n)
// Find pairs that sum to K
// Brute force
for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
        if (arr[i] + arr[j] == K) { /* ... */ }
    }
}
// ↓
// Sort + Two Pointers
sort(arr.begin(), arr.end());
int left = 0, right = n - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == K) {
        // Found
        left++;
        right--;
    } else if (sum < K) {
        left++;
    } else {
        right--;
    }
}

This loop finds whether a pair exists, and it finds distinct value pairs. It does not count all index pairs when there are duplicates: for {2, 2, 2} and K = 4 there are three pairs, and moving both pointers after each match finds one. Counting needs to handle runs of equal values (multiply the run lengths, or for equal values, use r·(r − 1)/2).

---

Time Complexity Checklist

Allowed Complexity by Input Size

Input Size n	Allowed Complexity	Algorithm Examples
n ≤ 10	O(n!)	All permutations
n ≤ 20	O(2ⁿ · n)	Subset enumeration, bitmask DP
n ≤ 500	O(n³)	Floyd-Warshall, interval DP
n ≤ 5,000	O(n²)	2D DP, all pairs
n ≤ 200,000	O(n log n)	Sorting, heaps, segment tree
n ≤ 10,000,000	O(n) with a small constant	Linear scan, prefix sums, two pointers
n up to 10¹⁸	O(log n) or O(√n)	Binary search on the answer, fast exponentiation

The table is a rule of thumb for C++ with a one- to two-second limit; slower languages need more headroom, and memory access patterns can shift the boundaries. Read it in both directions: the constraint tells you what is too slow, and it also hints at what the setter intended. N ≤ 20 almost always means exponential enumeration is expected.

Complexity Calculation Examples

// Example 1
for (int i = 0; i < n; i++) {          // O(n)
    for (int j = 0; j < n; j++) {      // × O(n)
        cout << i + j;                  // O(1)
    }
}
// Total: O(n²)
// Example 2
for (int i = 0; i < n; i++) {          // O(n)
    sort(arr.begin(), arr.end());       // × O(n log n)
}
// Total: O(n² log n)
// Example 3
for (int i = 0; i < n; i++) {          // O(n)
    if (binary_search(...)) {           // × O(log n)
        // ...
    }
}
// Total: O(n log n)

Example 2 is the one that hides in real code: a sort, a vector copy, a find in a vector, or a string concatenation inside a loop looks like one line but multiplies the loop’s cost.

---

Data Structure Selection Guide

Operation	Data Structure	Complexity
Duplicate removal with sorted output	sort + unique, or set	O(n log n)
Membership test	unordered_set	O(1) average
Ordered keys, next larger key	set, map	O(log n)
Range sum, static array	Prefix sum array	O(1) query
Range minimum or sum with updates	Segment tree / Fenwick tree	O(log n)
Repeated maximum or minimum	priority_queue	O(log n)
LRU cache	list + unordered_map	O(1) average

---

Conclusion

Across the five cases, the same steps led to the fix:

1. Estimate before coding. Multiply out the worst case from the constraints and compare it with about 10⁸ operations per second.
2. Find the repeated work. An inner scan, a re-summed range, a recomputed state or a restarted comparison is almost always the part that can be done once.
3. Choose the structure with the right operation cost: sorting, prefix sums, a heap, a DP table or a failure function.
4. Check the second limit. After the complexity is right, memory (the 2D DP table, the V² matrix), overflow (long long sums, INF + w, counts modulo a prime) and I/O speed are what fail next.

The habit that prevents most TLEs is a single line written before any code: the complexity of the planned approach, with the constraint values plugged in.

---

FAQ

Q1. Calculating complexity is difficult. Count nested loops and multiply their iteration counts, including the cost of library calls inside them (sort, find, erase from the middle of a vector, string copies). For recursion, count the number of distinct calls times the work per call.

Q2. Is the difference between O(n log n) and O(n) significant? For small n, the difference is minimal. For n = 1,000,000, log₂ n ≈ 20, so the operation count differs by roughly that factor, but the actual runtime gap can be smaller or larger because of constant factors and cache behavior (a cache-friendly O(n log n) sort can beat a hash-heavy O(n) pass). It usually matters only when you are close to the time limit.

Q3. Is constant time optimization needed? Complexity improvement comes first. If complexity is the same, consider constant optimization (fast I/O, contiguous arrays instead of node-based containers, avoiding repeated allocation).

---

Related Articles

• Time Complexity Optimization Checklist for Coding Interviews
• Fast C++ I/O for Coding Tests: What sync_with_stdio, cin.tie and endl Actually Do
• Dynamic Programming: Memoization vs Tabulation and How to Spot a DP Problem
• Preparing for C++ Coding Interviews