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

  • a, b are from arr
  • a < b
  • 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]]

Constraints:

  • 2 <= arr.length <= 105
  • -106 <= arr[i] <= 106
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 5
    integer, dimension(n) :: arr
    integer, dimension(:, :), allocatable :: pairs
    integer :: i, j, k

    ! Example 1
    arr = [4, 2, 1, 3]
    call solve(arr, pairs)
    write (*, '(A)') 'Example 1:'
    do i = 1, size(pairs, 1)
        write (*, '(2I5)') pairs(i, :)
    end do
    deallocate (pairs)

    ! Example 2
    arr = [1, 3, 6, 10, 15]
    call solve(arr, pairs)
    write (*, '(A)') 'Example 2:'
    do i = 1, size(pairs, 1)
        write (*, '(2I5)') pairs(i, :)
    end do
    deallocate (pairs)

    ! Example 3
    arr = [3, 8, -10, 23, 19, -4, -14, 27]
    call solve(arr, pairs)
    write (*, '(A)') 'Example 3:'
    do i = 1, size(pairs, 1)
        write (*, '(2I5)') pairs(i, :)
    end do
    deallocate (pairs)

contains

    subroutine solve(arr, pairs)
        implicit none
        integer, intent(in) :: arr(:)
        integer, allocatable, intent(out) :: pairs(:, :)
        integer :: min_diff, diff, i, j, k

        allocate (pairs(size(arr), 2))

        min_diff = huge(min_diff)
        do i = 1, size(arr) - 1
            do j = i + 1, size(arr)
                diff = abs(arr(j) - arr(i))
                if (diff < min_diff) then
                    min_diff = diff
                    pairs(:, :) = reshape(
❌ Compiled
❌ Executed
❌ Correct 
module pair_with_min_abs_diff

implicit none

contains

subroutine solve(arr, pairs)

! arr: array of distinct integers
! pairs: list of pairs with minimum absolute difference

integer, intent(in) :: arr(:)
integer, allocatable, intent(out) :: pairs(:, :)

! local variables
integer :: i, j, n, min_diff, min_diff_idx

! initialize variables
n = size(arr)
allocate(pairs(n, 2))

! loop through all pairs
do i = 1, n - 1
    do j = i + 1, n
        ! calculate absolute difference
        min_diff = abs(arr(i) - arr(j))
        ! check if minimum absolute difference is found
        if (min_diff < min_diff_idx) then
            min_diff_idx = min_diff
            pairs(i, :) = [arr(i), arr(j)]
        end if
    end do
end do

! sort pairs in ascending order
call sort(pairs)

end subroutine solve

end module pair_with_min_abs_diff

program test

use pair_with_min_abs_diff

implicit none

! test cases
integer, parameter :: arr1(4) = [4, 2, 1, 3]
integer, parameter :: arr2(5) = [1, 3, 6, 10, 15]
integer, parameter :: arr3(8) = [3, 8, -10, 23, 19, -4, -14, 27]

! expected output
integer, parameter :: pairs1(3, 2) = reshape([1, 2, 2, 3, 3, 4], [3, 2])
integer, parameter :: pairs2(1, 2) = reshape([1, 3], [1, 2])
integer, parameter :: pairs3(3, 2) = reshape([-14, -10, 19, 23, 23, 27], [3, 2])

! test variables
integer, allocatable :: pairs(:, :)

! test case 1
call solve(arr1, pairs)
if (any(pairs .ne. pairs1)) error stop "Test case 1 failed"

! test case 2
call solve(arr2, pairs)
if (any(pairs .ne. pairs2)) error stop "Test case 2 failed"

! test case 3
call solve(arr3, pairs)
if (any(pairs .ne. pairs3)) error stop "Test case 3 failed"

print *, "All tests passed!"

end program test
🌐 Data from online sources 
from typing import List

def minimumAbsDifference(arr: List[int]) -> List[List[int]]:
    arr.sort()
    min_diff = min(arr[i] - arr[i - 1] for i in range(1, len(arr)))

    result = []
    for i in range(1, len(arr)):
        if arr[i] - arr[i - 1] == min_diff:
            result.append([arr[i - 1], arr[i]])

    return result
  1. Sort the input array in ascending order.
  2. Iterate through the sorted array and find the minimum absolute difference between adjacent elements. This value will be the minimum difference between any two elements in the array.
  3. Iterate through the sorted array again and construct the output list by adding pairs of elements with an absolute difference equal to the minimum difference found in step 2.
🌐 Data from online sources 
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<vector<int>> result;
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] - arr[i - 1] == minDiff) {
            result.push_back({arr[i - 1], arr[i]});
        }
    }

    return result;
}
  1. Sort the input array in ascending order.
  2. Iterate through the sorted array and find the minimum absolute difference between adjacent elements. This value will be the minimum difference between any two elements in the array.
  3. Iterate through the sorted array again and construct the output list by adding pairs of elements with an absolute difference equal to the minimum difference found in step 2.