Given an array of ints, output an array of the ints that fall between duplicate ints (in order they occur)
Example:
Given [2, 3, 4, 2, 3] return [3, 4, 4, 2]
Given [2, 3, 4, 2, 3, 2] return [3, 4, 4, 2, 3]
I used a hashmap to track the last seen position of a given num, and if I encountered a dup I just added the numbers in range(last_seen+1, cur_index) to the output arr, as follows:
def fallBetween(arr):
seen = {}
output = []
for i, num in enumerate(arr):
if num in seen:
last_ind = seen[num]
for j in range(last_ind + 1, i):
output.append(arr[j])
seen[num] = i
return outputIs there a better way to do this? With the two loops, I feel it approaches O(n^2) time complexity no? Is there a way to do this in linear time?