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. Each pair arr[i], arr[j] must be in the format [arr[i], arr[j]] with arr[i] < arr[j].

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

Clarifying Questions

  1. Can we assume that the input array contains at least two elements?
    • Yes, because there would be no pairs if there were fewer than two elements.
  2. Is the array given in any particular order?
    • No, the array is not guaranteed to be in any particular order.
  3. Do we need to consider time and space constraints for large arrays?
    • Typically, performance is a consideration, but for this problem, an O(n log n) solution should be acceptable due to the sorting step involved.

Strategy

  1. Sort the Array: First, we need to sort the array to be able to efficiently compute the differences between consecutive elements.
  2. Find Minimum Absolute Difference: As we traverse the sorted array, we compute the differences between consecutive elements and track the minimum absolute difference found.
  3. Collect Result Pairs: Again, traverse the sorted array and collect all pairs that have this minimum absolute difference.

Code

Here is the C++ solution to the problem:

#include <vector>
#include <algorithm>
#include <cmath>

std::vector<std::vector<int>> minimumAbsDifference(std::vector<int>& arr) {
    // Sort the array
    std::sort(arr.begin(), arr.end());
    
    // Initialize the minimum difference as a large value
    int min_diff = INT_MAX;
    
    // Compute the minimum absolute difference
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        min_diff = std::min(min_diff, arr[i+1] - arr[i]);
    }
    
    // Collect all pairs with the minimum absolute difference
    std::vector<std::vector<int>> result;
    for (size_t i = 0; i < arr.size() - 1; ++i) {
        if (arr[i+1] - arr[i] == min_diff) {
            result.push_back({arr[i], arr[i+1]});
        }
    }
    
    return result;
}

Explanation

  1. Sorting the Array: We sort the array in ascending order which allows us to only consider the differences between consecutive elements.
  2. Finding the Minimum Difference:
    • Initialize the min_diff to the maximum possible integer value.
    • Traverse the array and update min_diff to be the minimum of the current min_diff and the difference between each pair of consecutive elements.
  3. Collecting Result Pairs:
    • Traverse the array again to find all pairs where the difference between consecutive elements is equal to min_diff.
    • Add these pairs to the result list.

Time Complexity

Thus, the overall time complexity of the solution is O(n log n).

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