LeetCode - 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 pairs in ascending order(with respect to pairs), each pair [a, b] follows

1. a, b is from arr 2. a < b 3. 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]]

Solution

There are many solutions to the problem.

Solution 1: Brute Force

1. Iterate over the Array and find a minimum difference. 2. Iterate Array in two nested loops to explore all pairs with respect to minimum difference.

Time Complexity : O(n²)

Solution 2: Sorting

1. Iterate over the Array and find a minimum difference. 2. Sort Array before iterate. 2. Iterate array with a single loop [ as minimum difference pair will come next one element to other].

Time Complexity : O(nlogn)

Code


import java.util.*;

public class AbsoluteDifference {

	public static void main(String[] args) {
		
		int [] arr= {3,8,-10,23,19,-4,-14,27};
		
		System.out.println(new AbsoluteDifference().minimumAbsDifference(arr));

	}

	public List<List<Integer>> minimumAbsDifference(int[] arr) {

		List<List<Integer>> result = new ArrayList<List<Integer>>();

		Arrays.sort(arr);
		int minDiff = Integer.MAX_VALUE;

		for (int i = 0; i < arr.length - 1; i++) {

			int tempDiff = arr[i + 1] - arr[i];
			minDiff = Math.min(minDiff, tempDiff);

		}

		for (int i = 0; i < arr.length - 1; i++) {

			int tempDiff = arr[i + 1] - arr[i];

			if (tempDiff == minDiff) {
				List<Integer> list = new ArrayList<Integer>();
				list.add(arr[i]);
				list.add(arr[i + 1]);
				result.add(list);
			}

		}

		return result;
	}
}