Sometimes, while working with lists, we can have a problem in which we need to find maximum distance between reoccurring elements. This kind of problem can have application in competitive programming and web development domain. Let’s discuss certain way in which this task can be performed.
Method 1: Using loop + max() + defaultdict() + enumerate()
The combination of above functions can be used to perform this particular task. In this, we first initialize the temp dict with list using defaultdict(). The iteration is using enumerate() and max() performs the maximum distance between all similar numbers in list.
Python3
# Python3 code to demonstrate # Maximum distance between elements# using max() + enumerate() + loop + defaultdict()from collections import defaultdict# Initializing listtest_list = [4, 5, 6, 4, 6, 3]# printing original listprint("The original list is : " + str(test_list))# Maximum distance between elements# using max() + enumerate() + loop + defaultdict()temp = defaultdict(list)for idx, ele in enumerate(test_list): temp[ele].append(idx)res = max(temp[ele][-1]-temp[ele][0] for ele in temp)# printing result print ("Maximum distance between same element is : " + str(res)) |
The original list is : [4, 5, 6, 4, 6, 3] Maximum distance between same element is : 3
Method 2: Using recursion + dictionary+ enumerte
The find_multiples function takes two lists as input, test_list, and div_list. It iterates over each element of test_list and checks whether it is divisible by any element in div_list. If it is, the element is added to the result list, and the loop moves on to the next element in test_list. If not, the loop moves on to the next element in div_list. Finally, the result list is returned.
Python3
# define the function max_distancedef max_distance(lst): # initialize the dictionary to store the last occurrence of each element last_occurrence = {} # initialize the maximum distance between the same element to 0 max_distance = 0 # loop through the list for i, num in enumerate(lst): # check if the element is already present in the dictionary if num not in last_occurrence: # if not, add the element to the dictionary with its index as the value last_occurrence[num] = i else: # if yes, calculate the distance between the current index and the last occurrence of the element distance = i - last_occurrence[num] # if the distance is greater than the maximum distance found so far, update the maximum distance if distance > max_distance: max_distance = distance # update the last occurrence of the element to the current index last_occurrence[num] = i # return the maximum distance between the same element return max_distance# sample input listlst = [4, 5, 6, 4, 6, 3]# call the max_distance function on the input listresult = max_distance(lst)# print the resultprint(f"Maximum distance between same element is : {result}") |
Maximum distance between same element is : 3
Time complexity: O(n)
Auxiliary Space: O(n)
Method 3: Using a heap to store the indices of each element :
Algorithm:
- Create a min heap to keep track of the minimum index of each element encountered so far.
- For each element in the list, add a tuple (element, index) to the min heap.
- Pop the minimum element (i.e., the element with the smallest index) from the heap and set it as the current element.
- For each subsequent element in the heap, if it is the same as the current element, calculate the distance between them.
- It’s an index and the minimum index of the current element, and updates the maximum distance if necessary. If it is a
- different element, set it as the new current element and its index as the new minimum index.
- Return the maximum distance found.
Python3
import heapqdef max_distance(lst): max_dist = 0 index_heap = [] for i in range(len(lst)): heapq.heappush(index_heap, (lst[i], i)) curr_elem, curr_min_idx = heapq.heappop(index_heap) while index_heap: next_elem, next_idx = heapq.heappop(index_heap) if next_elem == curr_elem: dist = next_idx - curr_min_idx if dist > max_dist: max_dist = dist else: curr_elem, curr_min_idx = next_elem, next_idx return max_dist# Example usage:lst = [4, 5, 6, 4, 6, 3]# printing original listprint("The original list is : " + str(lst))max_dist = max_distance(lst)print("The maximum distance between same elements is:", max_dist)#This code is contributed by Jyothi pinjala |
The original list is : [4, 5, 6, 4, 6, 3] The maximum distance between same elements is: 3
Time complexity: O(n log n)
Adding each element to the heap takes O(log n) time, and there are n elements in the list, so this step takes O(n log n) time.
Popping the minimum element from the heap takes O(log n) time, and this is done n times, so this step takes O(n log n) time as well.
The loop that checks each subsequent element and updates the maximum distance takes O(1) time per iteration, and is done at most n times, so this step takes O(n) time.
Overall, the time complexity of the algorithm is dominated by the heap operations, which take O(n log n) time.
Auxiliary Space: O(n)
The heap stores a tuple (element, index) for each element in the list, so the space complexity is O(n).
Method 4 : using a set
We define a function max_distance that takes a list lst as input and returns the maximum distance between same elements in the list.
We create a set unique_elems that contains all the unique elements in the list lst.
We initialize a variable max_dist to 0, which will be used to store the maximum distance between same elements.
We iterate over each element elem in the set unique_elems.
We create a list indices that contains the indices of all occurrences of the element elem in the list lst.
We calculate the distance between the first and last occurrence of the element elem by taking the difference between the maximum and minimum indices in the list indices. We store this distance in a variable dist.
If the distance dist is greater than the current maximum distance max_dist, we update the value of max_dist to dist.
After iterating over all unique elements, we return the value of max_dist.
Python3
def max_distance(lst): unique_elems = set(lst) max_dist = 0 for elem in unique_elems: indices = [i for i, x in enumerate(lst) if x == elem] dist = max(indices) - min(indices) if dist > max_dist: max_dist = dist return max_distlst = [4, 5, 6, 4, 6, 3]max_dist = max_distance(lst)print("The maximum distance between same elements is:", max_dist) |
The maximum distance between same elements is: 3
The time complexity of this approach is O(n^2) in the worst case if all elements are unique.
The auxiliary space required is O(n) as we need to store the indices of all occurrences of each unique element.
