leetcode/hash-table/TwoSum.java

[knasim]

There is a better solution for the TwoSum problem than the hashmap solution. Sure hashmap is fine and meets the desired output. however it can be completely eliminated as such. The techinque employs a pointers to track the argument array i.e. one from the begining aka head and the other one from the end aka tail. A single sweep on the array and adjusting the two pointers does the job rather nicely.

       //input array must be sorted 
       int head =0;  int tail = arr.length -1;  int k = 11;  //target sum to find

        while(head < tail) {
           int sum = arr[head] + arr[tail];
           if(sum == k)  return true; //found it !!
           else if(sum < k) ++head;
           else --tail; 
        }

[kdn251]

This assumes that the array is sorted which is not the case. Therefore this adds an overhead of O(nlogn) to sort which is slower than O(n)

[knasim]

right but the hashmap increases use of space. shouldn't we consider the net effect ?

[IAmPramod]

@knasim Even if we go best sorting algorithm(merge/quick/tree), It will have time complexity O(nlogn) with worst space complexity O(n).

Using hashmap, we solve this in O(n) time with space O(n) even if all the elements are distinct in the array.

[sragha45]

@IAmPramod , I reckon hashmap is implemented using Red-Black trees, so the average lookup time for a huge N becomes log N. So for N elements it again comes to O(N log N)

[IAmPramod]

@sragha45 Yes, you are correct. But O(NlogN) is the worst case scenario when we have a very poor implementation of hash code which will map all entries to same bucket.

Have a look at the performance of hashmap in average case. https://dzone.com/articles/hashmap-performance

[vin0010]

May be this is not completely related to the discussion. But with hash map and tuple together, we can solve this problem easily.

def get_count_map(nums):
        count_map = dict()
        for i in range(0, len(nums)):
            if nums[i] in count_map:
                temp = count_map[nums[i]]
                temp[1].append(i)
                temp = (temp[0]+1, temp[1])
                count_map[nums[i]] = temp
            else:
                count_map[nums[i]] = (1, [i])
        return count_map


    def print_indices(count_map, k):
        for i in count_map:
            if 2*i == k:
                return [count_map[i][1][0], count_map[i][1][1]]
                break
            else:
                if k-i in count_map:
                    return [count_map[i][1][0], count_map[k-i][1][0]]
                    break

https://github.com/vin0010/Competitve-Programming/blob/master/python/leetcode/TwoSum.py