O(m) solution explained clearly | C++
\nPls upvote(\uD83E\uDD7A\uD83D\uDE48\uD83D\uDE0C). If you found it useful,\nplease comment for any doubts, will be happy to reply\n\nI didnt come up with the s
\n**Pls upvote(\uD83E\uDD7A\uD83D\uDE48\uD83D\uDE0C). If you found it useful,\nplease comment for any doubts, will be happy to reply**\n\nI didnt come up with the solution, i checked out the solution of @hxu10 and first i was perplexed, confused and honestly frustrated at myself for not understanding the solution, after putting 1-2 hours and lots of chai :0 in to reading his code, i got what he was doing and i was amazed. Here the approach is explained clearly in the comments. Take a look and feel free to ask questions :) \n\nSo basically the core ideas is, we can move the grid anywhere in to the co-ordinate system and do the problem, we need to only check if the bounds(right,left,up,down) are violated, this core idea helps us to do the journey in reverse and do it in O(m). to do this we store the indexes of our journey with respective co-ordinates in reverse and at each step we check if by taking the current direction(L or R or U or D), did any of our previous co-ordinates in the reverse path violate the bounds we set.\n\nWe do the journey in reverse because that way we dont need to recalculate for every new index which we do while we do the journey straight(See brute force solutions) if we do L<-U<-R<-D , then by the time we reach L, we already took all the directions in the journey, \n \n so if say in L<-U<-R<-D path Lcol - leftviolation == Rcol(means Lcol-Rcol = leftviolation), then LU is the only valid \n directions, because the direction R crossed the grid(the bounds we set) and it doesnt matter where D    \ntakes us as R crossed the grid already while we are doing L->U->R->D (but we do this in reverse)\n\n```\nclass Solution {\npublic:\n\n    vector<int> executeInstructions(int n, vector<int>& startPos, string path) {\n        \n        unordered_map<char,pair<int,int>> dir = {{\'L\',{0,-1}},{\'R\',{0,1}},{\'U\',{-1,0}},{\'D\',{1,0}}};\n        int m = path.length();\n         // If ever these limits below are broken that means the robot is out of the grid\n        // only these bounds matter as virtually you can move the n x n grid throughout the coordinate system\n\t\t// and place it anywhere and do the problem.\n        //basically if current_row_path_index - anypreviousrow_path_index >= up_violation\n        //That means from the current_row_path_index to prev_row_path_index-1, where prev_row_path_index means\n\t\t//index in the path where this  bound is exactly violated is the answer( current_row_path_index - anypreviousrow_path_index == up_violation)\n\t\t//hence we need to store the indexes of our journey in the map.\n\t\t//Here only one violation is explained(up_violation), we have to take minimum of all violations.\n        int up_violation = startPos[0]+1; // U can only take startPos[1] net Up directions, startPos[1]+1 net Up\'s means you are out of the grid.\n        int btm_violation = n - startPos[0];\n        int lft_violation = startPos[1]+1;\n        int rt_violation = n - startPos[1];\n        //can be any co-ordinate as it was said before only bounds matter, try chaninging the values, u should get an OC :),\n\t\t//make sure you change the initializations in map down below also\n        //These are initializations only, but these keep track of our co-ordinates in the path\n\t\t //remember these are our final coordinates after doing any journey i.e., suppose path = "LUURRD",\n\t\t//these initial values(3,2) are our final coordinates for every path we take, like\n        //D, RD, RRD, URRD, etc....as we are doing this in reverse\n        int curr_row = 3, curr_col = 2;\n        //maps to store the position of directions for each co-ordinate in our path.\n        unordered_map<int,int> row_pathIdx;\n        unordered_map<int,int> col_pathIdx;\n        \n       \n        row_pathIdx[3] = m;\n        col_pathIdx[2] = m;\n        vector<int> ans;\n        for(int i = m-1; i>= 0; i--){\n            //here - sign helps us invert our directions, i.e, D become U, L becomes R and vice verse, because we are doing reverse(i.e, back tracking)\n            curr_row-=dir[path[i]].first;\n            curr_col-=dir[path[i]].second;\n            int min_valid_path_length = m - i;\n            //Checking for violations of bounds;\n\t\t\t//We are not using else if\'s bcz any bound can be violated and we get the minimum path length out of all bounds violated\n            if(row_pathIdx.count(curr_row-up_violation)){\n                // This part sets the valid length to 2 if in LURD, the current one is L and violation is found at R\n                min_valid_path_length = min(valid_path_length , row_pathIdx[curr_row-up_violation] - i - 1)\n            }\n            if(row_pathIdx.count(curr_row+btm_violation)){\n                min_valid_path_length = min(valid_path_length , row_pathIdx[curr_row+btm_violation] - i - 1);\n                \n            }\n            if(col_pathIdx.count(curr_col-lft_violation)){\n                min_valid_path_length = min(valid_path_length , col_pathIdx[curr_col-lft_violation] - i - 1);\n                \n            }\n            if(col_pathIdx.count(curr_col+rt_violation)){\n                min_valid_path_length = min(valid_path_length , col_pathIdx[curr_col+rt_violation] - i - 1);\n            }\n            \n            ans.push_back(min_valid_path_length);\n            //mapping path_idx to co-ordinates\n            row_pathIdx[curr_row] = i;\n            col_pathIdx[curr_col] = i;\n        }\n        reverse(ans.begin(),ans.end());\n        return ans;\n        \n    }\n};\n```
['C', 'C++']