1
\$\begingroup\$

I am trying to solve this problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

and this is my implementation:

public int[] twoSum(int[] numbers, int target) {
    Map<Integer, Integer> numbersMap = new HashMap<Integer, Integer>();
    int[] requiredNumbers = null;
    int index = 0;
    for (int number : numbers) {
        if (numbersMap.containsKey(target - number)) {
            requiredNumbers = new int[2];
            requiredNumbers[0] = numbersMap.get(target - number);
            requiredNumbers[1] = index;
            return requiredNumbers;
        } else {
            numbersMap.put(number, index);
            index++;
        }
    }
    return requiredNumbers;
}

How can I improve its execution time?

\$\endgroup\$
  • 1
    \$\begingroup\$ you could have used indexed for loop as you are anyway keeping the track of the index \$\endgroup\$ – Ankit Soni Dec 23 '18 at 18:24
0
\$\begingroup\$

If the size of your input array can be large, you can get a speed-up by preallocating the capacity of your HashMap:

Map<Integer, Integer> numbersMap = new HashMap<Integer, Integer>(numbers.length * 2);

As the algorithm runs, data will be added to the HashMap. When number of entries exceeds the capacity * load_factor, the hashmap's capacity is doubled, and the elements are re-binned for the larger capacity. This capacity doubling and rebinning takes time. It doesn't happen often, \$O(\log N)\$ times, but it can be eliminated by starting with a hashmap of sufficient capacity.

The load_factor defaults to 0.75, so an initial capacity larger than numbers.length * 4/3 is required. numbers.length * 2 is a simple expression that satisfies that requirement.

\$\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.