Solution For Minimum Absolute Difference

Problem Statement:

Given an array of integers, find the minimum absolute difference between any two elements in the array.

Solution:

One of the simplest approaches to solve this problem is to first sort the array in non-decreasing order so that we can easily compare adjacent elements of the array for finding minimum absolute difference. After sorting the array, we iterate through it and calculate the absolute difference between adjacent elements and compare it with the current minimum absolute difference. If the absolute difference is smaller than the current minimum, we update the current minimum.

Algorithm:

1. Sort the array in non-decreasing order.
2. Initialize a variable named min_diff with the maximum possible value.
3. Iterate through the array, starting from the second element (index 1).
4. Calculate the absolute difference between the current element and the previous element.
5. If the absolute difference is smaller than the current value of min_diff, update min_diff to be the absolute difference.
6. Return the final value of min_diff.

Code:

class Solution {
public:
int getMinimumDifference(vector<int>& nums) {
sort(nums.begin(), nums.end());
int min_diff = INT_MAX;
for (int i = 1; i < nums.size(); i++) {
int diff = abs(nums[i] - nums[i-1]);
if (diff < min_diff) {
min_diff = diff;
}
}
return min_diff;
}
};

Time Complexity:

The time complexity of the above algorithm is O(nlogn) where n is the number of elements in the array. The complexity is dominated by the sorting algorithm used to sort the array.

Space Complexity:

The space complexity of the above algorithm is O(1), as we are not using any extra space apart from the input array.

Step by Step Implementation For Minimum Absolute Difference

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. 

Return a list of all such pairs of elements with absolute difference sorted in ascending order.



class Solution {
    public List> minimumAbsoluteDifference(int[] arr) {
        // sort the array
        Arrays.sort(arr);
        
        // initialize a list to store the results
        List> result = new ArrayList<>();
        
        // iterate through the array
        for (int i = 0; i < arr.length - 1; i++) {
            // if the difference between the current element and the next element is less than or equal to the minimum difference
            if (Math.abs(arr[i] - arr[i + 1]) <= minDiff) {
                // create a list to store the pair of elements
                List pair = new ArrayList<>();
                // add the current element to the list
                pair.add(arr[i]);
                // add the next element to the list
                pair.add(arr[i + 1]);
                // add the list to the result
                result.add(pair);
            }
        }
        
        // return the result
        return result;
    }
}

def minimumAbsoluteDifference(arr): 
    
    # Initialize difference as infinite 
    diff = 10**20
      
    # Find the min and max element in array 
    L_max = max(arr) 
    L_min = min(arr) 
      
    # Check if array contains only one element 
    if L_max == L_min: 
        return 0
      
    # Find the minimum difference by comparing difference 
    # of all possible pairs in given array 
    for i in range(0, len(arr)-1): 
        for j in range(i+1, len(arr)): 
            if abs(arr[i] - arr[j]) < diff: 
               diff = abs(arr[i] - arr[j]) 
                 
    # return min diff 
    return diff

/**
 * @param {number[]} arr
 * @return {number}
 */
var minimumAbsoluteDifference = function(arr) {
    // sort the array
    arr.sort((a, b) => a - b);
    
    // set minDifference to the difference between the first two elements
    let minDifference = Math.abs(arr[0] - arr[1]);
    
    // iterate through the array
    for (let i = 1; i < arr.length - 1; i++) {
        // set difference to the absolute value of the difference between the current element and the next element
        let difference = Math.abs(arr[i] - arr[i + 1]);
        
        // if difference is less than minDifference, set minDifference to difference
        if (difference < minDifference) {
            minDifference = difference;
        }
    }
    
    // return minDifference
    return minDifference;
};

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. 

Return a list of pairs in ascending order(with respect to pairs), each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr
 

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]
Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]
 

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

#include  
using namespace std; 
  
// Function to find the minimum absolute 
// difference of any two elements 
void findMinAbsDiff(int arr[], int n) 
{ 
    // Sort the array 
    sort(arr, arr + n); 
  
    // Find the minimum diff 
    int min_diff = abs(arr[0] - arr[1]); 
    for (int i = 0; i < n - 1; i++) 
        if (abs(arr[i] - arr[i + 1]) < min_diff) 
            min_diff = abs(arr[i] - arr[i + 1]); 
  
    // Print all pairs with difference equal 
    // to min_diff. 
    for (int i = 0; i < n - 1; i++) 
        if (abs(arr[i] - arr[i + 1]) == min_diff) 
            cout << "(" << arr[i] << ", "
                 << arr[i + 1] << ")" << endl; 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { 1, 5, 3, 19, 18, 25 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    findMinAbsDiff(arr, n); 
    return 0; 
}

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. 

Return a list of all such pairs sorted in ascending order, each pair [a, b] follows

a, b are from arr
a < b
b - a equals to the minimum absolute difference of any two elements in arr
 

Example 1:

Input: arr = [4,2,1,3]
Output: [[1,2],[2,3],[3,4]]
Explanation: The minimum absolute difference is 1. List all pairs with difference equal to 1 in ascending order.
Example 2:

Input: arr = [1,3,6,10,15]
Output: [[1,3]]
Example 3:

Input: arr = [3,8,-10,23,19,-4,-14,27]
Output: [[-14,-10],[19,23],[23,27]]
 

Constraints:

2 <= arr.length <= 10^5
-10^6 <= arr[i] <= 10^6

public class Solution {
    public IList> MinimumAbsDifference(int[] arr) {
        
        // sort the array
        Array.Sort(arr);
        
        // create a list to store the output
        List> output = new List>();
        
        // create a variable to store the minimum absolute difference
        int minDifference = Int32.MaxValue;
        
        // iterate through the array
        for(int i = 0; i < arr.Length - 1; i++) {
            
            // calculate the absolute difference between the current element and the next element
            int difference = Math.Abs(arr[i] - arr[i + 1]);
            
            // if the difference is less than the minimum difference
            if(difference < minDifference) {
                
                // set the minimum difference to the current difference
                minDifference = difference;
                
                // clear the output list
                output.Clear();
                
                // add the current pair to the output list
                output.Add(new List {arr[i], arr[i + 1]});
                
            // if the difference is equal to the minimum difference    
            } else if(difference == minDifference) {
                
                // add the current pair to the output list
                output.Add(new List {arr[i], arr[i + 1]});
            }
        }
        
        // return the output list
        return output;
    }
}