Pair Sums in Java

!!! UPDATE UPDATE UPDATE !!! An issue was found in the implementation of the function of interest. The issue has been addressed. The code in the GitHub repository has been updated. Thanks to Mario Rincon Nigro.

Good day to all of you. I believe this is my first post for 2021. That said hope you had a nice holiday season. It seems that COVID-19 vaccinations have been started. Hopefully we will be able to put politics aside and move forward quickly vaccinating all people who are interested in getting the shots. My wife will be checking with our doctor to figure out if we can get on a schedule to get it done in the near future. We know of several people in our families and friends that have already received the first shot. It seems that for them so far so good. Will let you know how it goes after the second one.

We are already in January and the United States presidential inauguration is approaching quickly. That said; the winner of the election is still undetermined. Apparently there has been a lot of fraud committed by one of the political parties. If this is case democracy is out the door in the USA. Hopefully all will be resolved in a friendly manner and the people (if any) that committed fraud will be made accountable.

OK, enough chitchat and let’s get into the main subject for this post.

I decided to give Pair Sums a try. This is a coding practice questions by Facebook. The problem is similar, yet different, to the Two Sum problem that I tackled before and for which we have a post in this blog.

Given a list of n integers arr[0..(n-1)], 
determine the number of different pairs of elements within it which sum to k.

If an integer appears in the list multiple times, each copy is considered to be different; 
that is, two pairs are considered different if one pair includes at least one array index which the other doesn't, 
even if they include the same values.

Input:

n is in the range [1, 100,000].
Each value arr[i] is in the range [1, 1,000,000,000].
k is in the range [1, 1,000,000,000].

Output:

Return the number of different pairs of elements which sum to k.

We are given an array of integers. The integers appear to be positive as illustrated by the input constraints. We need to return the number of pairs that can be found in the array that add up to the specified value.

As you might already know, I like to solve the problems in my computers. For this problem I will use Java, a Windows 10 computer and the VSCode IDE. When done I will copy my solution and check if it passes the unit testing.

int numberOfWays(int[] arr, int k)

Because of my approach, I will need to write my own test scaffolding. If you are planning on applying to Facebook, I would suggest developing the code using the Facebook portal.

1,2,3,4,3
6
main <<<    arr: [1, 2, 3, 4, 3]
main <<<      k: 6
main <<< output: 2


1,5,3,3,3
6
main <<<    arr: [1, 5, 3, 3, 3]
main <<<      k: 6
main <<< output: 4


8, 8, 4, 2
6
main <<<    arr: [8, 8, 4, 2]
main <<<      k: 6
main <<< output: 1

The first input line contains the test numbers we will use for the array. The second line contains the number that the two integers should add up to. In the first example, 2 + 4 = 6 would count for one solution. Another would be 3 + 3 = 6. It seems we have two possible sets of numbers. Our test code appears to read the two set of numbers and then display them. It seems that part is working. The code should then be invoking the function of interest and displaying the result. The results seem to match.

    /**
     * Test scaffolding
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read array of strings ****
        String[] strArr = br.readLine()
                            .trim()
                            .split(",");

        // **** read k ****
        int k = Integer.parseInt(br.readLine().trim());

        // **** close buffered reder ****
        br.close();

        // **** populate int[] arr ****
        int[] arr = Arrays.stream(strArr)
                            .map(x -> x.trim())
                            .mapToInt(Integer::parseInt)
                            .toArray();
        
        // ???? ????
        System.out.println("main <<<    arr: " + Arrays.toString(arr));
        System.out.println("main <<<      k: " + k);

        // **** compute and display result ****
        System.out.println("main <<< output: " + numberOfWays(arr, k));
    }

The test code seems to work as was described above. We read the values and populate with them an array and a variable which are then used as arguments to the function / method we need to code. The result is then displayed.

Like I mentioned before, this code IS NOT PART OF THE SOLUTION.

    /**
     * Given a list of n integers arr[0..(n-1)], determine the number of different
     * pairs of elements within it which sum to k.
     */
    static int numberOfWays(int[] arr, int k) {

        // **** initialization ****
        int pairs                               = 0;
        HashMap<Integer, List<Integer>> valLoc  = new HashMap<>();
        List<Integer> locs                      = null;

        // **** populate hashmap of value : location O(n) ****
        for (var i = 0; i < arr.length; i++) {
            
            // **** get locations for this value ****
            locs = valLoc.get(arr[i]);
            if (locs == null) {
                locs = new ArrayList<Integer>();
                locs.add(i);
                valLoc.put(arr[i], locs);
            } else {
                locs.add(i);
            }
        }

        // ???? ????
        // System.out.println("numberOfWays <<< valLoc: " + valLoc.toString());

        // **** count pairs (pairs will be double counted) ****
        for (var i = 0; i < arr.length; i++) {

            // **** skip this value (if needed) ****
            if (arr[i] > k) continue;

            // **** compute the needed value ****
            var val = k - arr[i];

            // **** look up the value in the hashmap O(n) ****
            locs = valLoc.get(val);
            if (locs != null) {

                // **** double count pairs (a,b) & (b,a) ****
                pairs += locs.size();

                // **** decrement count (a,a) ****
                if (val == arr[i]) pairs--;

                // ???? ????
                // System.out.println("numberOfWays <<< pairs: " + pairs);
            }
        }

        // **** pairs were double counted ****
        return pairs / 2;
    }

The approach is to populate a hash map with the values in the array and their location. We need to make sure we do not count the same pair twice. We can determine that by storing for each value the location in the array.

By selecting a HashMap we have to deal with the issue that we cannot have two or more entries associated with the same key. In the first array number 3 is found at locations 2 and 4. In the second example, we have number 3 in locations 2, 3 and 4. Third party libraries support hash maps with repeated keys. The standard Java libraries do not.

We start by performing sanity checks. Not sure if much time is saved, but there it is.

We initialize three variables. The pairs variable will be used to count the number of pairs we find. Note that 2 + 4 == 4 + 2, so we need to keep that in mind. In addition in the second example, if the result is equal to the sum, we should not count 3 + 3 == 6 twice. Will look at how we deal with the condition in a few.

The valLoc hash map is used to keep track of the values and locations in the array. We could skip this but we would like to process the array in O(n) time.

Finally the locs list will be used to keep track of the different locations a value may have. In the first test case number 3 has two locations. In the second case number 3 has three locations.

We then populate the hash map. If you wish to see the contents of the hash map, I have commented out the line that displays its contents.

Now we enter a second loop. Since this loop is sequential and also traverses the values once, our algorithm runs in O(n) time. The space complexity is also O(n) because each array entry is associated with a hash map entry.

The second loop traverses all positions once. We compute the val which represents the value we need to locate to add to arr[i] to get to the value of the k argument. In both examples k is set to 6.

Now that we have computed val (we can also display it) we check if we can find it in our hash map in O(1). If not present we need to skip the arr[i] value and move on to the next array entry. Otherwise we increment the number of pairs. Note that as we move forward we will be counting the same pair twice. That is dealt with after the loop. At this point in the loop we need to deal when the value in arr[i] matches the sum. We should not use the same value in the array twice

After the loop we return the number of pairs divided by 2 in order to eliminate the double counting we encounter in the loop.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 5,425 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com