Algorithm Optimization Case Studies | Solving Time Limit Exceeded (TLE) in Coding Tests

Introduction

“My logic is correct, but I’m getting Time Limit Exceeded!” This is one of the most frustrating moments in coding tests. In this article, we’ll share real-world case studies of solving TLE by improving time complexity.

To use an analogy, it’s like having the right map but counting every person at every intersection. The direction is correct, but doing too much redundant work means you can’t finish within the time limit.

What You’ll Learn

• How to accurately analyze time complexity
• Techniques to find and optimize bottlenecks
• Strategies to improve performance through data structure selection
• Patterns you can immediately apply in coding tests

---

Table of Contents

1. Case 1: Duplicate Removal - O(n²) → O(n)
2. Case 2: Range Sum - O(n×q) → O(n+q)
3. Case 3: Shortest Path - O(V³) → O(E log V)
4. Case 4: Subsequence - O(2ⁿ) → O(n²)
5. Case 5: String Matching - O(n×m) → O(n+m)
6. Complexity Improvement Patterns
7. Conclusion

---

1. Case 1: Duplicate Removal - O(n²) → O(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

• n = 100,000
• O(n²) = 10,000,000,000 = 10 billion operations
• ~100 million ops/sec → 100 seconds → TLE!

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: 100 seconds (estimated)
• AC Code: 0.15 seconds
• Improvement: 667x faster

---

2. 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: 100 seconds (estimated)
• AC Code: 0.02 seconds
• Improvement: 5000x faster

---

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

Problem

Find the shortest path from starting point s to all vertices in a graph.

• 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!

AC Code (O(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(E log V) = 100,000 × 17 = 1,700,000

Result

• TLE Code: Impossible (10¹⁵ operations)
• AC Code: 0.3 seconds
• Improvement: Infinite (impossible → possible)

---

4. Case 4: Subsequence - O(2ⁿ) → O(n²)

Problem

Count the number of subsequences in an array that sum to K.

• 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!

AC Code (O(n²))

// Dynamic Programming
int dp[1001][100001]; // dp[i][j] = ways to make sum j using first i elements

dp[0][0] = 1;

for (int i = 0; i < n; i++) {
    for (int j = 0; j <= K; j++) {
        // Don't include i-th element
        dp[i+1][j] += dp[i][j];
        
        // Include i-th element
        if (j + arr[i] <= K) {
            dp[i+1][j + arr[i]] += dp[i][j];
        }
    }
}

cout << dp[n][K];

// Total: O(n × K) = 1,000 × 100,000 = 100 million

Result

• TLE Code: Impossible (2¹⁰⁰⁰)
• AC Code: 0.8 seconds
• Improvement: Infinite

---

5. 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

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: 100 seconds (estimated)
• AC Code: 0.05 seconds
• Improvement: 2000x faster

---

6. Complexity Improvement Patterns

Pattern 1: Duplicate Removal → 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)

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)
int sum = prefix[R+1] - prefix[L];

Pattern 3: Brute Force → Dynamic Programming

// O(2ⁿ) → O(n²) or O(n³)
void backtrack(int idx, int sum) {
    if (idx == n) { /* ... */ }
    backtrack(idx + 1, sum + arr[idx]);
    backtrack(idx + 1, sum);
}

// ↓

// DP
int dp[n+1][K+1];
for (int i = 0; i < n; i++) {
    for (int j = 0; j <= K; j++) {
        dp[i+1][j] = dp[i][j];
        if (j >= arr[i]) {
            dp[i+1][j] += dp[i][j - arr[i]];
        }
    }
}

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--;
    }
}

---

7. Time Complexity Checklist

Allowed Complexity by Input Size

Input Size n	Allowed Complexity	Algorithm Examples
n ≤ 10	O(n!)	Permutation, Brute Force
n ≤ 20	O(2ⁿ)	Bitmask DP
n ≤ 500	O(n³)	Floyd-Warshall
n ≤ 5,000	O(n²)	Bubble Sort, DP
n ≤ 100,000	O(n log n)	Sorting, Segment Tree
n ≤ 1,000,000	O(n)	Linear Search, Hash
n ≤ 10,000,000	O(log n)	Binary Search

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)

---

8. Data Structure Selection Guide

Optimal Data Structures by Operation

Operation	Data Structure	Complexity
Duplicate Removal	set	O(n log n)
Fast Search	unordered_set	O(1) average
Sorted Order	set, map	O(log n)
Range Sum	Prefix Sum Array	O(1) query
Range Minimum	Segment Tree	O(log n)
Track Maximum	priority_queue	O(log n)
LRU Cache	list + unordered_map	O(1)

---

Conclusion

Results and Lessons

Common points from the above case studies:

1. Complexity Analysis: First calculate the allowed upper bound from time limit and input size.
2. Find Bottlenecks: Suspect if you can reduce one level in nested loops, hidden sorting, or repeated checks.
3. Data Structure Selection: On top of “correct logic”, use structures with right operation cost (hash, prefix sum, heap, etc.).
4. Algorithm Improvement: Choose tools that fit problem constraints like prefix sum, DP, greedy, two pointers.

Summary: Even with correct implementation, TLE occurs if complexity exceeds limits. Before debugging, develop the habit of writing complexity on paper.

---

FAQ

Q1. Calculating complexity is difficult.

Count nested loops and multiply the iteration count of each loop. Consider function calls too.

Q2. Is the difference between O(n log n) and O(n) significant?

For small n, the difference is minimal, but for n = 1,000,000, log n = 20, so it’s a 20x difference.

Q3. Is constant time optimization needed?

Complexity improvement comes first. If complexity is the same, consider constant optimization (fast I/O, etc.).

---

Related Posts

• Algorithm Time Complexity Analysis
• C++ Coding Test I/O Optimization
• Complete Dynamic Programming Guide

---

Keywords

Algorithm, Time Complexity, Optimization, Coding Test, TLE, Time Limit Exceeded, Competitive Programming, Data Structures, Case Study, DP, Prefix Sum, KMP, Dijkstra