Two sum problem implementation with Hashtable

Question

Problem statement:

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1]

I have a working Java implementation with both time and space complexity of \$O(n)\$. However, I am looking for feedbacks on how to write better, more elegant code. Any suggestions on style, simplicity, comments, etc., are welcome.

Note: function signature is provided to me in the interview, not mine. Otherwise I would return a Pair instead of int[].

import java.util.Hashtable; 

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int loadFactor = 3;
        //key: num, value: num's parter's idx, if exists 
        Hashtable<Integer, Integer> parterIdxHash = new Hashtable<Integer, Integer>(loadFactor*nums.length);
        for(int i = 0; i < nums.length; i++){
            int curVal = nums[i];
            Integer parterIdx = parterIdxHash.get(curVal);

            //found its parter 
            if(parterIdx != null)
                return new int[]{parterIdx, i}; //parterIdx first because it's eariler in the array

            int parterVal = target - curVal;
            parterIdxHash.put(parterVal, i);

        }

        //should never reach here!
        return new int[]{-1, -1};            
    }
}

Answer 1

Interesting solution for the problem. My first question as interviewer to you would be: are you sure it's O(n) time complexity? The worst case for hash lookup is O(n) so doesn't that make your total time complexity O(n²)?

Hint to answer this: when does that worst case occur, and why is this no problem for you? (Given how you initialised the map in your code you probably don't even need this hint to answer it correctly though).

---

You don't check your input values. What happens if nums is null? I'm not saying your solution is wrong, but this should usually be a consious decission. Your current choice is that the user of this method is responsible for passing non-null arguments or that we should start the fun journey of debugging where that NPE comes from.

The same reasoning goes for the target value. What if it's an impossible sum? Take for example the input nums = [2,3] and target=4. I partially like that you return an int[] result with negative indices instead of throwing an error. But the comment documenting it feels wrong.

I would have prefered that you would have handled it like an actual valid case and added a javadoc on top of the method that states that passing an impossible target results in [-1,-1].

Since you handle an impossible target that way, you could also choose to handle a null input for nums the same way. Add it to the javadoc and start your method with this simple check

if(nums == null){
    return new int[]{-1, -1};
}

Alternatively you can also throw explicit errors to force users to handle edge cases correctly.

It's generally better during an interview if you make those choices explicit. There's no real wrong choice, as long as you can tell why you picked a specific one. (A possible answer is: it's the easiest to implement, which to chooce often depends on what the method is for and how the company usually handles edge cases).

---

Why do you want an O(n) space and time complexity? Wouldn't it be better to use O(1) space at the cost of O(n²) time if the implementation is easier?

For example:

private int[] twoSum(int[] nums, int target){
    if(nums == null) {
        return new int[]{-1, -1};
    }
    for (int i = 0; i < nums.length - 2; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if(nums[i]+nums[j]==target){
                return new int[]{i,j};
            }
        }
    }
    return new int[]{-1, -1};
}

Using this approach, you could ask the interviewer if the array is sorted. If it is you can replace the inner for loop with a search of the target in the remaining array. This turns the total time complexity into O(n*log(n)) instead.

Note that I wouldn't immediatly implement this for the interview. I would mention that these kind of optimisations are useful and possible, but that I would only do them after profiling shows these are the methods that take most time.

If it's a method that is only used a couple times per hour and on relatively small inputs then it's not worth putting in effort to optimise the implementation. If it's a major function that runs millions of times per hour then it's worth optimising the hell out of it, even going as far as bit-trickery if wanted.

---

parter isn't the right word in this context. I'm assuming you meant partNer. Typos happen and not being native english myself I too make spelling mistakes. But this one is repeated too often to ignore in your piece of code.

---

You mention that you would have prefered to return a Pair. What would you do if we also wanted the methods threeSum fourSum or a general nSum?

---

In this example it doesn't matter too much, but it's best practice if you code against the interface, not the implementation. More specifically this line of code:

Hashtable<Integer, Integer> parterIdxHash = new Hashtable<Integer, Integer>(loadFactor*nums.length);

should have been:

Map<Integer, Integer> partnerIndices = new Hashtable<>(loadFactor*nums.lenth);

Since you didn't do this in your little example solution, the interviewer might conclude that you never do this. For local variables it doesn't change that much, but if you also use concrete classes as return types or as parameter inputs you violate the encapsulation principle.

---

It's also good practice to always put curly braces after each for/if/while/... statement. With maybe an exception when putting the entire statement on the same line for reasons explained here

---

As a final note I would like to emphasize that with interview solutions it's more important that you can tell what your solution is good at, what can still be improved and that your coding style is consistent. With this in mind you can always implement the easiest solution and tell the interviewer what the alternatives are without actually having to write them correctly.