[2026] 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²))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))

아래 코드는 cpp를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

// 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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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³))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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ⁿ))

다음은 cpp를 활용한 상세한 구현 코드입니다. 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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²))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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))

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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

아래 코드는 cpp를 사용한 구현 예제입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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

다음은 cpp를 활용한 상세한 구현 코드입니다. 반복문으로 데이터를 처리합니다, 조건문으로 분기 처리를 수행합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

// 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