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).
Example 1:
Input: nums = [1,0,0,2,0,1]
Output: 2
Explanation:
The valid pairs are:
abs(0 - 3) = 3.abs(5 - 3) = 2.Thus, the answer is 2.
Example 2:
Input: nums = [1,0,1,0]
Output: -1
Explanation:
There are no valid pairs in the array, thus the answer is -1.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 2Problem Overview: Given a list of numbers, you need the smallest absolute difference between any pair of values. The task is simply to find two elements a and b such that |a - b| is minimized.
Approach 1: Brute Force (O(n²) time, O(1) space)
The straightforward method checks every pair of elements. Use two nested loops, compute abs(nums[i] - nums[j]) for all i < j, and track the minimum difference found. This guarantees the correct result but performs n*(n-1)/2 comparisons, which becomes expensive as the array grows. The approach works for small inputs and helps verify correctness during early implementation.
Approach 2: Sort + Single Pass (O(n log n) time, O(1) extra space)
A key observation: the smallest absolute difference must occur between two numbers that are closest in sorted order. After sorting the array, iterate once and compute the difference between adjacent elements only. Maintain a running minimum while scanning from left to right. Sorting takes O(n log n), and the single pass afterward takes O(n), giving an overall complexity of O(n log n) with constant extra space if sorting is done in place.
This approach relies on properties of ordered values: if a ≤ b ≤ c, then |a - c| cannot be smaller than both |a - b| and |b - c|. Because of that, checking only adjacent elements is sufficient.
Problems like this often appear in interviews when discussing arrays and sorting. The optimized method also reflects a common pattern: transform the data structure (sorting) so the final computation becomes a simple linear scan, similar to techniques used in greedy strategies.
Recommended for interviews: Interviewers expect the sort + single pass solution. Starting with brute force demonstrates that you understand the definition of the problem. Moving to the sorted scan shows you can reduce comparisons by exploiting ordering, which is the key insight.
We use an array last of length 3 to record the last occurrence index of digits 0, 1, and 2. Initially, last = [-(n+1), -(n+1), -(n+1)]. We iterate through the array nums. For the current number x, if x is not equal to 0, we update the answer ans = min(ans, i - last[3 - x]), where i is the index of the current number x. Then we update last[x] = i.
After the iteration, if ans is greater than the length of the array nums, it means no valid index pair exists, so we return -1; otherwise, we return ans.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Small arrays or quick correctness checks |
| Sort + Single Pass | O(n log n) | O(1) | General case and interview‑expected solution |
Practice Minimum Absolute Difference Between Two Values with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor