Given a list of numbers and a number k, return whether any two numbers from the list add up to k

Question

Given a list of numbers and a number \$k\$, return whether any two numbers from the list add up to \$k\$. For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.

How can I improve the solution below?

package com.alpha;

import java.util.HashMap;
import java.util.Map;

public class DailyCodingProblem1 {
    public static void main(String args[]) {
        int[] arr = { 10, 15, 3, 7 };
        int k = 17;

        Boolean ans = solution(arr, k);
        System.out.println(ans);
    }

    private static Boolean solution(int[] arr, int k) {
        final Map<Integer, Boolean> map = new HashMap<>();
        for (int x : arr) {
            map.put(k - x, true);
        }
        for (int x : arr) {
            if (Boolean.TRUE.equals(map.get(Integer.valueOf(x)))) {
                return true;
            }
        }
        return false;
    }
}

Answer 1

Boolean -vs- boolean

Java provides both a Boolean and a boolean type; the difference being the first type is an Object where as the second is just a value. Wherever possible, you should use a value type, for efficiency. Since you return a simple true or false result, boolean is the correct return type to use:

...
    boolean ans = solution(arr, k);
...
private static boolean solution(int[] arr, int k) {
...

Autoboxing

The java Collections need Objects as keys and values. The Java language will automatically "box" and "unbox" values as required. You take advantage of autoboxing in map.put(k-v,true) ... The value k-v is autoboxed as an Integer and true is autoboxed as Boolean.TRUE.

Yet, when you retrieve the value from map, you explicitly do the autoboxing yourself: map.get(Integer.valueOf(x)). You could simply write map.get(x).

Map<K,V> -vs- Set

When you have a Map<K,V>, it is expected that different values will be stored in the map (under one or more keys).

In this case, you are only ever storing Boolean.TRUE (autoboxed from true). Your map.get() either returns Boolean.TRUE, or it returns null if no value was stored under that key. You explicitly test if it is equal to the former value, but you could have tested the value was not null instead. Or more directly, you could test whether a value was stored under that key, and replace the complicated statement with simply:

if (map.containsKey(x)) { ... }

At this point, it should be clear we don't need a HashMap. Simply a Set of Integer values.

final Set<Integer> set = new HashSet<>();
...
   set.add(k-x);
...
   if (set.contains(x)) {
...

Algorithm

As mentioned by hodisr, you need to take into account that the list of numbers may contain only one copy of the value x which is exactly half of the target value (k/2). With your code, you add k-x to your container, and later successfully pull out the flag corresponding to x, and declare true.

Then, hodisr proceeds to demonstrate how to do it in one pass, and goes ahead and repeats the same error, by adding k-x to the container before testing whether x can be pulled out. To obtain the correct result, the check for x must be made before putting k-x into the container.

private static boolean solution(int[] arr, int k) {
    Set<Integer> set = new HashSet<>();

    for (int x : arr) {
        if (set.contains(x))
            return true;
        set.add(k-x);
    }
    return false;
}

Answer 2

Your solution doesn't take into consideration and array that k equals x*2, for example if arr = {10, 17, 3} and k == 20, k - x = 10 and 10 -> true will be placed in map. In the second iteration the value 10 will get you the value true, so you must make sure that you don't iterate over two integers twice.

One way to improve the algorithm is to put the integers in the map but also check if the integer is already in map, if we return to my example while k-v == 3 when v == 17 and k-v == 17 when v == 3, so if you check if the integer is already in the map it could be more efficient and avoid iterating over the array again.

If we go back to your code:

    private static Boolean solution(int[] arr, int k) {
        final Map<Integer, Boolean> map = new HashMap<>();
        for (int x : arr) {
            map.put(k - x, true);
            if (Boolean.TRUE.equals(map.get(Integer.valueOf(x)))) 
                return true;

        }
        return false;}

---

Let me know if you need any other clarifications,

Hod