1
\$\begingroup\$

Online coding challenge Hacker Rank.

Given a list of unsorted integers, find the pair of elements that have the smallest absolute difference between them? If there are multiple pairs, find them all.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    private static List<Integer> solve(int []arr) {
        Arrays.sort(arr);
        List<Integer> list = new ArrayList<>();
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < arr.length - 1; i++) {
            int diff = arr[i + 1] - arr[i];
            if (diff < min) {
                min = diff;
                list = new ArrayList<>();
                list.add(arr[i]);
                list.add(arr[i + 1]);
            }
            else if (diff == min) {
                list.add(arr[i]);
                list.add(arr[i + 1]);
            }
        }
        return list;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int []arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = s.nextInt();
        }
        List<Integer> result = solve(arr);
        for (int n : result) {
            System.out.print(n + " ");   
        }
    }
}

Note:

I would definitely have chosen better names in actual scenario.

\$\endgroup\$
1
\$\begingroup\$

here is something with objects:

Model:

static class Pair {
    int x, y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }

    int diff() {
        return y - x;
    }

    @Override
    public String toString() {
        return  x + " " + y + " ";
    }


}

controller:

private static List<Pair> solve(int[] arr) {
    Arrays.sort(arr);
    TreeMap<Integer, List<Pair>> pairsByDiff = new TreeMap<>();

    for (int i = 1; i < arr.length; i++) {
        Pair pair = new Pair(arr[i - 1], arr[i]);
        List<Pair> sameDiffPairs = pairsByDiff.getOrDefault(pair.diff(), new ArrayList<>());
        sameDiffPairs.add(pair);
        pairsByDiff.put(pair.diff(), sameDiffPairs);
    }
    return pairsByDiff.firstEntry().getValue();
}

UI:

public static void main(String[] args) {
       Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int []arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = s.nextInt();
        }
        List<Pair> result = solve(arr);
        for (Pair n : result) {
            System.out.print(n);   
        }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.