Problem

You are given an integer array nums consisting only of 0, 1, and 2.

A pair of indices (i, j) is called valid if nums[i] == 1 and nums[j] == 2.

Return the minimum absolute difference between i and j among all valid pairs. If no valid pair exists, return -1.

The absolute difference between indices i and j is defined as abs(i - j).

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 2

Examples:

• nums = [1, 0, 0, 2, 0, 1] → 2. The valid pairs are (0, 3) with difference 3 and (5, 3) with difference 2.
• nums = [1, 0, 1, 0] → -1. There are no 2s in the array, so no valid pair exists.

Walkthrough

Brute force

As ever we start with a brute force approach. It's not going to be the most efficient but working through it shows we understand the problem and often gives us ideas for how to optimise later.

The shape of the problem is: for every 1 find every 2 and track the smallest absolute difference between their indices. So the simplest thing we can do is two nested loops over the array and check every pair.

Note: abs just gives you the absolute value of a number, so abs(-3) and abs(3) both return 3. That's exactly what the problem is asking for so we can use it directly on idx1 - idx2 without worrying about which index is larger. And enumerate gives us both the index and the value as we iterate, which saves us from manually tracking a counter.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
  def minAbsoluteDifference(self, nums: list[int]) -> int:
    min_diff = 999
    for idx1, value1 in enumerate(nums):
      for idx2, value2 in enumerate(nums):
        # Check validity
        if value1 == 1 and value2 == 2:
          min_diff = min(min_diff, abs(idx1 - idx2))

    return min_diff if min_diff != 999 else -1

Submission result

The complexity here is O(n^2) because we have two nested loops over the array. Given the constraints (nums.length <= 100) this will run rapidly even though it's not optimal, so we'd get away with it on leet code, but we can do better.

Possible optimisations

Before jumping to a completely different approach let's see what we can shave off this brute force version, as the ideas we pick up will often inform the better solution.

The first thing to notice is that we iterate over the whole array twice and end up checking every pair in both orders. The pair (idx1, idx2) and the pair (idx2, idx1) give the same absolute difference, so we're doing twice the work. If we check both validity directions (nums[i]=1, nums[j]=2 and nums[j]=1, nums[i]=2) in the same comparison then we only need to look at each pair once, and we can start the inner loop one position past the outer one.

A handy thing to know here: enumerate takes an optional second argument which is the starting index it uses for the counter. So enumerate(nums[idx1+1:], idx1+1) walks the slice from idx1+1 onwards but keeps the indices aligned with the original array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
  def minAbsoluteDifference(self, nums: list[int]) -> int:
    min_diff = 999
    for idx1, value1 in enumerate(nums):
      # Start inner loop from next position.
      for idx2, value2 in enumerate(nums[idx1+1:], idx1+1):
        # Check validity
        if value1 == 1 and value2 == 2:
          min_diff = min(min_diff, abs(idx1 - idx2))
        # Check opposite way around too
        if value1 == 2 and value2 == 1:
          min_diff = min(min_diff, abs(idx1 - idx2))

    return min_diff if min_diff != 999 else -1

Submission result

This means on average we'll check n/2 elements in the inner loop, so we end up doing n * n / 2 comparisons. Much better in absolute terms, but it's still O(n^2) so for large inputs we'd still be in trouble.

We could push this further (rather than checking all values in the inner loop we only have to check as far as the current minimum) but that would still be O(n^2) in the worst case, so we need a different approach entirely.

The real insight we've picked up here is that the work is really lopsided. For each 2 in the array we don't actually care about every 1, we only care about the closest one. The brute force kept asking "is this pair valid, and if so how far apart are they?" but the question we actually need to answer is "for this 2, where is the nearest 1?" If we can answer that directly we never need to compare pairs at all.

Distance to nearest

So, we want a solution where we can find the valid elements in linear time. Can we store in an array the distance to the nearest 1 for each position? If we can do this then we can look up directly the distance for each value we check. After creating that array we iterate over nums and for every 2 we look up the distance to the nearest 1 in constant time.

To create this array we can do two passes through the data, once from the left and once from the right. The first pass we will fill in how many steps it takes to find a 1 from the left, and then the second we update the array counting steps from the right if it's smaller than from the left.

Spotting that for this particular solution you have to do this in two passes is, I think, the hardest part here. I suggest you write out by hand a few examples to understand why we need to do this. It's necessary because we're only checking one of the values.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
  def minAbsoluteDifference(self, nums: list[int]) -> int:
    dist = 999
    one_dist = []
    # Calculate the distance to the nearest 1 to the left.
    for value in nums:
      # Reset the distance if we have a target value
      if value == 1:
        # 0 because the 1 itself has distance 0 to the nearest 1.
        dist = 0
      one_dist.append(dist)
      # Increment dist for next iteration
      dist += 1
    # Second pass to calculate distance to the nearest 1 to the right.
    dist = 999
    for idx in range(len(nums)-1, -1, -1):
      # Reset the distance if we have a target value
      if nums[idx] == 1:
        dist = 0
      one_dist[idx] = min(one_dist[idx], dist)
      # Increment dist for next iteration
      dist += 1

    # Final pass finding minimum distance
    min_diff = 999
    for idx, value in enumerate(nums):
      if value == 2:
        min_diff = min(min_diff, one_dist[idx])

    return min_diff if min_diff != 999 else -1

Submission result

This requires 3 passes through the data so it is O(n) time complexity. It requires more memory than the brute force solution because we have to store the one_dist array, so it has O(n) memory complexity.

Optimal solution

The last solution only tracked the distance to the nearest 1, and needed two passes to do it because at any point we might find a closer 1 later in the array. But, can we use the same distance idea on both values at once and collapse the whole thing down to a single pass?

Obviously that's a leading question, yes we can. The key observation is that as we walk through the array left to right, the closest 1 to our current position is always the most recent 1 we've seen, same for 2. We don't need a whole array of distances, just the index of the last 1 and the last 2 we passed.

Until we've seen at least one 1 and one 2 there's nothing valid to compare against, so we start both last_1 and last_2 at -1. Then as we iterate: when we hit a 1, if we've already seen a 2, the gap between this 1 and the most recent 2 is a candidate for the minimum, so we compare it against min_diff. Either way we update last_1 to this index. The 2 branch is the mirror image.

For every element in nums we do at most two comparisons and one assignment, so it's a single linear pass through the data.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
  def minAbsoluteDifference(self, nums: list[int]) -> int:
    min_diff = 999
    # Start as unseen
    last_1 = -1
    last_2 = -1
    for idx, value in enumerate(nums):
      if value == 1:
        if last_2 != -1:
          min_diff = min(min_diff, idx - last_2)
        # Record the position of this 1
        last_1 = idx
      elif value == 2:
        if last_1 != -1:
          min_diff = min(min_diff, idx - last_1)
        # Record the position of this 2
        last_2 = idx

    return min_diff if min_diff != 999 else -1

Submission result

We're still at O(n) time complexity, the same as the previous solution on paper, but we've gone from three passes through the data down to one so the constant factor is a lot smaller. The bigger win is on memory: the previous version stored a full one_dist array which made it O(n) space, whereas here we only keep two integer indices and the running minimum, so we're down to O(1) extra memory.