Day 77 || O(1) time for Visit, Back and Forward || Easiest Beginner Friendly Sol
NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.\n\n# Intuitio
**NOTE - PLEASE READ INTUITION AND APPROACH FIRST THEN SEE THE CODE. YOU WILL DEFINITELY UNDERSTAND THE CODE LINE BY LINE AFTER SEEING THE APPROACH.**\n\n# Intuition of this Problem :\nThis code implements the BrowserHistory class which allows the user to visit URLs and navigate between them using back and forward methods. The class stores the history of visited URLs in a vector called URLsHistory.\n\nWhen a new URL is visited, it is added to the URLsHistory vector, and the current URL index currURL is updated to point to the latest URL. If the user navigates backward or forward, the currURL is updated accordingly to the desired index.\n\nThe back and forward methods simply update the currURL index by a certain number of steps, making sure not to exceed the boundaries of the URLsHistory vector. Then they return the URL at the new currURL index.\n\n**By avoiding the use of the erase function, the code achieves a time complexity of O(1) for the visit, forward methods and back method. This is an improvement over the O(n) time complexity achieved when using the erase function.**\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach for this Problem :\n1. Create a class called BrowserHistory.\n2. Define a vector of strings named URLsHistory, and two integers currURL and lastURL.\n3. Define the constructor of the class, which takes a string named homepage as an argument.\n4. Inside the constructor, push homepage string to the URLsHistory vector, set currURL and lastURL to 0.\n5. Define the visit function which takes a string named url as an argument.\n6. Inside the visit function, increment currURL by 1.\n7. If the size of URLsHistory is greater than currURL, set URLsHistory[currURL] to url.\n8. If the size of URLsHistory is not greater than currURL, push url to the end of URLsHistory.\n9. Set lastURL to currURL.\n10. Define the back function which takes an integer named steps as an argument.\n11. Inside the back function, set currURL to the maximum value of 0 and currURL - steps.\n12. Return URLsHistory[currURL].\n13. Define the forward function which takes an integer named steps as an argument.\n14. Inside the forward function, set currURL to the minimum value of lastURL and currURL + steps.\n15. Return URLsHistory[currURL].\n16. The main program instantiates the BrowserHistory class, calls its visit, back, and forward functions as required.\n<!-- Describe your approach to solving the problem. -->\n\n# Code :\n```C++ []\n//By avoiding the use of the erase function, the code achieves a time\n//complexity of O(1) for the visit, forward methods and back method.\n//This is an improvement over the O(n) time complexity achieved when\n//using the erase function.\n\nclass BrowserHistory {\npublic:\n    vector<string> URLsHistory;\n    int currURL, lastURL;\n    \n    BrowserHistory(string homepage) {\n        URLsHistory.push_back(homepage);\n        currURL = 0;\n        lastURL = 0;\n    }\n    \n    void visit(string url) {\n        currURL++;\n        if (URLsHistory.size() > currURL) {\n          // We have enough space in our array to overwrite an old \'url\' entry with new one. \n            URLsHistory[currURL] = url;\n        }\n        else {\n            // We have to insert a new \'url\' entry at the end.\n            URLsHistory.push_back(url);\n        }\n        // Now this will be out last url \n        lastURL = currURL;\n    }\n    \n    string back(int steps) {\n      // move currURL to the leftmost place\n        currURL = max(0, currURL - steps);\n        return URLsHistory[currURL];\n    }\n    \n    string forward(int steps) {\n      // move currURL to the rightmost place\n        currURL = min(lastURL, currURL + steps);\n        return URLsHistory[currURL];\n    }\n};\n\n/**\n * Your BrowserHistory object will be instantiated and called as such:\n * BrowserHistory* obj = new BrowserHistory(homepage);\n * obj->visit(url);\n * string param_2 = obj->back(steps);\n * string param_3 = obj->forward(steps);\n */\n```\n```C++ []\n// using erase function which takes O(n) time for visit which is costly.\nclass BrowserHistory {\npublic:\n    vector<string> history;\n    int currIndex;\n    BrowserHistory(string homepage) {\n        history.push_back(homepage);\n        currIndex = 0;\n    }\n    \n    void visit(string url) {\n        // clear forward history\n        history.erase(history.begin() + currIndex + 1, history.end());\n        // add new url to history\n        history.push_back(url);\n        currIndex++;\n    }\n    \n    string back(int steps) {\n        currIndex = max(0, currIndex - steps);\n        return history[currIndex];\n    }\n    \n    string forward(int steps) {\n        currIndex = min((int)history.size() - 1, currIndex + steps);\n        return history[currIndex];\n    }\n};\n\n```\n```Java []\nclass BrowserHistory {\n    private List<String> URLsHistory;\n    private int currURL;\n    private int lastURL;\n    \n    public BrowserHistory(String homepage) {\n        URLsHistory = new ArrayList<>();\n        URLsHistory.add(homepage);\n        currURL = 0;\n        lastURL = 0;\n    }\n    \n    public void visit(String url) {\n        currURL++;\n        if (URLsHistory.size() > currURL) {\n            URLsHistory.set(currURL, url);\n        }\n        else {\n            URLsHistory.add(url);\n        }\n        lastURL = currURL;\n    }\n    \n    public String back(int steps) {\n        currURL = Math.max(0, currURL - steps);\n        return URLsHistory.get(currURL);\n    }\n    \n    public String forward(int steps) {\n        currURL = Math.min(lastURL, currURL + steps);\n        return URLsHistory.get(currURL);\n    }\n}\n```\n```Python []\nclass BrowserHistory:\n    def __init__(self, homepage: str):\n        self.URLsHistory = [homepage]\n        self.currURL = 0\n        self.lastURL = 0\n    \n    def visit(self, url: str) -> None:\n        self.currURL += 1\n        if len(self.URLsHistory) > self.currURL:\n            self.URLsHistory[self.currURL] = url\n        else:\n            self.URLsHistory.append(url)\n        self.lastURL = self.currURL\n    \n    def back(self, steps: int) -> str:\n        self.currURL = max(0, self.currURL - steps)\n        return self.URLsHistory[self.currURL]\n    \n    def forward(self, steps: int) -> str:\n        self.currURL = min(self.lastURL, self.currURL + steps)\n        return self.URLsHistory[self.currURL]\n```\n\n# Time Complexity and Space Complexity:\n- Time complexity : \n**Time complexity of O(1) for the visit, forward methods and back method.**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity : \n**Overall space complexity is O(n).**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Array', 'Design', 'C++', 'Java', 'Python3']