Finding pairs of numbers with a given difference

Question

Without changing the outputs or the inputs of the method, how would you make this code more readable ?

I am interested in any general improvement it can be made in terms of readability without WORSEN the time complexity.

Above all I'm interested of know if there is a way of doing all this steps in one line:

• check if the key exist in the map.

• if exist create a list with two elements (pair) and then append the pair to list of pairs that will be the result.

• if not exist do nothing.

Also is there a more elegant way to return array[][] from an ArrayList<ArrayList<Integer>> ?

static int[][] findPairsWithGivenDifference(int[] arr, int k) {

    int n = arr.length; 
    Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 

    ArrayList<ArrayList<Integer>> all = new ArrayList<ArrayList<Integer>>();  

    for (int i = 0; i < n; i++){ 
      map.put(arr[i]-k,arr[i]);
    }

    for (int i = 0; i < n; i++){ 
      int x = arr[i];
      if (map.get(arr[i]) != null) {
        int y = map.get(x);
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(y);
        al.add(x);
        all.add(al);
      }
    }

    int m = all.size();
    int[][] res = new int[m][2];

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < 2; j++) {
        res[i][j] = all.get(i).get(j);
      }
    }

  return res;
}

Answer 1

You don’t need to specify types on the right hand side of a generic declaration as of Java 7.

It’s preferable to declare types as interfaces (List) rather than implementations (ArrayList) where possible.

al and all are meaningless, which makes the code a lot harder to read. Variable names should describe what they contain. Most of your variable names could be better.

You declare x = arr[i], and then use arr[i] on the very next line.

Either use containsKey instead of get() == null or make the get call once and then check the stored value to see if it’s null.

It’s typically a bad idea to mix arrays and generics, but given the target return value, you’d do much better with a List. You can then turn that into an int[][] with all.toArray().

size() and length take approximately zero time to compute. Replacing them with single-letter variables saves you virtually nothing and makes the code much harder to read.

Don’t declare all before you need to. In general, declare variables as narrowly as possible, and as close to where they’re used as possible.

Both for loops could be enhanced for loops.

If you made all the changes I suggest, your code might look something like:

static int[][] findPairsWithGivenDifference(final int[] values, final int difference) {

    final Map<Integer, Integer> map = new HashMap<>();
    for (final int value : values) {
        map.put(value - difference, value);
    }

    final List<int[]> pairs = new ArrayList<>();
    for (final int value : values) {
        final Integer match = map.get(value);
        if (match != null) {
            pairs.add(new int[] { value, match });
        }
    }

    return pairs.toArray(new int[pairs.size()][2]);
}

Answer 2

You don't need to use a map here. A set will work just as well, since you can recreate the original value by adding the difference again.

I'm not sure if it's possible to do it in one line (which of course is not necessarily the most readable solution), but you can get close by converting the input array into a set and then using streams:

static int[][] findPairsWithGivenDifference(final int[] values, final int difference) {

    Collection<Integer> valuesSet = Arrays.stream(values).boxed().collect(Collectors.toSet());

    return valuesSet.stream()
            .map(v -> v - difference)
            .filter(valuesSet::contains)
            .map(v -> new int[] { v, v + difference })
            .toArray(size -> new int[size][2]);
}