1472. Design Browser History

Approach 1: Array

• Time: $O(1)$
• Space: $O(n)$

C++JavaPython

class BrowserHistory {
 public:
  BrowserHistory(string homepage) {
    visit(homepage);
  }

  void visit(string url) {
    if (++index < urls.size())
      urls[index] = url;
    else
      urls.push_back(url);
    lastIndex = index;
  }

  string back(int steps) {
    index = max(0, index - steps);
    return urls[index];
  }

  string forward(int steps) {
    index = min(lastIndex, index + steps);
    return urls[index];
  }

 private:
  vector<string> urls;
  int index = -1;
  int lastIndex = -1;
};

class BrowserHistory {
  public BrowserHistory(String homepage) {
    visit(homepage);
  }

  public void visit(String url) {
    if (++index < urls.size())
      urls.set(index, url);
    else
      urls.add(url);
    lastIndex = index;
  }

  public String back(int steps) {
    index = Math.max(0, index - steps);
    return urls.get(index);
  }

  public String forward(int steps) {
    index = Math.min(lastIndex, index + steps);
    return urls.get(index);
  }

  private List<String> urls = new ArrayList<>();
  private int index = -1;
  private int lastIndex = -1;
}

class BrowserHistory:
  def __init__(self, homepage: str):
    self.urls = []
    self.index = -1
    self.lastIndex = -1
    self.visit(homepage)

  def visit(self, url: str) -> None:
    self.index += 1
    if self.index < len(self.urls):
      self.urls[self.index] = url
    else:
      self.urls.append(url)
    self.lastIndex = self.index

  def back(self, steps: int) -> str:
    self.index = max(0, self.index - steps)
    return self.urls[self.index]

  def forward(self, steps: int) -> str:
    self.index = min(self.lastIndex, self.index + steps)
    return self.urls[self.index]

Approach 2: Stack

• Time:
  • Constructor
  • visit(url: str): $O(1)$
  • back(steps: int): $O(\texttt{steps})$
  • forward(steps: int): $O(\texttt{steps})$
• Space: $O(n)$

C++JavaPython

class BrowserHistory {
 public:
  BrowserHistory(string homepage) {
    visit(homepage);
  }

  void visit(string url) {
    history.push(url);
    future = stack<string>();
  }

  string back(int steps) {
    while (history.size() > 1 && steps-- > 0)
      future.push(history.top()), history.pop();
    return history.top();
  }

  string forward(int steps) {
    while (!future.empty() && steps-- > 0)
      history.push(future.top()), future.pop();
    return history.top();
  }

 private:
  stack<string> history;
  stack<string> future;
};

class BrowserHistory {
  public BrowserHistory(String homepage) {
    visit(homepage);
  }

  public void visit(String url) {
    history.push(url);
    future = new ArrayDeque<>();
  }

  public String back(int steps) {
    while (history.size() > 1 && steps-- > 0)
      future.push(history.pop());
    return history.peek();
  }

  public String forward(int steps) {
    while (!future.isEmpty() && steps-- > 0)
      history.push(future.pop());
    return history.peek();
  }

  private Deque<String> history = new ArrayDeque<>();
  private Deque<String> future;
}

class BrowserHistory:
  def __init__(self, homepage: str):
    self.history = []
    self.visit(homepage)

  def visit(self, url: str) -> None:
    self.history.append(url)
    self.future = []

  def back(self, steps: int) -> str:
    while len(self.history) > 1 and steps > 0:
      self.future.append(self.history.pop())
      steps -= 1
    return self.history[-1]

  def forward(self, steps: int) -> str:
    while self.future and steps > 0:
      self.history.append(self.future.pop())
      steps -= 1
    return self.history[-1]

Approach 3: Doubly-Linked List

• Time:
  • Constructor
  • visit(url: str): $O(1)$
  • back(steps: int): $O(\texttt{steps})$
  • forward(steps: int): $O(\texttt{steps})$
• Space: $O(n)$

C++JavaPython

struct Node {
  Node(const string& url) : url(url) {}
  Node* prev = nullptr;
  Node* next = nullptr;
  const string url;
};

class BrowserHistory {
 public:
  BrowserHistory(string homepage) {
    curr = new Node(homepage);
  }

  void visit(string url) {
    curr->next = new Node(url);
    curr->next->prev = curr;
    curr = curr->next;
  }

  string back(int steps) {
    while (curr->prev && steps-- > 0)
      curr = curr->prev;
    return curr->url;
  }

  string forward(int steps) {
    while (curr->next && steps-- > 0)
      curr = curr->next;
    return curr->url;
  }

 private:
  Node* curr = nullptr;
};

class Node {
  public Node prev;
  public Node next;
  public final String url;
  public Node(final String url) {
    this.url = url;
  }
}

class BrowserHistory {
  public BrowserHistory(String homepage) {
    curr = new Node(homepage);
  }

  public void visit(String url) {
    curr.next = new Node(url);
    curr.next.prev = curr;
    curr = curr.next;
  }

  public String back(int steps) {
    while (curr.prev != null && steps-- > 0)
      curr = curr.prev;
    return curr.url;
  }

  public String forward(int steps) {
    while (curr.next != null && steps-- > 0)
      curr = curr.next;
    return curr.url;
  }

  private Node curr;
}

class Node:
  def __init__(self, url: str):
    self.prev = None
    self.next = None
    self.url = url


class BrowserHistory:
  def __init__(self, homepage: str):
    self.curr = Node(homepage)

  def visit(self, url: str) -> None:
    self.curr.next = Node(url)
    self.curr.next.prev = self.curr
    self.curr = self.curr.next

  def back(self, steps: int) -> str:
    while self.curr.prev and steps > 0:
      self.curr = self.curr.prev
      steps -= 1
    return self.curr.url

  def forward(self, steps: int) -> str:
    while self.curr.next and steps > 0:
      self.curr = self.curr.next
      steps -= 1
    return self.curr.url