Problem statement

https://binarysearch.com/problems/Minimum-Adjacent-Elements/

Solution

For each value keep positions wher ewe have it. Then we can have two options:

  1. Values are the same, then we need to check all pairs of adjacent places.
  2. Values are adjacent in sorted array, then we need to find the shortest distance, using two pointers approach.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        places = defaultdict(list)
        for i, x in enumerate(nums):
            places[x] += [i]
            
        vals = sorted(set(nums))
        ans = float("inf")
        for x in vals:
            for i1, i2 in zip(places[x], places[x][1:]):
                ans = min(ans, i2 - i1)

        for x, y in zip(vals, vals[1:]):
            p1, p2 = places[x], places[y]
            t = sorted([(i1, 1) for i1 in p1] + [(i2, 2) for i2 in p2])
            ans = min(ans, min(j[0]-i[0] for i,j in zip(t, t[1:]) if j[1] + i[1] == 3))

        return ans