Given a list and two elements, x and y find the nearest occurrence index of element x from element y.
Input : test_list = [2, 4, 5, 7, 8, 6, 3, 8, 7, 2, 0, 9, 4, 9, 4], x = 4, y = 6 Output : 1 Explanation : 4 is found at 1, 12 and 14th index, 6 is at 5th index, nearest is 1st index.
Input : test_list = [2, 4, 5, 7, 8, 6, 3, 8, 7, 2, 0, 9, 4, 9, 4], x = 7, y = 6 Output : 3 Explanation : 7 is found at 3rd and 8th index, 6 is at 5th index, nearest is 3rd index.
Method : Using list comprehension + loop + index()
In this, we find all indices of y using list comprehension, and then get index of x using index(), post that loop is used to get index difference, and the nearest index is returned as result.
Python3
# Python3 code to demonstrate working of# Nearest occurrence of x from y in List# Using list comprehension + loop + index()# Function to find index of nearest# occurrence between two elementsdef nearestOccurrenceIndex(test_list, x, y): # checking if both elements are present in list if x not in test_list or y not in test_list: return -1 # getting indices of x x_idx = [idx for idx in range(len(test_list)) if test_list[idx] == x] # getting y index y_idx = test_list.index(y) # getting min_dist index min_dist = 1000000 res = None for ele in x_idx: # checking for min ele, and updating index if abs(ele - y_idx) < min_dist: res = ele min_dist = abs(ele - y_idx) return res# initializing listinput_list = [2, 4, 5, 7, 8, 6, 3, 8, 4, 2, 0, 9, 4, 9, 4]# printing original listprint("The original list is : " + str(input_list))# initializing xx = 4# initializing yy = 6# printing resultprint("Minimum distance index: ", nearestOccurrenceIndex(input_list, x, y)) |
The original list is : [2, 4, 5, 7, 8, 6, 3, 8, 4, 2, 0, 9, 4, 9, 4] Minimum distance index: 8
Time Complexity: O(n), where n is the length of the list.
Auxiliary Space: O(1)
Method #2: Using linear search
Approach:
We use linear search to find the nearest occurrence of two elements x and y in the input list. The algorithm iterates through the list using a for loop and checks if the current element is equal to x or y. If the current element is equal to x or y, it checks if min_dist is None or if the distance between the current index and min_idx is less than min_dist. If the distance between the current index and min_idx is less than min_dist or min_dist is None, it updates min_dist and min_idx. At the end of the loop, if both x and y are found in the list, the algorithm returns min_dist. Otherwise, it returns -1 to indicate that one of the elements was not found in the list.
Algorithm:
- Initialize variables min_dist and min_idx to be None
- Iterate through the list using a for loop and check if the current element is equal to x or y.
- If the current element is equal to x or y, check if min_dist is None or if the distance between the current index and min_idx is less than min_dist.
- If the distance between the current index and min_idx is less than min_dist or min_dist is None, update min_dist and min_idx.
- If both x and y are found in the list, return min_dist. Otherwise, return -1.
- End.
Python3
def nearest_occurrence_linear(test_list, x, y): min_dist = None min_idx = None for i in range(len(test_list)): if test_list[i] == x or test_list[i] == y: if min_idx is not None and test_list[i] != test_list[min_idx]: dist = i - min_idx if min_dist is None or dist < min_dist: min_dist = dist min_idx = i if min_dist is not None: return min_dist else: return -1# Input lists test_list = [2, 4, 5, 7, 8, 6, 3, 8, 4, 2, 0, 9, 4, 9, 4]x = 4y = 6# Print the answerprint(nearest_occurrence_linear(test_list, x, y)) |
3
Time Complexity: O(n), where n is the length of the list
Space Complexity: O(1)
Method 3: Using 2 pointers
Steps:
- Initialize two pointers, one for x and one for y, to -1.
- Initialize a variable to store the minimum distance to a large value, such as float(‘inf’).
- Loop through the list, and for each element, update the index of the corresponding pointer if it matches x or y.
- If both pointers have been updated, calculate the distance between them and update the minimum distance variable if the distance is smaller than the current minimum.
- Return the index of the pointer that was updated last.
Example:
Python3
def nearestOccurrenceIndex(test_list, x, y): x_idx = -1 y_idx = -1 min_dist = float('inf') for i, val in enumerate(test_list): if val == x: x_idx = i elif val == y: y_idx = i if x_idx != -1 and y_idx != -1: dist = abs(x_idx - y_idx) if dist < min_dist: min_dist = dist if x_idx > y_idx: res = x_idx else: res = y_idx if min_dist == float('inf'): return -1 return res# Initializing listinput_list = [2, 4, 5, 7, 8, 6, 3, 8, 4, 2, 0, 9, 4, 9, 4]# Printing original listprint("The original list is : " + str(input_list))# Initializing xx = 4# Initializing yy = 6# Printing the resultprint("Minimum distance index: ", nearestOccurrenceIndex(input_list, x, y)) |
The original list is : [2, 4, 5, 7, 8, 6, 3, 8, 4, 2, 0, 9, 4, 9, 4] Minimum distance index: 8
Time complexity: O(n), since we need to loop through the entire list.
Auxiliary space: O(1), since we only need to store a few variables that don’t depend on the size of the input list.
