Just did an online test today for Microsoft and got this question

Optimize the following code:

def solution(arr):
	result = 0
	arr_len = len(arr)
	for i in range(arr_len):
		for j in range(arr_len):
			if arr[i] == arr[j]:
				result = max(result, abs(i-j))
	return result

Judging from the code, it looks to be just calculating the max distance between any 2 of the same elements and returning maximum distance found and it's being done in O(n^2) time.

I came up with a O(n) solution that uses a dictionary to keep track of the lowest index for a number and when I encounter that number again I subtract the indices to get the difference and then check if it's the new max distance. However, I was still getting a timeout in one of the test cases and was curious if this problem is similar to any other leetcode problems?

My solution that was timing out on one of the test cases:

def solution(arr):
	result = 0
	min_dict = {}
	for idx, num in enumerate(arr)):
		if num not in min_dict:
			min_dict[num] = index
		else:
			result = max(result, idx-min_dict[num])
	return result

Update: I passed the OTS and will be going to the virtual onsite