Given two arrays arr[ ] and peanlty[ ], each of size n.
All elements in arr[ ] are in the range of 1 to n. You have to traverse arr[ ] from start to end while following the given conditions.
If element has never occured before, it takes 1 second to move a step ahead.
If element has occured before, it will take penalty[arr[i]] seconds to move a step. Here i is the index of current element with 1 based indexing.
Find the total time taken to traverse through the array.
Example 1:
Input:
n = 4
arr[ ] = {1, 2, 3, 3}
penalty[ ] = {1, 2, 3, 4}
Output: 5
Explanation:
For i = 1, traversal time = 0 second since this is the start point.  
For i = 2, traversal time = 1 second 
For i = 3, traversal time = 1 second 
For i = 4, traversal time = penalty[arr[4]]  = penalty[3] = 3
Total = 0+1+1+3 = 5 
Example 2:
Input:
n = 8
arr = {6, 6, 1, 8, 1, 1, 3, 1}
time ={8, 4, 1, 5, 2, 8, 9, 3}
Output:
35
Explanation:
Your Task:
You don't need to read input or print anything. Your task is to complete the function totalTime() which takes three input parameters n, arr[ ], penalty[ ] and returns the total time taken to traverse through the array. 
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(n)
Constraints:
1 <= n <= 10^5
1 <= arr[i] <= n
1 <= time[i] <= 10^5

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: from typing import List





class Solution:

    def totalTime(self, n : int, arr : List[int], penalty : List[int]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		time_taken = 0
		seen = {arr[0]}
		for i in range(1, n):
			if arr[i] not in seen:
				seen.add(arr[i])
				time_taken += 1
			else:
				time_taken += penalty[arr[i] - 1]
		return time_taken


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		d = dict()
		s = 0
		for i in arr:
			if i in d.keys():
				s += penalty[i - 1]
			elif s == 0:
				s = 1
				d[i] = True
				continue
			else:
				s += 1
				d[i] = True
		return s - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		d = set()
		res = 0
		d.add(arr[0])
		for i in range(1, len(arr)):
			if arr[i] in d:
				res += penalty[arr[i] - 1]
			else:
				res += 1
				d.add(arr[i])
		return res


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		ans = -1
		vis = set()
		for num in arr:
			if num in vis:
				ans += penalty[num - 1]
			else:
				ans += 1
			vis.add(num)
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		ans = 0
		b = {}
		i = 0
		while i < n:
			if arr[i] in b:
				ans += penalty[arr[i] - 1]
				i += 1
			else:
				b[arr[i]] = 1
				i += 1
				if i == 1:
					pass
				else:
					ans += 1
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		s = set()
		ans = 0
		for i in range(n):
			if arr[i] not in s:
				s.add(arr[i])
				ans += 1
			else:
				ans += penalty[arr[i] - 1]
		return ans - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		seen = set()
		seen.add(arr[0])
		time = 0
		for i in range(1, len(arr)):
			num = arr[i]
			if num not in seen:
				time = time + 1
				seen.add(num)
			else:
				time = time + penalty[arr[i] - 1]
		return time


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		(result, m) = (0, {})
		for element in arr:
			if element not in m:
				result += 1
				m[element] = True
			else:
				result += penalty[element - 1]
		return result - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		(res, mp) = (0, {})
		for ele in arr:
			if ele not in mp:
				res += 1
				mp[ele] = True
			else:
				res += penalty[ele - 1]
		return res - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		sum = 0
		for i in arr:
			if penalty[i - 1] > 0:
				sum += 1
				penalty[i - 1] *= -1
			else:
				sum += abs(penalty[i - 1])
		return sum - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		dict1 = {}
		sum1 = 0
		for i in range(n):
			if i == 0:
				dict1[arr[i]] = penalty[arr[i] - 1]
			elif arr[i] in dict1:
				sum1 += penalty[arr[i] - 1]
			else:
				sum1 += 1
				dict1[arr[i]] = penalty[arr[i] - 1]
		return sum1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		dic = {}
		time = 0
		for i in range(n):
			if i == 0:
				dic[arr[i]] = True
			elif arr[i] in dic:
				time += penalty[arr[i] - 1]
			else:
				time += 1
				dic[arr[i]] = True
		return time


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		time = 0
		visited_values = set()
		for i in range(0, n):
			if arr[i] not in visited_values:
				time += 1
				visited_values.add(arr[i])
				continue
			time += penalty[arr[i] - 1]
		return time - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		total_time = 0
		prev_index = set()
		for i in range(n):
			curr_time = 1
			if arr[i] in prev_index:
				curr_time = penalty[arr[i] - 1]
			else:
				prev_index.add(arr[i])
			total_time += curr_time
		return total_time - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		d = {}
		time = 0
		for i in range(n):
			if d.get(arr[i], 0) > 0:
				time += penalty[arr[i] - 1]
				d[arr[i]] = d.get(arr[i], 0) + 1
			else:
				if i != 0:
					time += 1
				d[arr[i]] = d.get(arr[i], 0) + 1
		return time


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		mp = {}
		ans = -1
		for i in range(n):
			if arr[i] in mp:
				ans += penalty[arr[i] - 1]
			else:
				ans += 1
			mp[arr[i]] = True
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		a = {}
		t = 0
		a[arr[0]] = penalty[0]
		for i in range(1, n):
			if arr[i] not in a:
				t += 1
				a[arr[i]] = penalty[i]
			else:
				t += penalty[arr[i] - 1]
		return t


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] = dic.get(arr[i]) + penalty[arr[i] - 1]
			else:
				dic[arr[i]] = 1
		return sum(dic.values()) - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		c = 0
		s = 0
		d = dict()
		for i in range(n):
			if arr[i] in d.keys():
				s += penalty[arr[i] - 1]
			else:
				d[arr[i]] = 1
				s += c
			c = 1
		return s


from typing import List
import numpy as np

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		been_there = np.zeros(n + 1)
		suma = 0
		for i in range(n):
			if i + 1 == 1:
				suma += 0
			elif been_there[arr[i]] > 0:
				suma += penalty[arr[i] - 1]
			else:
				suma += 1
			been_there[arr[i]] += 1
		return suma


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		visited = {element: 0 for element in set(arr)}
		total_time = -1
		for element in arr:
			if visited[element]:
				total_time += penalty[element - 1]
			else:
				total_time += 1
				visited[element] += 1
		return total_time


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		ans = 0
		dic = dict()
		dic[arr[0]] = 1
		for i in range(1, n):
			if arr[i] in dic:
				ans += penalty[arr[i] - 1]
			else:
				ans += 1
				dic[arr[i]] = 1
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		num_seconds = 0
		seen = set([arr[0]])
		for i in range(1, n):
			cur_elem = arr[i]
			if cur_elem in seen:
				num_seconds += penalty[cur_elem - 1]
			else:
				num_seconds += 1
				seen.add(cur_elem)
		return num_seconds


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		ans = -1
		mp = {}
		for x in arr:
			if x in mp:
				mp[x] += 1
				ans += penalty[x - 1]
			else:
				mp[x] = 1
				ans += 1
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		d = {}
		count = -1
		for index in range(n):
			elem = arr[index]
			if elem in d:
				count += penalty[arr[index] - 1]
			else:
				d[elem] = 0
				count += 1
		return count


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], penalty: List[int]) -> int:
		ans = -1
		m1 = {}
		for i in range(len(arr)):
			if arr[i] in m1:
				m1[arr[i]] += 1
				ans += penalty[arr[i] - 1]
			else:
				m1[arr[i]] = 1
				ans += 1
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		s = 0
		arr.sort()
		for i in range(1, n):
			if arr[i] == arr[i - 1]:
				s += time[arr[i] - 1]
			else:
				s += 1
		return s


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		dic = {}
		t = -1
		for i in range(n):
			if arr[i] not in dic:
				dic[arr[i]] = 1
				t += 1
			else:
				t += time[arr[i] - 1]
		return t


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		l = set()
		t = 0
		h = 0
		l.add(arr[0])
		i = 1
		for i in range(1, n):
			if arr[i] in l:
				t = t + time[arr[i] - 1]
			else:
				t = t + 1
			l.add(arr[i])
		return t


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		d = {}
		for i in range(n):
			d[arr[i]] = d.get(arr[i], 0) + 1
		c = 0
		for (key, val) in d.items():
			if val > 1:
				tc = (val - 1) * time[key - 1]
				c += tc
			c += 1
		return c - 1


from typing import List
from collections import *

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		t = -1
		l = []
		d = Counter(arr)
		for (key, value) in d.items():
			t = t + 1
			if value > 1:
				ti = (value - 1) * time[key - 1]
				t = t + ti
		return t


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		(res, d) = (0, {})
		for i in arr:
			if i not in d:
				res += 1
				d[i] = True
			else:
				res += time[i - 1]
		return res - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		m = {}
		ma = -1
		c = 0
		for i in range(0, len(arr)):
			if arr[i] not in m:
				m[arr[i]] = 0
			m[arr[i]] += 1
		for i in range(0, len(arr)):
			if i == 0:
				if m[arr[i]] >= 2:
					c = 0
					m[arr[i]] = -1
				else:
					c = 0
			elif m[arr[i]] == -1:
				c = c + time[arr[i] - 1]
			elif m[arr[i]] >= 2:
				c += 1
				m[arr[i]] = -1
			else:
				c += 1
		return c


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		sum = 0
		tempList = {}
		for i in arr:
			if i in tempList:
				sum = sum + time[i - 1]
			else:
				sum += 1
				tempList[i] = True
		return sum - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		totalTime = -1
		usedElements = set()
		for i in range(len(arr)):
			if arr[i] in usedElements:
				totalTime += time[arr[i] - 1]
			else:
				usedElements.add(arr[i])
				totalTime = totalTime + 1
		return totalTime


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		x = 0
		m = 0
		l = [False] * (n + 1)
		for i in arr:
			if l[i] == False:
				l[i] = True
				x += 1
			else:
				x += time[i - 1]
		return x - 1


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		pre = {arr[0]: time[0]}
		t = 0
		for i in range(1, n):
			if arr[i] in pre:
				t += time[arr[i] - 1]
			else:
				pre[arr[i]] = 0
				t += 1
		return t


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		tot = 0
		k = [False] * (n + 1)
		if n == 1:
			return 0
		k[arr[0]] = True
		for i in range(1, n):
			if k[arr[i]] == True:
				tot += time[arr[i] - 1]
			else:
				tot += 1
				k[arr[i]] = True
		return tot


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		c = 0
		i = 1
		arr.sort()
		while i < n:
			if arr[i] == arr[i - 1]:
				c += time[arr[i] - 1]
			else:
				c += 1
			i += 1
		return c


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		used = set()
		cntr = 0
		for i in range(n):
			if i > 0:
				if arr[i] in used:
					cntr += time[arr[i] - 1]
				else:
					cntr += 1
			used.add(arr[i])
		return cntr


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		last = [False] * (max(arr) + 1)
		last[arr[0]] = True
		summ_time = 0
		for i in range(1, n):
			if last[arr[i]]:
				summ_time += time[arr[i] - 1]
			else:
				summ_time += 1
				last[arr[i]] = True
		return summ_time


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		ans = -1
		m = {}
		for i in arr:
			if i in m:
				m[i] += 1
				ans += time[i - 1]
			else:
				m[i] = 1
				ans += 1
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		c = {arr[0]: 1}
		out = 0
		for x in range(1, n):
			if arr[x] not in c:
				c[arr[x]] = 1
				out += 1
			else:
				out += time[arr[x] - 1]
		return out


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		total = 0
		l = set()
		l.add(arr[0])
		i = 1
		while i < len(arr):
			if arr[i] not in l:
				total = total + 1
				l.add(arr[i])
			else:
				total += time[arr[i] - 1]
			i += 1
		return total


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		c = 0
		di = {}
		for (i, j) in enumerate(time):
			di[i] = j
		lst = set()
		lst.add(arr[0])
		for i in range(1, len(arr)):
			if arr[i] not in lst:
				lst.add(arr[i])
				c += 1
			else:
				c += di[arr[i] - 1]
		return c


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		visited = set()
		for i in range(len(arr)):
			if i == 0:
				tot_time = 0
				visited.add(arr[0])
				continue
			if arr[i] in visited:
				tot_time += time[arr[i] - 1]
			else:
				visited.add(arr[i])
				tot_time += 1
		return tot_time


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		t = 0
		s = set()
		for x in arr:
			if x in s:
				t += time[x - 1]
			else:
				t += 1
				s.add(x)
		return t - 1


from typing import List

class Solution:

	def totalTime(self, n: int, a: List[int], time: List[int]) -> int:
		s = set()
		ans = -1
		for i in range(n):
			if a[i] in s:
				ans += time[a[i] - 1]
			else:
				ans += 1
			s.add(a[i])
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		a = -1
		b = {}
		for i in arr:
			if i in b:
				b[i] += 1
				a += time[i - 1]
			else:
				b[i] = 1
				a += 1
		return a


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		count = -1
		s = set()
		j = -1
		for i in range(n):
			if arr[i] not in s:
				s.add(arr[i])
				count = count + 1
			else:
				count = count + time[arr[i] - 1]
		return count


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		visited = dict.fromkeys(arr, 0)
		ans = 0
		visited[arr[0]] = 1
		for i in range(1, n):
			visited[arr[i]] += 1
			if visited[arr[i]] <= 1:
				ans += 1
			else:
				ans += time[arr[i] - 1]
		return ans


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		sum = 0
		d = {}
		for x in range(len(arr)):
			if arr[x] in d:
				sum = sum + time[arr[x] - 1]
			else:
				if x == 0:
					sum += 0
				else:
					sum += 1
				d[arr[x]] = 1
		return sum


from typing import List

class Solution:

	def totalTime(self, n: int, arr: List[int], time: List[int]) -> int:
		d = {}
		c = -1
		for i in arr:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		for (j, k) in d.items():
			if k >= 2:
				c += (k - 1) * time[j - 1] + 1
			else:
				c += 1
		return c