Minimum Absolute Difference - Leetcode Solution

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.

1