Skip to content
← All posts

Elimination Game: Tracking the Head Through Alternating Passes

4 min read
leetcodeproblemmediummath

Elimination Game is LeetCode 390, rated Medium. You start with a list of integers from 1 to n. On the first pass, you remove every other number starting from the left. On the next pass, you remove every other surviving number starting from the right. You alternate until one number remains. Return that number.

For example, with n = 9 the sequence plays out like this: start with [1,2,3,4,5,6,7,8,9], eliminate from the left to get [2,4,6,8], eliminate from the right to get [2,6], eliminate from the left to get [6]. The answer is 6.

The key insight

Simulating the elimination directly would require storing and scanning the list each round, giving you O(n) time and space. That is far too slow when n reaches a billion.

Instead, you can track just the head, the first element of the remaining sequence. Each round, you decide whether the head needs to move. The head always advances when you eliminate from the left, because the leftmost element is removed. When you eliminate from the right, the head only moves if there is an odd number of remaining elements, because that means the leftmost element also gets caught.

After each round, the remaining count halves, and the step between consecutive survivors doubles. Three variables are enough: head, step, and remaining. The entire process runs in O(log n) time.

Start123456789Round 1 (L→R)123456789Round 2 (R→L)123456789Round 3 (L→R)123456789
Alternating elimination on 1..9. Each round removes every other remaining number. The survivor is 6.

The approach

Here is the logic, round by round:

  1. Initialize head = 1, step = 1, remaining = n, and left_to_right = True.
  2. While remaining > 1:
    • If eliminating left to right, the head moves forward by step.
    • If eliminating right to left, the head moves forward by step only when remaining is odd.
    • Double the step.
    • Halve remaining.
    • Flip the direction.
  3. Return head.

The rule for right-to-left elimination makes sense when you think about it. If you have an even count like [2, 4, 6, 8] and eliminate from the right, you remove 8 and 4, leaving [2, 6]. The head (2) did not move. But if you had [2, 4, 6] (odd count) and eliminated from the right, you would remove 6 and then 2, so the head would shift to 4.

The code

def last_remaining(n: int) -> int:
    head = 1
    step = 1
    remaining = n
    left_to_right = True

    while remaining > 1:
        if left_to_right or remaining % 2 == 1:
            head += step
        step *= 2
        remaining //= 2
        left_to_right = not left_to_right

    return head
Practice this pattern
Tracing lastRemaining(9):

Step 0: Initialize

Start with head at 1. We have 9 numbers with a step of 1, going left to right.

head =1
step =1
remaining =9
direction =left → right

The head tracks the first surviving element. The step tracks the gap between consecutive survivors.

Step 1: Round 1, left to right

Eliminating from the left always moves the head forward by one step. After this pass, every other number is gone.

head =2
step =2
remaining =4
direction =right → left

head = 1 + 1 = 2. Step doubles to 2. Remaining halves to 4. Direction flips to right-to-left.

Step 2: Round 2, right to left

Eliminating from the right with an even count of remaining elements does not move the head.

head =2
step =4
remaining =2
direction =left → right

Remaining (4) is even, so the head stays at 2. Step doubles to 4. Remaining halves to 2. Direction flips.

Step 3: Round 3, left to right

Eliminating from the left again. The head jumps forward by the current step.

head =6
step =8
remaining =1
direction =right → left

head = 2 + 4 = 6. Remaining drops to 1, so we stop. The last number standing is 6.

remaining = 1. Return head = 6.

Three iterations for n = 9. Each round halves the remaining count, giving O(log n) total work.

Drill this from memory

Complexity

TimeSpace
TotalO(log n)O(1)

Time: O(log n). Each round halves the remaining count, so you loop at most log2(n) times. Each iteration does constant work.

Space: O(1). You only store three integers and a boolean, regardless of how large n is.

Building blocks

Simulation to math reduction

Many problems tempt you into simulating the full process. The Elimination Game teaches you to ask: "Can I track just the state I care about instead of the entire structure?" Here, the state is the head position, and the structure is the full list.

This pattern appears often. In Bulb Switcher, you reduce toggling all bulbs to counting perfect squares. In Nim Game, you skip simulating turns and jump to a divisibility check. The common thread is recognizing that the answer depends on a small set of variables that you can update in closed form, not on replaying every operation.

When you see a problem where simulating N steps takes O(n) per step, always ask: "What minimal state changes per step, and can I compute it directly?"

Edge cases

  • n = 1. Only one element, return 1. The while loop never executes.
  • n = 2. After one left-to-right pass, 1 is removed. Return 2.
  • Large n (up to 10^9). The O(log n) solution handles this in about 30 iterations, no issue with time or space.

From understanding to recall

You have seen how tracking the head avoids simulating the full elimination. The logic is compact, but reproducing it under pressure requires knowing exactly when the head moves and when it stays. That is the kind of detail that slips away after a few days.

Spaced repetition locks it in. CodeBricks breaks this problem into its building block, the simulation-to-math reduction, and drills it at increasing intervals. You type the solution from understanding, not from rote memory. After a few review cycles, the head-tracking logic becomes automatic.

Try CodeBricks free

Related posts