NY Startup | Phone Screen | Numbers Between Duplicates
Anonymous User
216

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 output

Is 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?

Comments (1)