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

[Anm01Chandel]

Sorting the numbers will change the indices of numbers which we need to return. If we keep record of the indices it will be a O(n) space complexity and O(n log n) time which is not good.

Here's a constant space implementation of two sum. Time Complexity is O(n^2) but the solution is much better than brute force. The answer even beats 97% in leetcode (in time)
`

public int[] twoSum(int[] nums, int target) {

    int high = 0, low = Integer.MAX_VALUE;
    int numsSize = nums.length;
    
    for (int a0 = 0; a0 < numsSize; a0++) {
        if (nums[a0] < low) 
            low = nums[a0];
        else if (nums[a0] > high)
            high = nums[a0];
    }
    
    for (int a0 = 0; a0 < numsSize ; a0++) {
        if (nums[a0] + low > target) 
            continue;
        if (nums[a0] + high < target) 
            continue;
        int target2 = target - nums[a0];
        for (int a1 = a0 + 1; a1 < numsSize; a1++) {
            if (nums[a1] == target2) {
                return new int[]{a0, a1};
            }
        }
    }
    return new int[0];
}

`

[Hoopeu]

邮件已收到，我会尽快回复。

[Jiruiyang]

来信收到，谢谢，祝您一切顺利！

[lingbaoer]

您好，您的邮件我已收到！祝工作顺利，天天开心。。。

[JR00010]

这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。