PROBLEM LINK
Author: Dipen Ved
Editorialist: Akshay Padte
DIFFICULTY
Easy
PRE-REQUISITES
Sets
PROBLEM:
You’re given a string consisting only of uppercase letters U, D, L, R which represent the commands to move either Up, Down, Left, Right respectively. Two volunteers Krushi and Mansi start from the same point in an infinite grid (crowd) and follow alternate commands from that string. You must find the number of unique points overall that they pass over.
QUICK EXPLANATION
We can solve this problem very easily if we maintain a set of points that are encountered. We initialize the positions of both the volunteers to (0, 0) and then each time one of them executes a command,we increment / decrement the coordinates of that volunteer accordingly and add it to the set. The final length of the set is the required answer.
EXPLANATION
We keep a track of both Krushi’s and Mansi’s position. We first initialize both of them arbitrarily to (0, 0) . Now they start executing alternate commands from the given string. Note that it does not matter who goes first. We must keep a track of only unique coordinates that turn up. For this we can maintain an unordered set. We loop through the list twice, first starting with index 0 and then with index 1, each time moving with increments of two to simulate alternate execution of commands. We increment / decrement the coordinates of the positions of the volunteers accordingly. Then we add the position obtained to the set. The length of the set at the end is the required answer.
For an unordered set, the insert operation takes O(1) time. Running this N times, we get a total time complexity of O(N).
If we use an ordered set instead, the insert operation takes O(logN) time, giving us a total complexity of O(NlogN), which would still pass for the given constraints.
Editorialist Solution: Link