Minimum Absolute Difference

class Solution {
public:
    vector<vector<int>> findMinimalDifferencePairs(vector<int>& inputArray) {
        int minVal = *min_element(inputArray.begin(), inputArray.end());
        int maxVal = *max_element(inputArray.begin(), inputArray.end());
        int offset = -minVal;
        vector<uint8_t> presenceMap(maxVal - minVal + 1);
        vector<vector<int>> result;
        
        for (const int& value : inputArray) {
            presenceMap[value + offset] = 1;
        }
        
        int leastDiff = maxVal - minVal;
        int former = 0;
        
        for (int current = 1; current <= maxVal + offset; ++current) {
            if (presenceMap[current] == 0) {
                continue;
            }
            
            if (current - former == leastDiff) {
                result.push_back({former - offset, current - offset});
            } else if (current - former < leastDiff) {
                leastDiff = current - former;
                result = {{former - offset, current - offset}};
            }
            
            former = current;
        }
        
        return result;
    }
};

This solution in C++ focuses on finding pairs in an array that have the minimum absolute difference between them.

• Start with identifying the smallest and largest values in the given array, which defines the range of possible values. This step is crucial for calculating the offsets used in the presence map to effectively mark which values appear in the array.

• Initialize a presence map that uses an efficient boolean-like value storage. The purpose of this map is to track the existence of elements within the adjusted range of values. Values are offset to ensure that the array indices always stay positive.

• Iterate through the input array to mark the presence of each value in the presence map. This marks all existing values in the modified range based on their offset.

• Determine the minimum absolute difference by comparing each successive pair of values found in the presence map. Keep track of this minimal difference and the associated pairs.

• Iterate through the map to find and potentially update the minimum difference and corresponding pairs. If a smaller difference is found, update the result and the minimum difference value.

• The function finally returns a vector of pairs that have the smallest absolute difference as determined through the iterative comparisons.

This process ensures efficient computation by minimizing unnecessary comparisons and directly leveraging the presence map to check only the existing values, thus optimizing the solution's performance.

class Solution {
    public List<List<Integer>> findMinimumAbsDifference(int[] inputArray) {
        int smallest = inputArray[0], largest = inputArray[0];
        for (int value : inputArray) {
            smallest = Math.min(smallest, value);
            largest = Math.max(largest, value);
        }
        int adjust = -smallest;
        int[] bins = new int[largest - smallest + 1];
        List<List<Integer>> result = new ArrayList<>();

        for (int value : inputArray) {
            bins[value + adjust] = 1;
        }

        int smallestDifference = largest - smallest;
        int previous = 0;
        
        for (int current = 1; current <= largest + adjust; ++current) {
            if (bins[current] == 0) continue;
            
            if (current - previous == smallestDifference) {       
                result.add(Arrays.asList(previous - adjust, current - adjust));
            } else if (current - previous < smallestDifference) {
                result = new ArrayList<>();
                smallestDifference = current - previous;
                result.add(Arrays.asList(previous - adjust, current - adjust));                
            }
            
            previous = current;
        }
        
        return result;
    }
}

This Java solution aims to find all pairs of elements in an array that have the minimum absolute difference. The approach uses an efficient strategy by leveraging the properties of minimum and maximum elements in the array combined with a binning technique to keep the running time complexity manageable.

• First, the algorithm determines the smallest and largest elements in the array. These values help in setting up a bins array, which is essentially used to track which numbers are present in the input array.
• It initializes the bins array to mark the presence of each element by indexing relative to the smallest element. This adjustment aligns the smallest value with index 0 in the bins array, ensuring that all indices used are non-negative.
• The algorithm then iterates through the bins array to identify consecutive elements (signifying minimal differences). During this scan, it checks and updates the smallest difference found so far.
• If the current difference matches the smallest difference found so far, the corresponding pair gets added to the result list. If a smaller difference is found, the result list is cleared and initiated with the current pair.
• Finally, the function returns a list of pairs that represent the minimum absolute differences.

This solution is effective in not just finding the minimum difference but also extracting all pairs with that minimum difference, making it suitable for large-scale data sets where direct comparison could be computationally expensive.

var findSmallestDifferencePairs = function(nums) {
    var smallest = nums[0], largest = nums[0];
    for (const number of nums) {
        smallest = Math.min(smallest, number);
        largest = Math.max(largest, number);
    }
    var offset = -smallest;
    var presenceMarker = new Array(largest - smallest + 1).fill(0);
    var resultPairs = [];
    
    for (const number of nums) {
        presenceMarker[number + offset] = 1;
    }

    var minDifference = largest - smallest;
    var lastSeen = 0;
    
    for (let i = 1; i <= largest + offset; ++i) {
        if (presenceMarker[i] === 0) continue;

        if (i - lastSeen === minDifference) {
            resultPairs.push([lastSeen - offset, i - offset]);
        } else if (i - lastSeen < minDifference) {
            resultPairs = [];
            minDifference = i - lastSeen;
            resultPairs.push([lastSeen - offset, i - offset]);
        }
        
        lastSeen = i;
    }
    return resultPairs;
};

This script efficiently identifies pairs of elements in an array of integers (nums) with the minimum absolute difference.

• Begin by initializing two variables, smallest and largest, to store the minimum and maximum values in nums.
• Iterate over nums to update smallest and largest using Math.min and Math.max functions.
• Create an offset variable to shift all numbers by the negative of smallest, ensuring all values are non-negative.
• Initialize an array presenceMarker with largest - smallest + 1 elements, all set to 0. This array will track the presence of each number in the adjusted range.
• Mark the presence of each number in presenceMarker by setting the corresponding index to 1.
• Calculate the initial minDifference as the difference between largest and smallest.
• Loop through presenceMarker to assess differences between consecutive numbers.
• If two consecutive numbers with markers are found and the difference matches the current minDifference, append this pair to resultPairs.
• If a smaller difference is found, reset resultPairs, update minDifference, and add the new pair.
• The end of the loop marks the completion of evaluating optimal pairs, which are returned in resultPairs.

In essence, use this script as a way to find all pairs in nums with the smallest absolute difference, harnessing space transformation and sequential evaluation.

class Solution:
    def getMinPairs(self, input_list: List[int]) -> List[List[int]]:
        # Determine minimum and maximum values in 'input_list'
        smallest = min(input_list)
        largest = max(input_list)
        offset = -smallest
        normalized = [0] * (largest - smallest + 1)
        closest_pairs = []
        
        # Normalize input values and map to 'normalized' index
        for value in input_list:
            normalized[value + offset] = 1
        
        # Initial large pair difference to ensure the first pair is smaller
        smallest_diff = largest - smallest
        previous = 0
        
        # Process the normalized values to find the closest pairs
        for current in range(1, largest + offset + 1):
            if normalized[current] == 0:
                continue
            
            diff = current - previous
            if diff == smallest_diff:
                closest_pairs.append([previous - offset, current - offset])
            elif diff < smallest_diff:
                closest_pairs = [[previous - offset, current - offset]]
                smallest_diff = diff
            
            previous = current
        
        return closest_pairs

This Python solution is designed to find pairs of elements in a list that have the smallest absolute difference. Here’s a step-by-step breakdown of how the solution operates:

1. Initialize variables to find the smallest and largest elements in the input list. This helps in normalizing the values.
2. Normalize the input list values to a zero-based index for easier computation by adjusting each element using the smallest value as an offset.
3. Compute differences between successive elements that have been normalized.
4. Keep track of the smallest difference found and record pairs that have this smallest difference.
5. If a smaller difference than previously identified is found, reset the list of closest pairs and update the smallest difference.
6. Return the list of pairs that share the minimum absolute difference.

The approach ensures efficient processing by normalizing the values and then only comparing adjacent elements, taking advantage of the properties of sorted sequences indirectly through a normalized array. This approach minimizes the overall number of comparisons needed.