Facebook Pixel

3880. Minimum Absolute Difference Between Two Values

EasyArrayEnumeration
LeetCode β†—

Problem Description

You are given an integer array nums that contains only the values 0, 1, and 2.

A pair of indices (i, j) is considered valid when two conditions are met:

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

For every valid pair, you can compute the absolute difference between its two indices, defined as abs(i - j).

Your task is to find and return the minimum absolute difference among all valid pairs. If there is no valid pair (for example, the array has no 1 or no 2), return -1.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Straightforwardstep-by-step?yesMath orbitmanipulation?noSimulation /Basic DSA

A single linear scan tracking the last seen index of each digit suffices to find the minimum absolute difference between pairs.

Open in Flowchart

Intuition

The key observation is that we are looking for a 1 and a 2 whose positions are as close to each other as possible. A natural but slow idea would be to compare every 1 with every 2, but that costs O(n^2) time.

To do better, think about what happens as we scan the array from left to right. At each position, if the current number is a 2, the closest 1 that can pair with it is the most recent 1 we have seen so far. Likewise, if the current number is a 1, the closest 2 that can pair with it is the most recent 2 seen so far. In both cases, only the latest occurrence of the other digit matters, because any earlier occurrence would be even farther away.

This tells us we only need to remember the last seen index of each digit as we walk through the array. Whenever we encounter a 1 or a 2, we immediately try to form a pair with the last index of the other value and update our best answer.

A neat trick simplifies the bookkeeping: since the relevant pairing is always between 1 and 2, the "other" digit of x is exactly 3 - x (because 3 - 1 = 2 and 3 - 2 = 1). So with a single array last storing the most recent index of each digit, we can look up last[3 - x] to grab the matching partner. This lets us solve the problem in one pass with O(n) time and constant extra space.

Solution Approach

Solution 1: Single Pass

We use an array last of length 3 to record the last occurrence index of each digit 0, 1, and 2. Since digit 0 never participates in a valid pair, only the slots for 1 and 2 truly matter, but keeping all three keeps the indexing clean. Initially, every entry is set to a very small value (here -inf), so that any pairing computed before a real partner has been seen produces a difference too large to ever become the answer.

We also keep an answer variable ans, initialized to n + 1, which is larger than any possible valid difference. This makes it easy to detect later whether a valid pair was ever found.

We then iterate through nums. For the current number x at index i:

  • If x is non-zero (that is, x is 1 or 2), we try to form a pair with the most recent occurrence of the other digit. The other digit is 3 - x, because 3 - 1 = 2 and 3 - 2 = 1. We update the answer with ans = min(ans, i - last[3 - x]).
  • Then we update last[x] = i so that future numbers can pair with this position.

Notice that since we always scan left to right and i is the current (largest so far) index, i - last[3 - x] is naturally non-negative and equals the absolute difference. There is no need for an explicit abs call.

After the loop ends, if ans is still greater than n, it means no valid pair was ever formed, so we return -1. Otherwise, we return ans.

The time complexity is O(n), where n is the length of the array, since we make a single pass. The space complexity is O(1), as the last array has a fixed size of 3.

Example Walkthrough

Let's trace through the algorithm with a small example: nums = [2, 1, 0, 2, 1].

Setup:

  • n = 5
  • last = [-inf, -inf, -inf] (last seen index of digits 0, 1, 2)
  • ans = n + 1 = 6 (larger than any possible valid difference)

We scan left to right. For each non-zero x at index i, we look up last[3 - x] (the most recent index of the partner digit), update ans, then record last[x] = i.

ix = nums[i]Partner 3 - xlast[3 - x]Candidate i - last[3-x]ans after updateUpdate last
021-infhuge (ignored)6last[2] = 0
11201 - 0 = 11last[1] = 1
20β€”β€” (skip)β€” (no pairing for 0)1last[0] = 2
32113 - 1 = 21last[2] = 3
41234 - 3 = 11last[1] = 4

Step-by-step reasoning:

  1. i = 0, x = 2: The partner is 1, but last[1] = -inf (no 1 seen yet), so the candidate difference is enormous and gets ignored. We record that a 2 lives at index 0.

  2. i = 1, x = 1: The partner is 2, and the most recent 2 is at last[2] = 0. The pair (1, 0) gives 1 - 0 = 1, so ans improves from 6 to 1. We record a 1 at index 1.

  3. i = 2, x = 0: Since x is 0, it never forms a valid pair, so we skip the update. (In the code, only last[0] gets refreshed, which is never queried.)

  4. i = 3, x = 2: The most recent 1 is at last[1] = 1. The pair (1, 3) gives 3 - 1 = 2, which is not better than the current ans = 1, so ans stays 1. We refresh last[2] = 3.

  5. i = 4, x = 1: The most recent 2 is now at last[2] = 3. The pair (4, 3) gives 4 - 3 = 1, tying the current best, so ans stays 1.

Result: After the loop, ans = 1, which is not greater than n, so a valid pair was found. We return 1.

This matches our intuition: the closest 1-and-2 pair in [2, 1, 0, 2, 1] is the adjacent 2, 1 at indices 0 and 1 (or equivalently 2, 1 at indices 3 and 4), giving a minimum absolute difference of 1. Notice we only ever needed the last seen index of each digit β€” never the full history β€” which is exactly why a single pass with O(1) space suffices.

Solution Implementation

1from math import inf
2
3
4class Solution:
5    def minAbsoluteDifference(self, nums: list[int]) -> int:
6        n = len(nums)
7        # Initialize the answer to a value larger than any valid distance.
8        ans = n + 1
9
10        # last_seen[v] stores the most recent index where value v appeared.
11        # Size 3 to cover indices 0, 1, 2; only indices 1 and 2 are used here,
12        # since the loop only proceeds when x is non-zero (i.e. x is 1 or 2).
13        last_seen = [-inf] * 3
14
15        for i, x in enumerate(nums):
16            # Only consider the marker values 1 and 2; skip zeros.
17            if x:
18                # 3 - x maps 1 -> 2 and 2 -> 1, giving the "opposite" value.
19                # The distance between the current index and the last index
20                # of the opposite value is a candidate answer.
21                ans = min(ans, i - last_seen[3 - x])
22                # Record the current index as the latest position of value x.
23                last_seen[x] = i
24
25        # If ans was never updated below the sentinel, no valid pair exists.
26        return -1 if ans > n else ans
27
1class Solution {
2    public int minAbsoluteDifference(int[] nums) {
3        int length = nums.length;
4
5        // Initialize the answer to an impossible-large value (sentinel).
6        // Any valid gap will be at most length - 1, so length + 1 means "not found".
7        int minGap = length + 1;
8
9        // lastIndex[v] stores the most recent position where value v appeared.
10        // Only indices 1 and 2 are used (index 0 is unused padding).
11        // They start far in the "past" so that early reads produce large gaps
12        // that never beat a real answer.
13        int[] lastIndex = new int[3];
14        Arrays.fill(lastIndex, -(length + 1));
15
16        for (int i = 0; i < length; i++) {
17            int value = nums[i];
18
19            // Skip zeros: they are neither of the two complementary values.
20            if (value != 0) {
21                // 3 - value maps 1 <-> 2, giving the complementary value's index.
22                // Distance from the current index to the last complementary value.
23                int complementIndex = 3 - value;
24                minGap = Math.min(minGap, i - lastIndex[complementIndex]);
25
26                // Record the current position for this value.
27                lastIndex[value] = i;
28            }
29        }
30
31        // If minGap was never updated to a real value, no valid pair exists.
32        return minGap > length ? -1 : minGap;
33    }
34}
35```
36
37**A note on correctness / perspectives:**
38
391. **What it computes:** the minimum index distance between an element equal to `1` and an element equal to `2`. The variable naming (`minAbsoluteDifference`) suggests it may be a partial/specialized solution rather than a general "minimum absolute difference" problem β€” the values are restricted to `{0, 1, 2}`.
40
412. **Index safety:** because the only non-zero writes are for `value ∈ {1, 2}`, `lastIndex[value]` and `lastIndex[3 - value]` stay within bounds `[1, 2]`. If `nums` could contain other non-zero values, this would throw an `ArrayIndexOutOfBoundsException`, so the precondition `nums[i] ∈ {0, 1, 2}` is implicit.
42
433. **Alternative styling:** instead of the size-3 array with an unused slot, you could use two explicit variables `lastOne` and `lastTwo` for clarity, trading the compact `3 - value` trick for more readable code:
44
45```java
46int lastOne = -(length + 1);
47int lastTwo = -(length + 1);
48// ...
49if (value == 1) { minGap = Math.min(minGap, i - lastTwo); lastOne = i; }
50else if (value == 2) { minGap = Math.min(minGap, i - lastOne); lastTwo = i; }
51
1class Solution {
2public:
3    int minAbsoluteDifference(vector<int>& nums) {
4        int n = nums.size();
5
6        // Initialize the answer with a value larger than any possible distance.
7        int minDistance = n + 1;
8
9        // last[v] stores the most recent index at which value v appeared.
10        // Initialized to a large negative value so that the first comparison
11        // does not produce a valid (small) distance by accident.
12        vector<int> last(3, -(n + 1));
13
14        for (int i = 0; i < n; ++i) {
15            int value = nums[i];
16
17            // Only non-zero values are meaningful here (values are 1 or 2).
18            if (value != 0) {
19                // The complementary value: if value is 1 -> 2, if value is 2 -> 1.
20                int complement = 3 - value;
21
22                // Update the answer with the distance between the current index
23                // and the last index where the complementary value appeared.
24                minDistance = min(minDistance, i - last[complement]);
25
26                // Record the current index as the latest occurrence of this value.
27                last[value] = i;
28            }
29        }
30
31        // If no valid pair was found, minDistance stays greater than n -> return -1.
32        return minDistance > n ? -1 : minDistance;
33    }
34};
35
1/**
2 * Finds the minimum absolute difference of indices between two elements
3 * whose values sum to 3 (i.e., a pair of 1 and 2).
4 *
5 * The array is expected to contain values in {0, 1, 2}, where:
6 *   - 1 and 2 are complementary (1 + 2 = 3)
7 *   - 0 is treated as a "blank" / ignored value
8 *
9 * @param nums - The input array of numbers.
10 * @returns The minimum index distance between a complementary pair, or -1 if none exists.
11 */
12function minAbsoluteDifference(nums: number[]): number {
13    const n: number = nums.length;
14
15    // Initialize the answer to an impossible large value (sentinel).
16    let ans: number = n + 1;
17
18    // lastIndex[v] stores the most recent index where value v appeared.
19    // Initialized to a large negative sentinel so early comparisons
20    // never produce a valid (small) distance by accident.
21    const lastIndex: number[] = Array(3).fill(-ans);
22
23    for (let i = 0; i < n; ++i) {
24        const x: number = nums[i];
25
26        // Skip the "blank" value 0; only process 1 and 2.
27        if (x) {
28            // The complement of x is (3 - x):
29            //   if x === 1, complement is 2
30            //   if x === 2, complement is 1
31            // Distance from the last occurrence of the complement.
32            ans = Math.min(ans, i - lastIndex[3 - x]);
33
34            // Record the current index as the latest position of value x.
35            lastIndex[x] = i;
36        }
37    }
38
39    // If ans was never updated to a valid distance, return -1.
40    return ans > n ? -1 : ans;
41}
42

Time and Space Complexity

Time Complexity

The time complexity is O(n), where n is the length of the array nums. The code iterates through the array nums exactly once with a single for loop. In each iteration, only constant-time operations are performed, such as comparisons, the min function call, and array indexing/assignment on the fixed-size last array. Therefore, the overall time complexity is O(n).

Space Complexity

The space complexity is O(1). The code only uses a fixed number of extra variables, including n, ans, and the last array which has a constant size of 3. These do not grow with the size of the input array nums, so the extra space used is constant, giving a space complexity of O(1).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using 0 (or another in-range value) as the sentinel for last_seen

A tempting shortcut is to initialize last_seen = [0, 0, 0] instead of [-inf, -inf, -inf]. This silently produces wrong answers because 0 is a legitimate array index.

Consider nums = [2, 0, 0, 1]. The only valid pair is (i=3, j=0) with difference 3. But if last_seen starts at 0, then when we reach the 1 at index 3, we compute i - last_seen[2] = 3 - 0 = 3, which happens to be correct here only by luck. Now consider nums = [1, 2] where we want the answer 1. If we instead had nums = [2, ...] with no 1 before it, a 0-initialized sentinel can fabricate a small difference. For example nums = [0, 2]: when we hit the 2 at index 1, we do ans = min(ans, 1 - last_seen[1]) = 1 - 0 = 1, even though there is no 1 at all in the array. The correct answer is -1, but the buggy code returns 1.

Solution: Use a sentinel that can never be confused with a real index. -inf guarantees that i - last_seen[3 - x] is huge (effectively +inf) until a real partner has been seen, so it can never win the min.

last_seen = [-inf] * 3   # correct: impossible to mistake for an index
# NOT last_seen = [0] * 3   # buggy: index 0 is a valid position

Pitfall 2: Choosing a final sentinel for ans that collides with a valid distance

The code initializes ans = n + 1 and detects "no pair found" with return -1 if ans > n else ans. The maximum possible valid difference in an array of length n is n - 1 (between index 0 and index n - 1). So any sentinel strictly greater than n - 1 works, and n + 1 is safe.

A common mistake is initializing ans = n and then checking if ans >= n. While the check still works, using a sentinel exactly equal to a boundary value invites off-by-one confusion. Worse, if someone writes ans = n - 1 as the sentinel, a genuine pair with the maximum distance n - 1 becomes indistinguishable from "no pair found," producing -1 on valid input.

Solution: Pick a sentinel clearly outside the range of any achievable answer (such as n + 1 or inf) and check against it consistently.

ans = n + 1
# ...
return -1 if ans > n else ans

Pitfall 3: Misreading the pairing direction (which index needs to be 1 vs 2)

The problem requires nums[i] == 1 and nums[j] == 2, but because the answer is an absolute difference, the order of i and j in the subtraction does not affect correctness. The 3 - x trick handles both directions automatically: when the current element is a 1, it pairs with the last 2; when it is a 2, it pairs with the last 1. A pitfall is to "fix" only one direction (e.g., only pair 2s with earlier 1s), which misses pairs where a 1 appears after its closest 2.

Solution: Pair every non-zero element with the most recent occurrence of the opposite value, so both orderings (1 before 2 and 2 before 1) are covered in a single pass.

if x:
    ans = min(ans, i - last_seen[3 - x])  # 3 - x flips 1<->2
    last_seen[x] = i

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Depth first search is equivalent to which of the tree traversal order?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More