LeetCode Problem 3880

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

LeetCode 3880 - Minimum Absolute Difference Between Two Values

Problem Understanding

The problem gives us an integer array nums where every element is guaranteed to be one of three values: 0, 1, or 2.

A pair of indices (i, j) is considered valid when:

• nums[i] == 1
• nums[j] == 2

For every valid pair, we compute the absolute distance between the indices:

abs(i - j)

Our goal is to find the smallest such distance among all valid pairs.

If the array contains no valid pair, meaning there is no index containing 1 or no index containing 2, then we must return -1.

The input size is very small:

1 <= nums.length <= 100

Since the array length is at most 100, even a quadratic solution would be acceptable. However, it is still useful to think about how to solve the problem efficiently.

Several edge cases are important:

• The array may contain only 1s and no 2s.
• The array may contain only 2s and no 1s.
• The closest 1 and 2 may be adjacent.
• Multiple 1s and 2s may exist, requiring us to check many candidate pairs.
• The minimum distance could involve a 1 appearing before a 2 or after a 2, since the absolute difference ignores direction.

Approaches

Brute Force

The most direct solution is to examine every possible pair of indices.

For every index i containing a 1, we can iterate through every index j containing a 2. For each valid pair, compute abs(i - j) and keep track of the smallest value seen.

This approach is correct because it explicitly evaluates every valid pair and therefore cannot miss the optimal answer.

The downside is that we may compare every element with every other element, resulting in quadratic time complexity.

Key Insight

We only care about the positions of 1s and 2s.

If we scan the array from left to right, we can keep track of the most recent position where we saw a 1 and the most recent position where we saw a 2.

Whenever we encounter a 1, the closest previously seen 2 is the only candidate that could produce a new minimum distance ending at the current position.

Similarly, whenever we encounter a 2, the closest previously seen 1 is the only candidate that could produce a new minimum distance ending at the current position.

By updating the answer whenever we see a 1 or 2, we can find the minimum distance in a single pass.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check every (1, 2) pair explicitly
Optimal	O(n)	O(1)	Single scan while tracking latest positions of 1 and 2

Algorithm Walkthrough

1. Initialize last_one to -1. This stores the most recent index where a 1 was seen.
2. Initialize last_two to -1. This stores the most recent index where a 2 was seen.
3. Initialize answer to a very large value such as positive infinity.
4. Scan the array from left to right.
5. If the current value is 1, update last_one to the current index. If a 2 has already been seen (last_two != -1), compute the distance between the current index and last_two, then update the minimum answer.
6. If the current value is 2, update last_two to the current index. If a 1 has already been seen (last_one != -1), compute the distance between the current index and last_one, then update the minimum answer.
7. Ignore elements equal to 0 because they do not participate in valid pairs.
8. After the scan finishes, if answer was never updated, return -1.
9. Otherwise, return answer.

Why it works

When scanning left to right, every time a 1 or 2 appears, the nearest possible matching value on its left is the most recently seen occurrence of the opposite value. Any older occurrence would be farther away and therefore cannot produce a smaller distance. Since every potential minimum pair must be formed when one of its endpoints is processed, checking only the latest opposite occurrence is sufficient to discover the global minimum distance.

Python Solution

class Solution:
    def minAbsoluteDifference(self, nums: list[int]) -> int:
        last_one = -1
        last_two = -1
        answer = float("inf")

        for index, value in enumerate(nums):
            if value == 1:
                last_one = index
                if last_two != -1:
                    answer = min(answer, index - last_two)

            elif value == 2:
                last_two = index
                if last_one != -1:
                    answer = min(answer, index - last_one)

        return -1 if answer == float("inf") else answer

The implementation maintains the most recent positions of 1 and 2 while traversing the array once.

Whenever a 1 is encountered, its position is stored in last_one. If a 2 was previously seen, the distance between them is computed and compared against the current best answer.

The same logic is applied symmetrically when encountering a 2. Since the scan proceeds from left to right, the difference index - previous_index is already nonnegative and equals the absolute distance between the two indices.

After processing the entire array, the code returns -1 if no valid pair was found. Otherwise, it returns the minimum distance discovered during the scan.

Go Solution

func minAbsoluteDifference(nums []int) int {
	lastOne := -1
	lastTwo := -1
	answer := len(nums) + 1

	for i, value := range nums {
		if value == 1 {
			lastOne = i
			if lastTwo != -1 {
				distance := i - lastTwo
				if distance < answer {
					answer = distance
				}
			}
		} else if value == 2 {
			lastTwo = i
			if lastOne != -1 {
				distance := i - lastOne
				if distance < answer {
					answer = distance
				}
			}
		}
	}

	if answer == len(nums)+1 {
		return -1
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python solution. Instead of using positive infinity, it initializes answer to len(nums) + 1, which is guaranteed to be larger than any possible valid distance. Since array indices are small and the maximum distance is at most len(nums) - 1, there are no integer overflow concerns.

Worked Examples

Example 1

nums = [1,0,0,2,0,1]

Index	Value	last_one	last_two	answer
Start	-	-1	-1	inf
0	1	0	-1	inf
1	0	0	-1	inf
2	0	0	-1	inf
3	2	0	3	3
4	0	0	3	3
5	1	5	3	2

Final answer:

2

The valid pairs are:

(0, 3) -> 3
(5, 3) -> 2

The minimum is 2.

Example 2

nums = [1,0,1,0]

Index	Value	last_one	last_two	answer
Start	-	-1	-1	inf
0	1	0	-1	inf
1	0	0	-1	inf
2	1	2	-1	inf
3	0	2	-1	inf

No 2 is ever found, so no valid pair exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through the array
Space	O(1)	Only a few variables are stored

The algorithm visits each element exactly once. Every iteration performs only constant-time operations such as assignments and comparisons. No auxiliary data structures whose size depends on n are used, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.minAbsoluteDifference([1, 0, 0, 2, 0, 1]) == 2  # example 1
assert sol.minAbsoluteDifference([1, 0, 1, 0]) == -1  # example 2
assert sol.minAbsoluteDifference([1, 2]) == 1  # adjacent valid pair
assert sol.minAbsoluteDifference([2, 1]) == 1  # reverse order still valid
assert sol.minAbsoluteDifference([1]) == -1  # only one element, no 2
assert sol.minAbsoluteDifference([2]) == -1  # only one element, no 1
assert sol.minAbsoluteDifference([0, 0, 0]) == -1  # neither value exists
assert sol.minAbsoluteDifference([1, 1, 1, 2]) == 1  # closest 1 near end
assert sol.minAbsoluteDifference([2, 2, 2, 1]) == 1  # closest 2 near end
assert sol.minAbsoluteDifference([1, 0, 2, 0, 1, 0, 2]) == 2  # multiple pairs
assert sol.minAbsoluteDifference([1, 2, 1, 2, 1, 2]) == 1  # many adjacent pairs
assert sol.minAbsoluteDifference([0, 1, 0, 0, 0, 2, 0]) == 4  # distant pair

Test Summary

Test	Why
[1,0,0,2,0,1]	Official example with multiple valid pairs
[1,0,1,0]	Official example with no valid pair
[1,2]	Smallest possible valid distance
[2,1]	Valid pair with reversed ordering
[1]	Missing 2
[2]	Missing 1
[0,0,0]	Neither required value exists
[1,1,1,2]	Multiple 1s before one 2
[2,2,2,1]	Multiple 2s before one 1
[1,0,2,0,1,0,2]	Multiple candidate pairs
[1,2,1,2,1,2]	Repeated adjacent matches
[0,1,0,0,0,2,0]	Large separation between values

Edge Cases

No Valid Pair Exists

An array may contain only 1s, only 2s, or neither value. In such situations, no valid pair can be formed. A common bug is returning an uninitialized answer value. This implementation avoids that issue by keeping answer at infinity and returning -1 if it was never updated.

Closest Pair Appears in Reverse Order

The problem defines a valid pair using values rather than index ordering. A 2 can appear before a 1, such as in [2,1]. An implementation that only searches for 1s before 2s would fail. By tracking both last_one and last_two, the algorithm correctly handles either ordering.

Multiple Consecutive Occurrences

Arrays such as [1,1,1,2] or [2,2,2,1] contain many repeated values. A naive implementation might compare against outdated positions and miss the closest pair. This algorithm always stores the most recent occurrence of each value, ensuring that the smallest possible distance is considered whenever a matching value is encountered.

Adjacent Values

When a 1 and 2 are next to each other, the answer should be 1, which is the smallest possible nonzero distance between two distinct indices. The algorithm naturally detects this situation during the scan and updates the minimum answer immediately.