algoadvance

Leetcode 1200. Minimum Absolute Difference

Problem Statement

Given an array of distinct integers arr, find all pairs of elements with the minimum absolute difference of any two elements. Specifically, these pairs should be listed in ascending order based on their values, and each pair should be in the format [a, b] where a < b.

Clarifying Questions

  1. Input Size: What is the range of size for the input array?
  2. Element Range: What is the range of values for the elements in the array?
  3. Constraints: Are there any additional constraints or requirements we should consider?

For simplicity, I will assume that:

If these assumptions hold, we’ll proceed with the solution.

Strategy

  1. Sort the Array: For an array of distinct integers, the smallest differences will likely be between consecutive numbers. Thus, sorting simplifies the problem.
  2. Find Minimum Absolute Difference: Post sorting, traverse through the array and compute differences between consecutive elements to find the minimum absolute difference.
  3. Identify Pairs: Traverse again to collect all pairs that have this minimum absolute difference.
  4. Return the Pairs: Ensure pairs are in the required format and order.

Code

import java.util.*;

public class MinimumAbsoluteDifference {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        // Sort the array
        Arrays.sort(arr);
        
        // Initialize the list to store the result
        List<List<Integer>> result = new ArrayList<>();
        
        // Find the minimum absolute difference
        int minDiff = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - arr[i - 1];
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        
        // Collect the pairs with minimum absolute difference
        for (int i = 1; i < arr.length; i++) {
            int diff = arr[i] - arr[i - 1];
            if (diff == minDiff) {
                List<Integer> pair = new ArrayList<>();
                pair.add(arr[i - 1]);
                pair.add(arr[i]);
                result.add(pair);
            }
        }
        
        return result;
    }
    
    // Example driver method for testing
    public static void main(String[] args) {
        MinimumAbsoluteDifference mad = new MinimumAbsoluteDifference();
        int[] arr = {4, 2, 1, 3};
        System.out.println(mad.minimumAbsDifference(arr));  // Output: [[1, 2], [2, 3], [3, 4]]
    }
}

Time Complexity

  1. Sorting: The time complexity for sorting the array is (O(n \log n)).
  2. Finding Minimum Difference: This requires a single pass through the sorted array, making it (O(n)).
  3. Collecting Pairs: Another single pass through the array to collect pairs, also (O(n)).

Thus, the overall time complexity is dominated by the sorting step, making it O(n \log n).

This solution is efficient for the input size constraints and ensures correctness by leveraging simpler problem transformations like sorting.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI