Introduction

The Codewars twice-linear kata times out when the implementation generates too many candidates and keeps re-sorting them. The sequence has enough structure that you can build it in order with two moving indices and no repeated global cleanup. Once that shift is made, the solution becomes both fast and easy to reason about.

Why Naive Solutions Slow Down

The sequence starts with u[0] = 1. For every value x already in the sequence, two new candidates appear:

• '2x + 1'
• '3x + 1'

The slow approach is to keep throwing those candidates into a set or list, sorting repeatedly, and deduplicating over and over. That works for small tests, but the repeated sorting and structure churn dominate the runtime as n grows.

Even if each individual step seems reasonable, the total work becomes much larger than necessary because the solution keeps reorganizing data it already knows is mostly ordered.

The Key Observation: Two Sorted Streams

If the sequence u itself is increasing, then the generated values 2 * u[i] + 1 and 3 * u[j] + 1 also appear in increasing order as i and j move forward. That means you do not need a global sort. You only need to merge two already ordered streams.

This is the same idea used in many efficient sequence-generation problems: generate the next candidate from each source, pick the smaller one, append it, and advance the relevant pointer.

1def dbl_linear(n: int) -> int:
2    values = [1]
3    i = 0
4    j = 0
5
6    while len(values) <= n:
7        a = 2 * values[i] + 1
8        b = 3 * values[j] + 1
9        nxt = min(a, b)
10        values.append(nxt)
11
12        if nxt == a:
13            i += 1
14        if nxt == b:
15            j += 1
16
17    return values[n]

This loop grows the sequence directly in sorted order. There is no heap, no repeated sort, and no expensive full deduplication pass.

Why Advancing Both Pointers Matters

Some values can be generated from both streams. If you only advance one pointer when the candidates are equal, the duplicate value will appear again later.

That is why the solution checks both conditions separately:

1if nxt == a:
2    i += 1
3if nxt == b:
4    j += 1

This is the detail that often separates a correct fast solution from a nearly correct one that either duplicates values or drifts off the expected sequence.

Validate Correctness Before Benchmarking

Performance only matters after the sequence is correct. A small known-prefix test is usually enough to catch off-by-one errors and duplicate-handling mistakes.

1expected = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22]
2for index, expected_value in enumerate(expected):
3    assert dbl_linear(index) == expected_value
4
5print("checks passed")

Once those checks succeed, you can benchmark a larger index to confirm the timeout problem is actually gone.

1import time
2
3start = time.perf_counter()
4answer = dbl_linear(50000)
5elapsed = time.perf_counter() - start
6
7print(answer)
8print(round(elapsed, 3))

This is the right order of work: correctness first, then performance.

Dynamic Programming Is Not the Main Idea Here

People often describe this solution as dynamic programming, but the more helpful mental model is ordered generation with merging pointers. The algorithm stores previous sequence values, but the real win comes from exploiting the monotonic structure of the candidate streams.

That distinction matters because it keeps you focused on the right optimization. If you think "DP," you may reach for memoization without fixing the real bottleneck. If you think "merge two increasing sources," the linear solution becomes obvious.

The Same Structure Works in Other Languages

The approach is not Python-specific. Here is the same idea in JavaScript:

1function dblLinear(n) {
2  const values = [1];
3  let i = 0;
4  let j = 0;
5
6  while (values.length <= n) {
7    const a = 2 * values[i] + 1;
8    const b = 3 * values[j] + 1;
9    const next = Math.min(a, b);
10    values.push(next);
11
12    if (next === a) i++;
13    if (next === b) j++;
14  }
15
16  return values[n];
17}

That makes it clear the speedup comes from the algorithm, not from a language trick or a library choice.

Common Pitfalls

The most common mistake is repeatedly sorting candidate collections inside the loop. Another is using a set-heavy solution that looks clean but adds too much overhead. People also often forget to advance both pointers on equal values, or they benchmark only tiny inputs and conclude the slow approach is good enough.

Summary

• The twice-linear sequence can be generated by merging two increasing candidate streams.
• Repeated sorting and deduplication are the usual cause of timeouts.
• A two-pointer solution builds values directly in order.
• Advancing both pointers on equal candidates is essential.
• Validate the prefix first, then benchmark large inputs to confirm the fix.