0

Am trying to find the closest pair based on sum but am getting a

java.lang.ArrayIndexOutOfBoundsException: -1

Find a pair in array whose sum is closest to sum.

e.g.

Input: arr[] = {10, 22, 28, 29, 30, 40}, sum = 54
Output: 22 and 30

My solution:

import java.util.Arrays;

public class ArrayUtils {

    public static int[] closestPairBasedOnSum(int[] arr, int sum) {
        if (arr == null) {
            return null;
        }

        if (sum < 1) {
            return null;
        }

        int[] closestPair = new int[2];

        int left = 0;
        int right = arr.length - 1;
        int diff = Integer.MAX_VALUE;

        while (right > left) {

            // this if is throwing the ArrayIndexOutOfBoundsException  
            if (Math.abs(arr[left] + arr[right] - sum) < diff) {
                closestPair[0] = arr[left];
                closestPair[1] = arr[right];
                diff = Math.abs(arr[left] + arr[right] - sum);
            }

            if (arr[left] + arr[right] > sum) {
                right--;
            }
            else {
                left--;
            }

        }
        System.out.println(Arrays.toString(closestPair));
        return closestPair;
    }

    public static void main(String[] args) {
        int [] arr = new int[] {10, 22, 28, 29, 30, 40};
        int[] closestPair = ArrayUtils.closestPairBasedOnSum(arr, 54);
        System.out.println(Arrays.toString(closestPair));
    }
}

Outputs:

java.lang.ArrayIndexOutOfBoundsException: -1

Why is it not returning [22, 30]?

Jongware
  • 22,200
  • 8
  • 54
  • 100
PacificNW_Lover
  • 4,746
  • 31
  • 90
  • 144
  • 1
    *FYI:* "coding puzzle" vs "school assignment" makes no difference. It's an *exercise* you've "chosen" to do, whether that choice is directly voluntary or not. As far as StackOverflow questions go, "school assignment", "exercise", "exam", "test", "puzzle", "interview question", "challenge", etc. is all the same, they are all things that *you* should be completing, to show that you know what you're doing, whether showing others or yourself. – Andreas Mar 24 '20 at 23:33
  • Since you are testing yourself, so should also do as much yourself to try identifying the problem, in particular, you should **debug** the code yourself, instead of asking us to debug it for you. There seems to be no attempt at debugging, so now would be a great time for you to learn / teach yourself how to debug. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) – Andreas Mar 24 '20 at 23:37
  • Edited my post and added a ```diff``` variable for my calculations. – PacificNW_Lover Mar 24 '20 at 23:39
  • 1
    You initialize `left = 0`, then have `left--`, and you're confused that you get `left = -1` causing `ArrayIndexOutOfBoundsException: -1`? --- *Hint:* **Debugging** would have showed you that `left` is `-1`, which is obviously incorrect, so debugging would have lead you straight to that incorrect `left--` bug, without having to ask us. – Andreas Mar 24 '20 at 23:40
  • @Andreas - oh, I read it wrong - thanks! By, the way, I did use the debugger and have unit tests in place. – PacificNW_Lover Mar 24 '20 at 23:44
  • If you'd been debugging properly, you would have seen where the array out of bound error was coming from. Debugging is a skill that should be taught. – NomadMaker Mar 24 '20 at 23:48

1 Answers1

0

Figured out the solution:

 public static int[] closestPairBasedOnSum(int[] arr, int sum) {
    if (arr == null) {
        return null;
    }

    if (sum < 1) {
        return null;
    }

    int[] closestPair = new int[2];

    int left = 0;
    int right = arr.length - 1;
    int diff = Integer.MAX_VALUE;

    while (right > left) {

        if (Math.abs(arr[left] + arr[right] - sum) < diff) {
            closestPair[0] = arr[left];
            closestPair[1] = arr[right];
            diff = Math.abs(arr[left] + arr[right] - sum);
        }

        if (arr[left] + arr[right] > sum) {
            right--;
        }
        else {
            left++;
        }
    }
    System.out.println(Arrays.toString(closestPair));
    return closestPair;
}
PacificNW_Lover
  • 4,746
  • 31
  • 90
  • 144
  • Don't ask questions in an answer. Create a new Question to ask those. – Andreas Mar 25 '20 at 00:00
  • But ask yourself why `[10, 22]` wouldn't be the correct answer for `sum = -10`. It is the closest you can get. --- Ask yourself why `NullPointerException` wouldn't be correct if `arr == null`. --- Ask yourself what the return value should be if `arr.length` is 0 or 1. E.g. why not `IllegalArgumentException`? Right now your code returns `[0, 0]`. *Oops!* – Andreas Mar 25 '20 at 00:04
  • Your code seems to *assume* that the input array is sorted. That has not been specified anywhere. – Andreas Mar 25 '20 at 00:05
  • Andreas - sorry to create a new question inside a question that has been answered... Will create a new question to ask those. Have deleted them from the Answer I provided. Thanks for the implications. – PacificNW_Lover Mar 25 '20 at 00:07