Minimum Absolute Difference Leetcode Solution

The problem Minimum Absolute Difference Leetcode Solution provides us an unsorted array or vector containing some integers. We are required to find out all the pairs that have a difference equal to that of minimum absolute difference. The minimum absolute difference is the minimum value of absolute difference that can be achieved by picking up any two different elements among all possible integers from the given vector or array. So, without diving deep into the solution let’s first take a look at a few examples.

arr = [4,2,1,3]

[[1,2],[2,3],[3,4]]

Explanation: Since there are only three such pairs with the minimum absolute difference. We return them as the answer to the problem. All three of them have the same difference of 1. The difference of 1 is the least possible difference.

arr = [1,3,6,10,15]

[[1,3]]

Explanation: Since the minimum absolute difference is equal to 2, and can be achieved only by a single pair of integers. This pair of integers is returned as the answer.

Approach for Minimum Absolute Difference Leetcode Solution

The problem Minimum Absolute Difference Leetcode Solution, asks us to find all the pairs of integers that have the difference between them equal to the minimum absolute difference. We had already stated what is the minimum absolute difference. So, instead of looking at that let’s focus on how to solve the problem. So, first of all, we need to find the minimum absolute difference. The minimum absolute difference can be found only between the adjacent elements when arranged in a sorted manner. The problem provided us with an unsorted array or vector. So, first, we sort the array. Then keep track of the adjacent differences and update the answer whenever we find a smaller difference.

We also create an unordered set or hash set that stores the integers from the vector. Bow we just traverse over the array and try to find the number that has a difference equal to the minimum absolute difference obtained, where the current element is the larger of the two. If we find such an element in our hash set, we add the pair in the answers. but if we don’t, we simply move ahead.

Code

C++ code for Minimum Absolute Difference Leetcode Solution

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> minimumAbsDifference(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    int mnDiff = INT_MAX, n = arr.size();
    unordered_set<int> h;
    for(int i=0;i<n-1;i++){
        mnDiff = min(mnDiff, arr[i+1] - arr[i]);
        h.insert(arr[i]);
    }
    h.insert(arr[n-1]);

    vector<vector<int>> l;
    for(int i=0;i<n;i++){
        if(h.count(arr[i]-mnDiff)){
            l.push_back({arr[i]-mnDiff, arr[i]});
        }
    }
    return l;
}

int main(){
    vector<int> sequence = {4, 3, 1, 2};
    vector<vector<int>> output = minimumAbsDifference(sequence);
    for(auto x: output){
        cout<<x[0]<<" "<<x[1]<<endl;
    }
}

1 2
2 3
3 4

Java code for Minimum Absolute Difference Leetcode Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        int mnDiff = Integer.MAX_VALUE, n = arr.length;
        HashSet<Integer> h = new HashSet<Integer>();
        for(int i=0;i<n-1;i++){
            mnDiff = Math.min(mnDiff, arr[i+1] - arr[i]);
            h.add(arr[i]);
        }
        h.add(arr[n-1]);
        
        List<List<Integer>> l = new ArrayList<List<Integer>>();
        for(int i=0;i<n;i++){
            if(h.contains(arr[i]-mnDiff)){
                l.add(new ArrayList<Integer>(Arrays.asList(arr[i]-mnDiff, arr[i])));
            }
        }
        return l;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] arr = {4, 3, 1, 2};
    List<List<Integer>> output = minimumAbsDifference(arr);
    for(List<Integer> x: output){
      System.out.println(x);
    }
  }
}

[1, 2]
[2, 3]
[3, 4]

Complexity Analysis

Time Complexity

O(N), since we traverse the given array, and have used a hash set that has reduced the time complexity.

Space Complexity

O(N), because we store the elements of the array in the hash set. The space complexity is linear.