Introduction

If your first solution is O(n^2), the next question is whether the nested work is truly necessary or whether you are recomputing information that could be remembered. Many problems that start with a double loop can be improved to linear time by replacing repeated comparisons with a hash table, prefix state, or a single running summary.

Why O(n^2) Solutions Appear First

Quadratic solutions are common because the most direct thought process is often:

• compare every item with every other item
• scan the rest of the array for each position
• recompute a condition from scratch every time

That is easy to write, but it often means the algorithm is doing duplicate work.

A classic example is duplicate detection:

1def has_duplicate_quadratic(nums):
2    for i in range(len(nums)):
3        for j in range(i + 1, len(nums)):
4            if nums[i] == nums[j]:
5                return True
6    return False

This is clearly O(n^2).

How Problems Become Linear

The usual path to O(n) is:

1. walk through the data once
2. keep enough state to avoid rescanning old elements
3. answer each new step in constant expected time

For duplicate detection, a set is enough:

1def has_duplicate_linear(nums):
2    seen = set()
3
4    for num in nums:
5        if num in seen:
6            return True
7        seen.add(num)
8
9    return False

Now the algorithm is O(n) on average because each lookup and insertion into the set is constant expected time.

Another Example: Two-Sum

Naive version:

1def two_sum_quadratic(nums, target):
2    for i in range(len(nums)):
3        for j in range(i + 1, len(nums)):
4            if nums[i] + nums[j] == target:
5                return i, j
6    return None

Linear-time idea:

1def two_sum_linear(nums, target):
2    seen = {}
3
4    for i, num in enumerate(nums):
5        needed = target - num
6        if needed in seen:
7            return seen[needed], i
8        seen[num] = i
9
10    return None

This works because the second loop was only checking whether a complementary value had appeared before. A dictionary stores that answer directly.

When Linear Time Is Not Possible

Not every O(n^2) algorithm can be collapsed to O(n). If the problem genuinely requires examining all pairs or producing all pairwise relationships, then quadratic work may be unavoidable.

For example, if the output itself can contain O(n^2) pairs, then an O(n) total algorithm is impossible because just writing the result already costs more than linear time.

So the real question is not "can every double loop become linear". The real question is:

• is the second loop searching for something that can be remembered
• or is it generating inherently pairwise output

Common Linear-Time Tools

When trying to improve a quadratic solution, ask whether one of these helps:

• a set for membership checks
• a dict for value-to-index or value-to-count lookup
• prefix sums for repeated range totals
• two pointers on sorted data
• a frequency table when values are small integers

These are the usual patterns behind linear or near-linear improvements.

A Useful Mental Test

Look at the inner loop and ask:

"What answer is this loop searching for each time"

If the answer is something like:

• "have I seen this before"
• "does the complementary value exist"
• "what is the running total so far"

then there is a good chance a data structure can remove the repeated scan.

Common Pitfalls

• Assuming every O(n^2) solution must have a linear version.
• Ignoring output size. If the output can be quadratic, the runtime may need to be quadratic too.
• Replacing a double loop with a hash structure without checking whether the required operation is actually supported efficiently.
• Claiming an algorithm is linear while hiding a sort, which makes it O(n log n).
• Optimizing too early without first understanding exactly what the inner loop is doing.

Summary

• Many O(n^2) solutions can become O(n) when the inner loop is only searching for information that can be stored.
• Sets, dictionaries, prefix sums, and two-pointer techniques are common tools for that improvement.
• Duplicate detection and two-sum are classic examples of quadratic-to-linear upgrades.
• Not every quadratic algorithm can be made linear, especially if the output itself is pairwise.
• To judge whether linear time is possible, inspect what the repeated scan is really trying to discover.