Design Browser History (Optimized)

Suppose, We have a browser of one tab where we start on the homepage and we 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 with following requirements:

• BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
• void visit(string url) Visits url from the current page. It clears up all the forward history.
• string back(int steps) Move steps back in history. Assume, x is number of valid backward movements we can do from our current position. If steps > x, Return the url after moving x steps backward in history.
• string forward(int steps) Move steps forward in history. Assume, x is number of valid forward steps we can move forward from our current position. If steps > x, Return the url after moving x steps forward in history.

Intuition

Previously we have solved it using Doubly Linked List. If you didn't solve Design Browser History yet, go ahead and solve it using Doubly Linked List so that you will fully understand where we are going to optimize our code and what is the limitation of Linked List data structure.
In our previous solution we have seen back and forward taken O(n) time because Linked List doesn't have Array like indexing. To optimize that we will use ArrayList instead of Linked List. We will see that shortly.

Homepage

Let's launch the BrowserHistory instance with Homepage BrowserHistory(string homepage).

class BrowserHistory:
	def __init__(self, homepage):
		self.history = []
		self.history.append(homepage)
		self.curr = 0
		self.end = self.curr

Initially we are appending a new value homepage=leetcode in the Array at index=0. Here we are maintaining Two Pointers one is for pointing the current page another one is for last valid index. We will discuss more about the end pointer later.

Go Backward

OK Let's assume we have visited few pages after the Homepage and our ArrayList is looking like bellow.

Every time we visit a new page the Array index is getting incremented, that's the difference between Array and Linked List that Array has Index to Lookup value by index in Constant Time.

According to the picture, we can move only 2 indices backward. But the function back(steps: int) takes steps as parameter, so we need to make sure that we have not moved bellow the 0th index (i.e. Homepage), otherwise we will get IndexOutOdBound exception.
Now, suppose the back function is invoked with steps=5 like this back(steps=5) so we need to find out the Valid Index from our current index. We can simply calculate it by subtracting backIndex = (curr - steps) but there is still a chance to get the the result bellow 0.
So we will choose the Maxium value between 0 and backIndex

To find the valid Backward Index:

given, steps = 5 and curr = 2
=> backIndex = curr - steps
=> backIndex = 2 - 5
=> backIndex = -3 (which is an invalid index bellow 0th index)
=> curr = max(0, backIndex)
hence backIndex = 0

Let's visualize:

Let's implement the back function now

class BrowserHistory:
	# skipping previous codes
	def back(steps: int) -> str:
		backIndex = self.curr - steps
		self.curr = max(0, backIndex)
		return self.history[self.curr]

This operation takes O(1) times because instead of iterating through the ArrayList we have calculated our desired Array Index and Lookup the value by index.

Move Forward

After moving back to Homepage our pointers are placed like this bellow

Same as Back function but this time we will move forward from a backward index.
We can see our current pointer is at 0th index (i.e. Homepage) and we can move only 2 index forward. Same as the back function the forward(steps: int) function takes steps as input parameter, so we need to make sure that we have not moved beyond our Last Valid Index.

Guess what, len(history) - 1 is not our Last Valid Index just because of one feature that we have not implemented yet (i.e. clear up all the forward history when you visit a page). However, let's not focus on that now just think like end is our Last Valid Index.

To find the Valid Forward Index:

given, steps = 5 
we have, curr = 0 and end = 2
=> forwardIndex = curr + steps
=> forwardIndex = 0 + 5 = 5 (which is beyond the last valid index)
now we gonna choose the minimum value between end and forwardIndex
=> curr = min(end, forwardIndex)

Let's visualize:

class BrowserHistory
	# skipping previous codes
	def forward(steps: int) -> str:
		forwardIndex = self.curr + steps
		self.curr = min(self.end, forwardIndex)
		return self.history[self.curr]

This operation takes O(1) times because instead of iterating through the ArrayList we have calculated our desired Array Index and Lookup the value by index.

Visit

Now let's implement visit(url: str) function. Basically visits url from the current page and clears up all the forward history. Let's assume the ArrayList only has the homepage at 0th index, so the ArrayList is looking like bellow.

Let's visit some pages from here.

visit("Google")
visit("Youtube")
visit("Facebook")

which is looking like this

Let's Implement it

class BrowserHistory:
	def visit(self, url: str) -> None:
		# we already know homepage has added in the ArrayList 
		# so curr = 0, end = 0
		# now increment curr by 1 for our next operation
		self.curr += 1
		# appending new value in the list
		self.history.append(url)
		# setting current as end
		# because the URL we just have visited should be the latest one
		self.end = self.self

Now Go 2 steps Back

Now the current page is Google at index 1 . Let's visit a new page Wikipidia from here by invoking visit(url="wikipidia"). This is the trickiest part of this problem,

At this point curr=1 so the next index is curr + 1 = 2. We need to replace Youtube with the new value Wikipidia at index 2 and set out end pointer at index 2.

You can think this like Soft Delete operation, instead of deleting the indexing and Shifting items we are modifying the value at the specific index. Because Array shifting takes O(n) time which we are not gonna do.

Though Facebook is still there but you can not reach there because of end index validation min(end, curr + steps) in forward function. I hope you get the idea about the Significance of end pointer. However, Facebook will be updated in our next visit function call like this

Ok, Let's update our visit function

class BrowserHistory:
	def visit(self, url: str) -> None:
		self.curr += 1
		if len(self.history) > self.curr:
			# means there is already some forward history in the ArrayList like "Youtube", "Facebook" and so on.
			# let update it with the given url
			self.history[self.curr] = url
		else:
			self.history.append(url)
		
		self.end = self.curr

This operation will also take O(1) time because we are either Updating ArrayList value by Index or Appending new item in the ArrayList

Complete Code Snippet

class BrowserHistory:
	def __init__(self, homepage: str):
		self.history = []
		self.history.append(homepage)
		self.curr = 0
		self.end = self.curr
	
	def visit(self, url: str) -> None:
		self.curr += 1
		if len(self.history) > self.curr:
			# update array value by index
			self.history[self.curr] = url
		else:
			self.history.append(url)
		self.end = self.curr

	def back(self, steps: int) -> str:
		backIndex = self.curr - steps
		self.curr = max(0, backIndex)
		return self.history[self.curr]

	def forward(self, steps: int) -> str:
		forwardIndex = self.curr + steps
		self.curr = min(end, forwardIndex)
		return self.history[self.curr]

This solution is the Optimized version of Design Browser History

Complexity Analysis

• Visit: O(1) constant time, because we are either update value by index or appending at the end of the ArrayList.
• Back: O(1), Lookup value by index
• Forward: O(1) Lookup value by index

Thanks for Stopping by! Happy Leet coding

Connect with me on