Elimination Game solution and explanation
Google
9 more videos on this problem
Leetcode Medium 390, Elimination Game, One line Python solutionCodingCat · 6:32 · 12K views
Elimination Game | leetcode explanation | Leetcode MediumBinaryMagic · 19:42 · 11K views
Amazon Coding Interview Question | Leetcode 390 | Elimination GameWorkWithGoogler · 8:12 · 9K views
390. Elimination Game (Leetcode Medium)Programming Live with Larry · 1:00:17 · 2K views
Leetcode Elimination Game TutorialAndrew Rasvanis · 10:08 · 1K views
leetcode 390 elimination game 解法Ming Dai · 4:50 · 1K views
Leetcode 390 Squid GameBborian · 9:05 · 1K views
#LeetCode 390 | Elimination Game #JavaSleepy Cracker · 9:14 · 945 views
Elimination Game (Medium), Leetcode, C++H William Polenz · 1:16:26 · 276 views
Elimination GameRavi Shankar Kumar · 41:53 · 235 views
The problem
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).
def lastRemaining(n):
head = 1
step = 1
remaining = n
left = True
while remaining > 1:
if left or remaining % 2 == 1:
head += step
remaining //= 2
step *= 2
left = not left
return head
print(lastRemaining(9)) # Output: 6class Solution {
public int lastRemaining(int n) {
int head = 1;
int step = 1;
int remaining = n;
boolean left = true;
while (remaining > 1) {
if (left || remaining % 2 == 1) {
head += step;
}
remaining /= 2;
step *= 2;
left = !left;
}
return head;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.lastRemaining(9)); // Output: 6
}
}#include <iostream>
int lastRemaining(int n) {
int head = 1;
int step = 1;
int remaining = n;
bool left = true;
while (remaining > 1) {
if (left || remaining % 2 == 1) {
head += step;
}
remaining /= 2;
step *= 2;
left = !left;
}
return head;
}
int main() {
std::cout << lastRemaining(9) << std::endl; // Output: 6
return 0;
}function lastRemaining(n) {
let head = 1;
let step = 1;
let remaining = n;
let left = true;
while (remaining > 1) {
if (left || remaining % 2 === 1) {
head += step;
}
remaining = Math.floor(remaining / 2);
step *= 2;
left = !left;
}
return head;
}
console.log(lastRemaining(9)); // Output: 6#include <stdio.h>
int lastRemaining(int n) {
int head = 1;
int step = 1;
int remaining = n;
int left = 1;
while (remaining > 1) {
if (left || remaining % 2 == 1) {
head += step;
}
remaining /= 2;
step *= 2;
left = !left;
}
return head;
}
int main() {
printf("%d\n", lastRemaining(9)); // Output: 6
return 0;
}using System;
public class Solution {
public int LastRemaining(int n) {
int head = 1;
int step = 1;
int remaining = n;
bool left = true;
while (remaining > 1) {
if (left || remaining % 2 == 1) {
head += step;
}
remaining /= 2;
step *= 2;
left = !left;
}
return head;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LastRemaining(9)); // Output: 6
}
}In Python, the variable left acts as a boolean to determine the direction of removal. The function iteratively halves the remaining elements and doubles the step size, updating the head when necessary, i.e., when removing from the left or handling odd count from the right.
Time Complexity: O(log n) as the element count halves each iteration.
Space Complexity: O(1) since the function maintains constant space usage.
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.
def lastRemainingSimulate(n):
arr = list(range(1, n + 1))
left = True
while len(arr) > 1:
if left:
arr = arr[1::2]
else:
arr = arr[::-2][::-1]
left = not left
return arr[0]
print(lastRemainingSimulate(9)) # Output: 6This 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.
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
func lastRemaining(n int) int {
a1, an, step := 1, n, 1
for i, cnt := 0, n; cnt > 1; cnt, step, i = cnt>>1, step<<1, i+1 {
if i%2 == 1 {
an -= step
if cnt%2 == 1 {
a1 += step
}
} else {
a1 += step
if cnt%2 == 1 {
an -= step
}
}
}
return a1
}Complexity comparison
| Approach | Complexity |
|---|---|
| Mathematical Simulation with Two Pointer Reduction | Time Complexity: O(log n) as the element count halves each iteration. |
| 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 | – |
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. |
Frequently asked questions
Is Elimination Game easy or hard?
Elimination Game is rated Medium difficulty on LeetCode with an acceptance rate around 46%. The challenge is recognizing the mathematical pattern behind the eliminations instead of simulating the entire list. Once the head and step pattern is understood, the implementation becomes short and efficient.
Elimination Game Python/Java solution
In Python or Java, implement the mathematical approach using variables for head, step, remaining elements, and direction. Update these values after each elimination round until only one element remains. The implementation runs in O(log n) time and O(1) space in both languages.
How to solve Elimination Game in O(log n)?
Track four variables: the current head value, the step size between numbers, the remaining count, and the direction of elimination. When eliminating from the left, the head always moves forward by the step. When eliminating from the right, the head moves only if the remaining count is odd. After each round, halve the count and double the step until one number remains.
What is the best approach for Elimination Game?
The optimal solution uses a mathematical simulation that tracks the head of the sequence, the step size between remaining numbers, the direction of elimination, and the remaining count. After each round, half of the numbers are removed and the step size doubles. This reduces the process to about log2(n) rounds, giving O(log n) time and O(1) space.
Is Elimination Game asked at Google/Amazon/Meta?
Elimination Game appears in interview preparation sets and has been reported in coding rounds at companies that emphasize algorithmic reasoning. The problem tests mathematical pattern recognition and simulation logic, which are common in interviews at companies like Google, Amazon, and Meta.
What data structure is used in Elimination Game?
The optimal solution does not require a data structure like an array or list. Instead, it uses constant variables to track the sequence mathematically. A brute-force simulation may use an array or list to repeatedly remove elements, but that approach is less efficient.
What is the time complexity of Elimination Game?
The optimal mathematical approach runs in O(log n) time because each elimination round halves the number of remaining elements. The step size doubles each round while only a few variables are updated. Space complexity stays O(1) since no array or list is stored.