[Java] Hash table implementation: (Accepted Solution)


  • 1
    P

    Hi. Here's my solution for the Two Sum problem using a Hash table.
    Adding each element to the Hash table takes linear time (O(n)). I store each element in the array as the key and its position as the value. The idea is to find the key value (target - index1) if it's not null (it exists), then index2 is the value of that key. Each lookup takes constant time (O(1)) and in the worst case, it'll run n times.
    Any comments or improvements are welcome.
    Cheers.

    import java.util.Hashtable;
        
        public class Solution {
            public int[] twoSum(int[] numbers, int target) {
                int[] solution = new int[2];
        		Hashtable<Integer, Integer> H = new Hashtable<Integer,Integer> (numbers.length);
        		
        		// O(n) time for adding each element to the Hash table.
        		for(int i=0; i<numbers.length; i++) {
        			H.put(numbers[i], i);
        		}
        		
        		// Lookup for element index2 such that index2==(target-index1) (O(1)) 
        		// O(1) for each lookup, O(n) total.
        		for(int i=0; i<numbers.length; i++) {
        			if(H.get(target-numbers[i]) != null && H.get(target-numbers[i])!=i) {
        				solution[0] = i+1;
        				solution[1] = H.get(target - numbers[i]) +1;
        				break;
        			}
        			else continue;
        		}
        		return solution;
        	}
        }

  • 1
    Z

    Do you assume the numbers are distinct? What if
    numbers={3, 3, 10}, target=6


  • 0
    P

    It would still work. Hashtable has a way to handle hash collisions (with a linked list).
    Very interesting question, thanks for commenting.


  • 0
    Z

    Yes, you are right. The hash table will contain the index of the latter 3 so that when i == 0, H.get(target-numbers[i])!=i could be true.


  • 2
    S

    HashSet would be better choice to optimise space consumption for large input datasets.

    I solved same problem using HashSet. After finding matching numbers, I used an extra linear scan of input array, in order to determine the index of found matches.

    So, in my solution the memory occupied will be half compared to your solution at the cost of one extra linear scan of input array.


  • 0
    P

    Awesome improvement, would you mind adding your diff?


  • 0
    D
    This post is deleted!

  • 0
    D

    Here is my accepted implementation

    public class Solution {

    public int[] twoSum(int[] numbers, int target) {
        if(numbers==null){
            return null;
        }
        HashMap<Integer, ArrayList<Integer>> originalPosition= new HashMap<Integer,ArrayList<Integer>>();
        for(int k=0;k<numbers.length;k++){
            ArrayList<Integer> indexes= originalPosition.get(numbers[k]);
            if(indexes==null){
                indexes=new ArrayList<Integer>();
            }
            indexes.add(k+1);
            originalPosition.put(numbers[k],indexes);
        }
        int[] result= new int[2];
        int i=0, j=numbers.length-1;
        //sort the list
        Arrays.sort(numbers);
        while(i<j){
            int sum=numbers[i]+numbers[j];
            if(sum==target){
                ArrayList<Integer> indexesI =  originalPosition.get(numbers[i]);
                ArrayList<Integer> indexesJ =  originalPosition.get(numbers[j]);
                if(indexesI.get(0)<indexesJ.get(0)){
                    result[0]=indexesI.get(0);
                    result[1]=indexesJ.get(indexesJ.size()-1);
                }
                else{
                    result[0]=indexesJ.get(0);
                    result[1]=indexesI.get(indexesJ.size()-1);
                }
                
                
                
                break;
            }
            if(sum<target){
                i++;
            }
            if(sum>target){
                j--;
            }
        }
    if(i==j){
        return null;
    }
        return result;
    }
    

    }


  • 12
    J

    What about this accepted solution ?
    Clean and simple.

    public int[] twoSum(int[] numbers, int target) {
            Map<Integer, Integer> map = new HashMap<Integer,Integer>();
            for(int i = 0; i < numbers.length; i++) {
                Integer index1 = map.get(target-numbers[i]);
                if (index1 != null) {
                    return new int[]{index1,i+1};
                }
                map.put(numbers[i], i+1);
            }
            return null;
    }

  • 0
    M
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.