5 Best Ways to Find Minimum Possible Difference of Indices of Adjacent Elements in Python

Rate this post

πŸ’‘ Problem Formulation: We need to determine the smallest distance between indices of adjacent elements in a Python list. If we are given an input list like [5, 3, 2, 3, 3, 5], we aim to find the minimum index difference for adjacent elements with the same value, which in this case would be the difference between the indices of the value 3, with an expected output of 1.

Method 1: Brute Force Approach

This method involves checking each pair of elements in the list. It iterates through the list, maintaining a record of the smallest difference encountered so far. The time complexity is O(n^2), which might not be efficient for large lists.

Here’s an example:

def find_min_diff_bruteforce(lst):
      min_diff = len(lst)
      for i in range(len(lst)):
          for j in range(i+1, len(lst)):
              if lst[i] == lst[j]:
                  min_diff = min(min_diff, j-i)
      return min_diff if min_diff != len(lst) else -1

  print(find_min_diff_bruteforce([5, 3, 2, 3, 3, 5]))

Output: 1

This code iterates through each element, comparing it with all subsequent elements to find pairs with equal values and then calculates their index difference, updating min_diff when a smaller difference is found.

Method 2: Hash Map to Store Indices

Using a hash map, we can store the last index at which each element occurred. As we iterate over the array, we calculate the index difference between the current and last occurrence for each element, which yields a time complexity of O(n).

Here’s an example:

def find_min_diff_hashmap(lst):
      index_map = {}
      min_diff = float('inf')
      for idx, val in enumerate(lst):
          if val in index_map:
              min_diff = min(min_diff, idx - index_map[val])
          index_map[val] = idx
      return min_diff if min_diff != float('inf') else -1

  print(find_min_diff_hashmap([5, 3, 2, 3, 3, 5]))

Output: 1

The code snippet creates a hash map to track the last index of each element. When the same element is encountered, it calculates the difference with the saved index and updates the minimum difference accordingly.

Method 3: Linear Scan with Early Exit

Similar to the hash map approach, this method employs a linear scan over the input list while keeping track of the last occurrence of each element. However, if the minimum possible difference (which is 1) is found, the method returns early, potentially saving time if such a pair is found early in large lists.

Here’s an example:

def find_min_diff_early_exit(lst):
      index_map = {}
      for idx, val in enumerate(lst):
          if val in index_map and (idx - index_map[val]) == 1:
              return 1
          index_map[val] = idx
      return min(index_map.values()) if index_map.values() else -1

  print(find_min_diff_early_exit([5, 3, 2, 3, 3, 5]))

Output: 1

This method is a small optimization on top of the hash map approach by incorporating an early exit strategy. The moment the minimum difference is detected, the function returns without scanning the rest of the list.

Method 4: Sort and Compare Consecutive Elements

By first sorting the elements along with their original indices, we can then compare only consecutive elements for equality, which reduces the problem to finding the minimum difference between consecutive elements’ indices. The total complexity becomes O(n log n) due to the sort operation.

Here’s an example:

def find_min_diff_sort(lst):
      enumerated_list = sorted((val, idx) for idx, val in enumerate(lst))
      min_diff = float('inf')
      for i in range(1, len(enumerated_list)):
          if enumerated_list[i-1][0] == enumerated_list[i][0]:
              min_diff = min(min_diff, enumerated_list[i][1] - enumerated_list[i-1][1])
      return min_diff if min_diff != float('inf') else -1

  print(find_min_diff_sort([5, 3, 2, 3, 3, 5]))

Output: 1

This code sorts the list by element values, then compares adjacent elements in the sorted list. If the values match, it computes the index difference and updates the minimum difference found.

Bonus One-Liner Method 5: Using a List Comprehension and min() Function

This succinct approach uses a list comprehension to create a list of index differences for all pairs of equal adjacent elements, and then returns the smallest difference using the min() function.

Here’s an example:

def find_min_diff_oneliner(lst):
      return min((j-i for i, j in zip(range(len(lst)), range(1, len(lst))) if lst[i] == lst[j]), default=-1)

  print(find_min_diff_oneliner([5, 3, 2, 3, 3, 5]))

Output: 1

This compact one-liner uses Python’s min() function to directly compute the minimum index difference by checking all consecutive elements for equality inside a list comprehension.

Summary/Discussion

  • Method 1: Brute Force Approach. Simple to implement. Not suitable for large lists due to O(n^2) complexity.
  • Method 2: Hash Map to Store Indices. More scalable with O(n) complexity. Requires extra space for the hash map.
  • Method 3: Linear Scan with Early Exit. Time-efficient if pairs found early. Same complexity as Method 2, might still require full scan.
  • Method 4: Sort and Compare Consecutive Elements. Time complexity of O(n log n) due to sorting. More efficient than brute force but slower than hash methods for large lists.
  • Method 5: Bonus One-Liner Method. Elegant and concise. May be less readable for those not familiar with list comprehensions and generator expressions.