Elimination Game - Solution & Explanation
Problem Statement
You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:
- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.
Example 1:
Input: n = 9 Output: 6 Explanation: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6]
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 109
Approach Overview
Problem Overview: You start with numbers from 1 to n. In the first pass, remove every second number from left to right. In the next pass, remove every second number from right to left. Continue alternating directions until only one number remains. Return that final number.
Approach 1: Simulating the Elimination Process (O(n) time, O(n) space)
The most straightforward way is to simulate the list of numbers and repeatedly remove every second element. Start with an array [1..n], iterate through it, and keep only the numbers that survive each round. After each pass, reverse the direction of traversal to match the alternating rule. Each round roughly halves the list size, so the total work across all rounds is about n + n/2 + n/4 ..., which gives O(n) time and O(n) space for storing the list. This approach is useful for understanding the elimination pattern but wastes memory and does unnecessary copying.
Approach 2: Mathematical Simulation with Two Pointer Reduction (O(log n) time, O(1) space)
The key observation is that you never need the full list. You only need to track the first remaining number, the step size between surviving numbers, the remaining count, and the elimination direction. After each round, half of the numbers disappear, the step size doubles, and the direction flips. When eliminating from the left, the head always moves forward by step. When eliminating from the right, the head only moves if the remaining count is odd. This compact mathematical simulation reduces the problem to about log₂(n) rounds, giving O(log n) time with constant space. The reasoning relies on patterns in arithmetic progressions and alternating passes, which ties closely to math reasoning and can also be expressed recursively using recursion.
Recommended for interviews: The mathematical reduction approach is what interviewers expect. A quick brute-force simulation shows you understand the elimination process, but recognizing the arithmetic pattern and tracking the head, step, and direction demonstrates stronger algorithmic insight and reduces the complexity to O(log n) time and O(1) space.
Approach 1: Mathematical Simulation with Two Pointer Reduction
This approach involves simulating the elimination process using a mathematical understanding of how the starting point changes after each pass. This allows us to avoid explicitly generating large lists, and instead make calculations based on the current sequence step size and direction of elimination (left-to-right or right-to-left).
The function lastRemaining initializes variables: head (to track the first remaining number), step (the distance between elements in current round), and remaining (number of elements left). We iterate until only one element remains. On each iteration, it checks if the removal is left-to-right or if the number of elements is odd in right-to-left for incrementing the head.
Complexity
Time Complexity: O(log n) since at most log n passes are made.
Space Complexity: O(1) because only a constant amount of space is used.
Approach 2: Simulating the Elimination Process
In this approach, we simulate the elimination process using a loop that iterates over a range of elements. This involves maintaining an explicit list and repetitively modifying it by alternating between left-to-right and right-to-left eliminations until a single element remains. Although this direct simulation ensures clarity by closely following the problem description, it is less optimal for larger inputs.
This Python solution creates a list from 1 through n. It uses slicing to remove elements by skipping every other one: [1::2] takes every other starting from index 1 (left-to-right), and [::-2] reverses the list and takes every other element (right-to-left). The process repeats alternately until one number remains.
Code
Python
Complexity
Time Complexity: O(n log n) as slicing operations are used starting from size n and halving with each pass.
Space Complexity: O(n) due to maintaining a list of size initially equal to n.
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Mathematical Simulation with Two Pointer Reduction | Time Complexity: O(log n) since at most log n passes are made. |
| Simulating the Elimination Process | Time Complexity: O(n log n) as slicing operations are used starting from size n and halving with each pass. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulating the Elimination Process | O(n) | O(n) | Good for understanding the elimination pattern or during initial brute-force reasoning. |
| Mathematical Simulation with Two Pointer Reduction | O(log n) | O(1) | Best for interviews and production solutions where minimal time and memory are required. |
Video Solution
Leetcode Medium 390, Elimination Game, One line Python solution • CodingCat • 12,611 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Elimination Game easy or hard?
Elimination Game Python/Java solution
How to solve Elimination Game in O(log n)?
What is the best approach for Elimination Game?
Is Elimination Game asked at Google/Amazon/Meta?
What data structure is used in Elimination Game?
What is the time complexity of Elimination Game?
Ready to solve this problem?
Practice Elimination Game with our built-in code editor and test cases.
Practice on FleetCode