Minimum Absolute Difference Between Two Values

Difficulty: Easy | Acceptance: 66.40% | Paid: No Topics: Array, Enumeration

You are given a 0-indexed integer array nums and an integer k.

Return the minimum absolute difference between any two elements nums[i] and nums[j] such that abs(i - j) >= k.

The absolute difference between two numbers nums[i] and nums[j] is defined as abs(nums[i] - nums[j]).

• Examples
• Constraints
• Brute Force Enumeration
• Sorting by Value

Examples

Example 1

Input:

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

Output:

2

Explanation: The valid pairs are:

(0, 3) which has absolute difference of abs(0 - 3) = 3.

(5, 3) which has absolute difference of 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 <= 100
- 0 <= nums[i] <= 2

Brute Force Enumeration

Intuition Since the constraint on the array length is very small ($N \le 100$), we can simply check every possible pair of elements in the array. We calculate the absolute difference of their indices to see if it meets the requirement abs(i - j) >= k, and if so, we update our minimum difference found so far.

Steps

• Initialize a variable min_diff to a very large number (e.g., infinity).
• Iterate through the array with index i from 0 to n-1.
• Iterate through the array with index j from 0 to n-1.
• Check if abs(i - j) >= k.
• If true, calculate abs(nums[i] - nums[j]) and update min_diff if this value is smaller.
• Return min_diff.

class Solution:
    def minDifference(self, nums: list[int], k: int) -> int:
        n = len(nums)
        min_diff = float('inf')
        for i in range(n):
            for j in range(n):
                if abs(i - j) >= k:
                    diff = abs(nums[i] - nums[j])
                    if diff < min_diff:
                        min_diff = diff
        return min_diff

Complexity

• Time: O(n²) — We iterate through all pairs of indices.
• Space: O(1) — We only use a few variables for storage.
• Notes: This is the most straightforward approach and is efficient enough given the constraint n <= 100.

Sorting by Value

Intuition The minimum absolute difference between any two numbers in a set is always achieved by two adjacent numbers when the set is sorted. We can leverage this property by sorting the array elements while keeping track of their original indices. Then, we only need to check adjacent elements in this sorted list to see if their original indices satisfy the distance constraint abs(i - j) >= k.

Steps

• Create a list of pairs (value, original_index) from the input array.
• Sort this list based on the value.
• Initialize min_diff to a large number.
• Iterate through the sorted list from index 0 to n-2.
• For each element at i, compare it with the element at i+1.
• Check if abs(original_index_i - original_index_j) >= k.
• If true, calculate the difference in values and update min_diff.
• Return min_diff.

class Solution:
    def minDifference(self, nums: list[int], k: int) -> int:
        # Create list of (value, index)
        indexed_nums = [(val, idx) for idx, val in enumerate(nums)]
        # Sort by value
        indexed_nums.sort(key=lambda x: x[0])
        
        min_diff = float('inf')
        n = len(indexed_nums)
        
        for i in range(n - 1):
            val1, idx1 = indexed_nums[i]
            val2, idx2 = indexed_nums[i + 1]
            
            if abs(idx1 - idx2) >= k:
                diff = abs(val1 - val2)
                if diff < min_diff:
                    min_diff = diff
                    
        return min_diff

Complexity

• Time: O(n log n) — Sorting the array dominates the time complexity.
• Space: O(n) — We need extra space to store the (value, index) pairs.
• Notes: While this approach is theoretically faster for large n, the overhead of sorting and extra space might not be worth it for n <= 100 compared to the simple brute force method.