What started as a simple feature in a Rock-Paper-Scissors game (tracking the most common move) quickly revealed a classic performance pitfall.
Here's how I refactored an inefficient O(n) approach into a snappy O(1) solution.
🐢 The Slow Way: Recalculate from history every time
My state looked like this:
history: {
player: ['rock', 'paper', 'rock', ...],
computer: ['scissors', 'rock', ...]
}
To get the most common move, I was doing this:
function determineMostCommonMove(moves: StandardMove[]): StandardMove | null {
if (moves.length === 0) return null;
const counts: Record<StandardMove, number> = { rock: 0, paper: 0, scissors: 0 };
for (const move of moves) {
counts[move]++;
}
return Object.entries(counts).reduce((a, b) => (b[1] > a[1] ? b : a))[0] as StandardMove;
}
Totally functional. Totally unnecessary. Every time I needed the most common move, I was reprocessing the entire move history.
That’s O(n) time complexity, where n is the number of moves played. For short games, no big deal. But if players go hundreds or thousands of rounds, the cost adds up fast.
To visualize the difference this makes:
📈 Performance Growth (Time)
^
| O(n) 🐌
| /
| /
| /
| /
| /
| /
|====================== O(1) ⚡️
+----------------------------------> Input Size (n)
⚡ The Fix: Track move counts as I go
Instead of recalculating, the core idea was to cache the counts as moves were made.
I added a new moveCounts object to my state:
moveCounts: {
player: { rock: 0, paper: 0, scissors: 0 },
computer: { rock: 0, paper: 0, scissors: 0 }
}
Now, every time a move is played, I just increment the relevant count:
private incrementMoveCount(key: Participant, move: StandardMove): void {
this.state.moveCounts[key][move] += 1;
}
And do a quick pass over the counts to get the most common move:
private determineMostCommonMove(moveCounts: MoveCount): StandardMove | null {
let mostCommonMove: StandardMove | null = null;
let highestCount = 0;
let hasMoveFrequencyTie = false;
// Iterate over the fixed number of possible moves (rock, paper, scissors)
// not the entire, ever-growing, game history.
for (const [move, count] of Object.entries(moveCounts)) {
if (count > highestCount) {
highestCount = count;
mostCommonMove = move as StandardMove;
hasMoveFrequencyTie = false;
} else if (count === highestCount && count !== 0) {
hasMoveFrequencyTie = true;
}
}
// In case of a tie in move frequency (e.g., rock: 5, paper: 5),
// return null as there's no single "most" common move.
return hasMoveFrequencyTie ? null : mostCommonMove;
}
This change also addresses a later-found bug related to handling ties in move frequency (where multiple moves occurred an equal number of times).
Now, the determineMostCommonMove function iterates only over the fixed number of possible moves (rock, paper, scissors), which is always 3. While technically O(k) where k is the number of possible moves, since k is a tiny constant and does not grow with the game history, this operation is effectively constant time, O(1)!
This means its execution time is entirely independent of how long a game may go.
✅ Before & After
Before:
Most common move was recalculated every time from the full history. O(n). Clunky.
After:
Counts are updated in real time and checked instantly. O(1). More efficient, more scalable, and simpler to reason about.
Top comments (2)
Smart move, this is what true optimization looks like.
It’s not just about working harder, but working smarter: making thoughtful decisions that maximize results with minimal wasted effort.
Optimization means constantly refining your approach, learning from experience, and finding the most effective path forward.
In both coding and career, that mindset separates good from great.
Couldn’t have said it better, love that mindset.