We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Solution with O(n) time complexity and O(n) space complexity,
#!/bin/python3importsys# Input array sizen=int(input().strip())# Input arrayA=[int(A_temp)forA_tempininput().strip().split(' ')]# Create empty dictionary to keep track of element value and its last know position in the arrayd={}# Initialize minimum difference variable as one more than the maximum value(n-1) we can achievemin_diff=n# Going through each element in the arrayforiinrange(n):# Try/Except statement to find record of the last known index for the element in the dictionary(for index difference calc), if unable to find the record then create the recordtry:# min_diff equals minimum value between (the element index i and the last known location of the same element) and (min_diff)min_diff=min(i-d[A[i]],min_diff)# Change the last known position of the elementd[A[i]]=i# Now if min_diff has value 1 then the code doesnt need to go further as its the minimum possible value for the answerifmin_diff==1:breakexcept:d[A[i]]=i# If min_diff is the same as initialized value meaning no element in input array is repeating then print -1 else the minimum difference valueifmin_diff==n:print(-1)else:print(min_diff)
Note: Dictionary lookup has time complexity of O(1), which is why it doesnt affect the time complexity of the rest of the code in this case.
Minimum Distances
You are viewing a single comment's thread. Return to all comments →
Solution with O(n) time complexity and O(n) space complexity,
Note: Dictionary lookup has time complexity of O(1), which is why it doesnt affect the time complexity of the rest of the code in this case.