Problem 🤔

You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.

Implement the BrowserHistory class:

Example 1

Input

Output

Explanation

Real World Applications 🌎

You’re accessing this from a web browser? Yeah, you are :) Let’s build some naive logic for how our browser history works!

The Finer Details 🔎

Keeping track of previous and current behaviour. First in first out. FIFO… We should be thinking about stacks immediatley! So let’s explore this direction.

There’s only 1 thing that we need to look out for here! visit clears all the forward web history. This means that we need to remember to wipe the forward history after a visit. Let’s split this into two cases:

1. We’re at the edge (furthest point) in our browser history. In this case no, need to wipe anything (there’s nothing to wipe), we can just append to our history.
2. We’ve invoked vist at some other point in our browserHistory. This means that we called back at some point. At this point we need to delete our forward history! Now, we can either delete the forward cells or keep track of our last valid former position. Let’s do the latter!

Solution 💡

Complexity Analysis 🧮

Time Complexity

O(1)

All operations require constant amount of operations.

Space Complexity

O(n)

Maintain browserHistory that can have n elements

Takeaways 🎉🥳

• A classic stack question!

Resources 📚

Leetcode