Every editor you've ever used — a text editor, a Figma canvas, a database GUI — keeps a history of what you've done so you can step backwards (undo) and forwards (redo) through it. You're going to build the data structure that makes that possible: a small class that tracks a sequence of values, remembers a cursor into that sequence, and exposes navigation methods.
Implement UndoRedoManager(initial). It accepts a starting value and exposes five methods. current() returns the value at the cursor. set(value) records value as the new current and advances the cursor — and, importantly, if you're sitting in the middle of the history (you've undone a few steps), set BRANCHES: it drops everything past the cursor before recording the new value. undo() steps the cursor backwards one place and returns the value now under it. redo() steps forwards. canUndo() and canRedo() are booleans reporting whether each direction has somewhere to go.
class UndoRedoManager {
constructor(initial)
current() // -> the value at the cursor
set(value) // record value as new current; drops any redo tail
undo() // step cursor back; returns the value now under it
redo() // step cursor forward; returns the value now under it
canUndo() // -> boolean: is there anywhere to go back to?
canRedo() // -> boolean: is there anywhere to go forward to?
}// Basic linear edits
const m = new UndoRedoManager(1);
m.current(); // 1
m.set(2);
m.set(3);
m.current(); // 3
m.canUndo(); // true
m.canRedo(); // false// An undo/redo round trip
const m = new UndoRedoManager('a');
m.set('b');
m.set('c');
m.undo(); // 'b' (cursor steps back one)
m.undo(); // 'a' (back to the start)
m.canUndo(); // false
m.redo(); // 'b' (cursor steps forward)
m.current(); // 'b'// set() in the middle of history BRANCHES — drops the redo tail
const m = new UndoRedoManager(1);
m.set(2);
m.set(3);
m.undo(); // 2 (cursor is now in the middle)
m.set(4); // branch! "3" is dropped from history
m.canRedo(); // false — there is no 3 to redo to anymore
m.undo(); // 2
m.redo(); // 4canUndo() is false and undo() is a no-op that returns the current value. Don't throw and don't return undefined.canRedo() is false and redo() is a no-op that returns the current value. Same rule.set always branches when there is a redo tail. This is the defining behaviour. After set, canRedo() must be false.set(v) with the same value still records a new history entry. Equality detection is out of scope.set mutates the history entry too. Treat values as immutable, or clone them yourself.maxSize option is discussed in the solution but not part of this spec.You'll keep one array of snapshots and one integer cursor pointing at the current value; undo and redo move the cursor; set truncates anything past the cursor before appending.
A user clicks around a form, types some text, then thinks: "no, undo that." A few seconds later: "actually, redo it." That's the feature. You need a tiny data structure that remembers every value the user has committed, can step backwards through them on undo, can step forwards again on redo, and — the subtle bit — knows how to "branch" cleanly when the user makes a new edit while sitting in the middle of history. Once they branch, the future they undid is gone.
Picture history as a horizontal strip of cards laid left-to-right, one card per set call (plus one for the initial value). A small arrow — the cursor — points at the card you're currently on. current() reads off that card. undo() slides the arrow one card left; redo() slides it one card right. The cards themselves never move; only the cursor does. That single picture is the whole solution.
The most common first instinct is to reach for two stacks: an undoStack you push onto when the user sets a new value, and a redoStack you push onto when the user undoes. It feels right — undo pops from one and pushes onto the other; redo does the reverse.
// naive — two-stack version
class UndoRedoManager {
constructor(initial) {
this.undoStack = [initial];
this.redoStack = [];
}
current() { return this.undoStack[this.undoStack.length - 1]; }
set(value) {
this.undoStack.push(value);
// BUG: forgot to clear redoStack here
}
undo() {
if (this.undoStack.length <= 1) return this.current();
this.redoStack.push(this.undoStack.pop());
return this.current();
}
redo() {
if (this.redoStack.length === 0) return this.current();
this.undoStack.push(this.redoStack.pop());
return this.current();
}
}The linear case works, but the branch-on-set semantic is awkward to bolt on. You have to remember to clear redoStack inside set, and it's the kind of detail that gets quietly dropped during a refactor. When it's missing, the bug is silent and surprising: the user types a value, then calls redo(), and gets a value they undid five minutes ago and then explicitly overwrote. They have no idea where it came from. Two stacks aren't wrong, just brittle — the "future" of history is implicit in a separate place from the "past", and keeping them coherent is a chore.
Collapse the two stacks into one array plus a cursor. The cursor is "where you are"; everything to the left is the past, everything to the right is the future, and set simply chops off the future before appending.
class UndoRedoManager {
constructor(initial) {
// One array holds every snapshot, oldest at index 0.
// The constructor seeds it with the initial value, so the
// manager always has a current value to return — there's
// no "empty" state we'd need to handle.
this.history = [initial];
// cursor points at the CURRENT value's index, not the next
// free slot. That convention makes current() a one-liner
// and makes the canUndo / canRedo boundary checks obvious.
this.cursor = 0;
}
current() {
return this.history[this.cursor];
}
set(value) {
// Truncate the redo tail FIRST. Setting `.length` shorter
// than the current length is the fastest way to drop
// entries past the cursor; it's an O(1) array op in V8.
// This is the branch-on-set step — once we record a new
// value mid-history, the old future is gone.
this.history.length = this.cursor + 1;
// Now append the new value and advance the cursor onto it.
this.history.push(value);
this.cursor++;
}
undo() {
// Guard against walking off the left edge. We return the
// current value (not undefined, not throw) so callers can
// wire undo() straight into a button handler without
// bothering to check canUndo() first — the no-op case
// still gives them something sensible.
if (this.cursor > 0) this.cursor--;
return this.history[this.cursor];
}
redo() {
// Mirror of undo on the right edge.
if (this.cursor < this.history.length - 1) this.cursor++;
return this.history[this.cursor];
}
canUndo() {
// cursor > 0 means there's at least one snapshot to the
// left of where we are.
return this.cursor > 0;
}
canRedo() {
// cursor < length - 1 means there's at least one snapshot
// to the right. Using `length - 1` (not `length`) because
// cursor is an INDEX, not a count.
return this.cursor < this.history.length - 1;
}
}
module.exports = { UndoRedoManager };Three things this design buys you over the two-stack version. First, the branch-on-set rule is impossible to forget — it's the first line of set, and without it the rest of set would be wrong. Second, there's no synchronization to maintain between two collections; one array, one number, one source of truth. Third, every boolean check (canUndo, canRedo) and every read (current) is a single line that reads as plain English: "is the cursor greater than zero?"
Take this concrete sequence: const m = new UndoRedoManager(1); m.set(2); m.set(3); m.undo(); m.set(4); m.redo(); and trace the array and cursor at every step.
new UndoRedoManager(1) — history = [1], cursor = 0. current() returns 1. canUndo false, canRedo false.m.set(2) — first history.length = cursor + 1 = 1 (no-op, already length 1). Then history.push(2) → [1, 2]. Then cursor++ → cursor = 1. current() returns 2.m.set(3) — history.length = 2 (no-op). Push 3 → [1, 2, 3]. cursor++ → 2. current() returns 3.m.undo() — cursor > 0, so decrement → cursor = 1. Return history[1] = 2. Array is unchanged: [1, 2, 3]. canRedo is now true because 3 is still there at index 2.m.set(4) — and here's the branch. First history.length = cursor + 1 = 2, which truncates the array to [1, 2], dropping the 3. Then push 4 → [1, 2, 4]. Then cursor++ → 2. current() returns 4. canRedo is now false — there is no entry to the right of index 2.m.redo() — cursor < history.length - 1 is 2 < 2, false. The guard prevents any movement, and we just return history[cursor] = 4. No-op, as documented.The 3 is genuinely gone. If the user wants it back, they have to re-type it. That's the branch semantic, and it matches how every text editor and design tool you've used works.
set — if you write set(value) { this.history.push(value); this.cursor++; } and skip this.history.length = this.cursor + 1, redo will resurrect values the user explicitly overwrote. The user undoes from 3 back to 2, types 4, then accidentally hits redo and sees 3 again — a "ghost" value they have no model for. Always truncate first.m.set(obj) stores obj itself, not a copy. If you mutate obj later, the history entry mutates too — undo will appear to "not work" because the snapshot has silently changed. Either treat values you pass to set as immutable, or clone them at the call site (m.set(structuredClone(obj))).history only ever grows (within a single branch). A long-running editor session could accumulate thousands of snapshots. If each is a 50KB object, you've handed the GC a problem. See "Going further" for the maxSize extension.undo() at the start, redo() at the end — return the current value rather than undefined or throwing. It makes the methods safe to wire directly to button handlers without a canUndo check, which is the common case.canRedo — the right boundary is cursor < history.length - 1, not <=. If history.length is 3, valid cursor positions are 0, 1, 2; only when cursor is 0 or 1 is there something to redo to. Using <= would lie and redo() would no-op while canRedo claimed otherwise.maxSize — accept a constructor option and drop the oldest snapshot whenever history.length exceeds it. Subtract one from cursor each time you drop, otherwise the cursor will point at the wrong slot.{ do, undo } function pairs. undo replays the inverse; redo replays the forward action. Saves memory on large states but forces every caller to author the reverse operation. Right answer for document editors and vector canvases where a snapshot would be megabytes; wrong answer for primitives where the snapshot is a number.sets — in a text editor, every keystroke is a set. Naively that's one history entry per keystroke and undo becomes per-character, which users hate. Bucket set calls within a short time window (say 500ms with no intervening pause) into a single history entry.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Every editor you've ever used — a text editor, a Figma canvas, a database GUI — keeps a history of what you've done so you can step backwards (undo) and forwards (redo) through it. You're going to build the data structure that makes that possible: a small class that tracks a sequence of values, remembers a cursor into that sequence, and exposes navigation methods.
Implement UndoRedoManager(initial). It accepts a starting value and exposes five methods. current() returns the value at the cursor. set(value) records value as the new current and advances the cursor — and, importantly, if you're sitting in the middle of the history (you've undone a few steps), set BRANCHES: it drops everything past the cursor before recording the new value. undo() steps the cursor backwards one place and returns the value now under it. redo() steps forwards. canUndo() and canRedo() are booleans reporting whether each direction has somewhere to go.
class UndoRedoManager {
constructor(initial)
current() // -> the value at the cursor
set(value) // record value as new current; drops any redo tail
undo() // step cursor back; returns the value now under it
redo() // step cursor forward; returns the value now under it
canUndo() // -> boolean: is there anywhere to go back to?
canRedo() // -> boolean: is there anywhere to go forward to?
}// Basic linear edits
const m = new UndoRedoManager(1);
m.current(); // 1
m.set(2);
m.set(3);
m.current(); // 3
m.canUndo(); // true
m.canRedo(); // false// An undo/redo round trip
const m = new UndoRedoManager('a');
m.set('b');
m.set('c');
m.undo(); // 'b' (cursor steps back one)
m.undo(); // 'a' (back to the start)
m.canUndo(); // false
m.redo(); // 'b' (cursor steps forward)
m.current(); // 'b'// set() in the middle of history BRANCHES — drops the redo tail
const m = new UndoRedoManager(1);
m.set(2);
m.set(3);
m.undo(); // 2 (cursor is now in the middle)
m.set(4); // branch! "3" is dropped from history
m.canRedo(); // false — there is no 3 to redo to anymore
m.undo(); // 2
m.redo(); // 4canUndo() is false and undo() is a no-op that returns the current value. Don't throw and don't return undefined.canRedo() is false and redo() is a no-op that returns the current value. Same rule.set always branches when there is a redo tail. This is the defining behaviour. After set, canRedo() must be false.set(v) with the same value still records a new history entry. Equality detection is out of scope.set mutates the history entry too. Treat values as immutable, or clone them yourself.maxSize option is discussed in the solution but not part of this spec.You'll keep one array of snapshots and one integer cursor pointing at the current value; undo and redo move the cursor; set truncates anything past the cursor before appending.
A user clicks around a form, types some text, then thinks: "no, undo that." A few seconds later: "actually, redo it." That's the feature. You need a tiny data structure that remembers every value the user has committed, can step backwards through them on undo, can step forwards again on redo, and — the subtle bit — knows how to "branch" cleanly when the user makes a new edit while sitting in the middle of history. Once they branch, the future they undid is gone.
Picture history as a horizontal strip of cards laid left-to-right, one card per set call (plus one for the initial value). A small arrow — the cursor — points at the card you're currently on. current() reads off that card. undo() slides the arrow one card left; redo() slides it one card right. The cards themselves never move; only the cursor does. That single picture is the whole solution.
The most common first instinct is to reach for two stacks: an undoStack you push onto when the user sets a new value, and a redoStack you push onto when the user undoes. It feels right — undo pops from one and pushes onto the other; redo does the reverse.
// naive — two-stack version
class UndoRedoManager {
constructor(initial) {
this.undoStack = [initial];
this.redoStack = [];
}
current() { return this.undoStack[this.undoStack.length - 1]; }
set(value) {
this.undoStack.push(value);
// BUG: forgot to clear redoStack here
}
undo() {
if (this.undoStack.length <= 1) return this.current();
this.redoStack.push(this.undoStack.pop());
return this.current();
}
redo() {
if (this.redoStack.length === 0) return this.current();
this.undoStack.push(this.redoStack.pop());
return this.current();
}
}The linear case works, but the branch-on-set semantic is awkward to bolt on. You have to remember to clear redoStack inside set, and it's the kind of detail that gets quietly dropped during a refactor. When it's missing, the bug is silent and surprising: the user types a value, then calls redo(), and gets a value they undid five minutes ago and then explicitly overwrote. They have no idea where it came from. Two stacks aren't wrong, just brittle — the "future" of history is implicit in a separate place from the "past", and keeping them coherent is a chore.
Collapse the two stacks into one array plus a cursor. The cursor is "where you are"; everything to the left is the past, everything to the right is the future, and set simply chops off the future before appending.
class UndoRedoManager {
constructor(initial) {
// One array holds every snapshot, oldest at index 0.
// The constructor seeds it with the initial value, so the
// manager always has a current value to return — there's
// no "empty" state we'd need to handle.
this.history = [initial];
// cursor points at the CURRENT value's index, not the next
// free slot. That convention makes current() a one-liner
// and makes the canUndo / canRedo boundary checks obvious.
this.cursor = 0;
}
current() {
return this.history[this.cursor];
}
set(value) {
// Truncate the redo tail FIRST. Setting `.length` shorter
// than the current length is the fastest way to drop
// entries past the cursor; it's an O(1) array op in V8.
// This is the branch-on-set step — once we record a new
// value mid-history, the old future is gone.
this.history.length = this.cursor + 1;
// Now append the new value and advance the cursor onto it.
this.history.push(value);
this.cursor++;
}
undo() {
// Guard against walking off the left edge. We return the
// current value (not undefined, not throw) so callers can
// wire undo() straight into a button handler without
// bothering to check canUndo() first — the no-op case
// still gives them something sensible.
if (this.cursor > 0) this.cursor--;
return this.history[this.cursor];
}
redo() {
// Mirror of undo on the right edge.
if (this.cursor < this.history.length - 1) this.cursor++;
return this.history[this.cursor];
}
canUndo() {
// cursor > 0 means there's at least one snapshot to the
// left of where we are.
return this.cursor > 0;
}
canRedo() {
// cursor < length - 1 means there's at least one snapshot
// to the right. Using `length - 1` (not `length`) because
// cursor is an INDEX, not a count.
return this.cursor < this.history.length - 1;
}
}
module.exports = { UndoRedoManager };Three things this design buys you over the two-stack version. First, the branch-on-set rule is impossible to forget — it's the first line of set, and without it the rest of set would be wrong. Second, there's no synchronization to maintain between two collections; one array, one number, one source of truth. Third, every boolean check (canUndo, canRedo) and every read (current) is a single line that reads as plain English: "is the cursor greater than zero?"
Take this concrete sequence: const m = new UndoRedoManager(1); m.set(2); m.set(3); m.undo(); m.set(4); m.redo(); and trace the array and cursor at every step.
new UndoRedoManager(1) — history = [1], cursor = 0. current() returns 1. canUndo false, canRedo false.m.set(2) — first history.length = cursor + 1 = 1 (no-op, already length 1). Then history.push(2) → [1, 2]. Then cursor++ → cursor = 1. current() returns 2.m.set(3) — history.length = 2 (no-op). Push 3 → [1, 2, 3]. cursor++ → 2. current() returns 3.m.undo() — cursor > 0, so decrement → cursor = 1. Return history[1] = 2. Array is unchanged: [1, 2, 3]. canRedo is now true because 3 is still there at index 2.m.set(4) — and here's the branch. First history.length = cursor + 1 = 2, which truncates the array to [1, 2], dropping the 3. Then push 4 → [1, 2, 4]. Then cursor++ → 2. current() returns 4. canRedo is now false — there is no entry to the right of index 2.m.redo() — cursor < history.length - 1 is 2 < 2, false. The guard prevents any movement, and we just return history[cursor] = 4. No-op, as documented.The 3 is genuinely gone. If the user wants it back, they have to re-type it. That's the branch semantic, and it matches how every text editor and design tool you've used works.
set — if you write set(value) { this.history.push(value); this.cursor++; } and skip this.history.length = this.cursor + 1, redo will resurrect values the user explicitly overwrote. The user undoes from 3 back to 2, types 4, then accidentally hits redo and sees 3 again — a "ghost" value they have no model for. Always truncate first.m.set(obj) stores obj itself, not a copy. If you mutate obj later, the history entry mutates too — undo will appear to "not work" because the snapshot has silently changed. Either treat values you pass to set as immutable, or clone them at the call site (m.set(structuredClone(obj))).history only ever grows (within a single branch). A long-running editor session could accumulate thousands of snapshots. If each is a 50KB object, you've handed the GC a problem. See "Going further" for the maxSize extension.undo() at the start, redo() at the end — return the current value rather than undefined or throwing. It makes the methods safe to wire directly to button handlers without a canUndo check, which is the common case.canRedo — the right boundary is cursor < history.length - 1, not <=. If history.length is 3, valid cursor positions are 0, 1, 2; only when cursor is 0 or 1 is there something to redo to. Using <= would lie and redo() would no-op while canRedo claimed otherwise.maxSize — accept a constructor option and drop the oldest snapshot whenever history.length exceeds it. Subtract one from cursor each time you drop, otherwise the cursor will point at the wrong slot.{ do, undo } function pairs. undo replays the inverse; redo replays the forward action. Saves memory on large states but forces every caller to author the reverse operation. Right answer for document editors and vector canvases where a snapshot would be megabytes; wrong answer for primitives where the snapshot is a number.sets — in a text editor, every keystroke is a set. Naively that's one history entry per keystroke and undo becomes per-character, which users hate. Bucket set calls within a short time window (say 500ms with no intervening pause) into a single history entry.Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.