Given an array arr[] of size N that denotes the type of an element, and another time array time[] of size N where time[i] denotes the time interval between picking two elements of the i^{th} type. The task is to find the time taken to pick all the elements while traversing from left to right of the array.
Note: Moving between adjacent positions takes 1 unit of time and no extra time is required to pick an element. Also, the arrays follow 1based indexing.
Examples:
Input: N = 4, arr = {1, 2, 3, 3}, time = {1, 2, 3, 4}
Output: 5
Explanation: You start from index1, and pick arr[1] i.e. 1 in no time.
In 1 sec you move from index 1 to 2, and pick arr[2] i.e. 2, total time = 1.
In the next 1 sec you move from index 2 to 3 and pick arr[3] i.e. 3, total time = 2.
In the next 1 sec you move from index 3 to 4, and arr[4] is 3, which you have taken already at time 2, hence you need to wait for time[arr[i]] sec to again pick arr[i], time[arr[i]] = time[3] = 3.
Hence in 1 sec you moved from index 3 to 4, waited for the next 2 sec, and finally picked arr[4], total time = 5.Input: N = 4, arr[] = {1, 2, 3, 4}, time[] = {1, 2, 3, 4}
Output: 3
Explanation: All the array elements are different hence, you do not have to wait for any arr[i] before picking it, hence the total time will be 3, which is the time required to traverse the array.
Approach: This problem can be solved using a Greedy Algorithm and Hashing.
The idea is to iterate over the array and for every element update the timestamp. If the difference between the current time and the previous timestamp for the current element is less than the waiting time and add the waiting time to the current time.
Steps involved in the implementation of the above approach:
 Initialize current time as 1.
 Create a HashTable of size N to store the last timestamp of the N elements.
 At every iteration, increment the current time by 1.
 Check if the difference between the current time and the previous timestamp for the current element is less than the waiting time and add the waiting time in the current time.
 Update the timestamp of the element to the current time.
Below is the implementation of the above approach:
C++

Time Complexitya: O(N)
Auxiliary Space: O(1)
Related Articles: