Problem Statement in English

You’re given an array nums consisting of only 1s and 2s. You have to find the minimum absolute difference between the indices of any two values in the array, where one value is 1 and the other value is 2. If there are no such pairs, return -1.

Approach

We can maintain two separate lists to store the indices of 1s and 2s in the array. Then, we can iterate through both lists and calculate the absolute difference between the indices of 1s and 2s, keeping track of the minimum difference found.

And we’re done!

Solution in Python


class Solution:
    def minAbsoluteDifference(self, nums: list[int]) -> int:
        ones = []
        twos = []

        for i in range(len(nums)):
            if nums[i] == 1:
                ones.append(i)
            elif nums[i] == 2:
                twos.append(i)

        res = inf

        for i in range(len(ones)):
            for j in range(len(twos)):
                res = min(res, abs(ones[i] - twos[j]))

        if res == inf:
            return -1

        return res

Complexity

  • Time: $O(m \times n)$
    Where m is the number of 1s and n is the number of 2s in the array. In the worst case, we can have all 1s and all 2s, which will lead to $O(n^2)$ time complexity.

  • Space: $O(m + n)$
    Where m is the number of 1s and n is the number of 2s in the array. We store the indices of 1s and 2s in separate lists.

And we are done.