LeetCode Easy: Two Sum

Simple single pass O(n) solution to the Two Sum problem of LeetCode (https://leetcode.com/problems/two-sum/):

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hm = new HashMap<>();
        
        
        for (int i=0; i<nums.length; i++) {
            if (hm.get(target - nums[i]) != null) {
                return (new int[]{hm.get(target - nums[i]), i});
            }
            hm.put(nums[i], i);
        }
        
        //never occours for appropriate inputs
        return new int[2];
    }
}

 

One can also solve the same by keeping two-pointers at the boundaries of the sorted version of the input array and either reducing the larger index inwards if the sum needed is lesser than the sum of the elements at the pointed indexes or incrementing the lower pointer index if the sum needed is larger than that of the current elements under the pointers, all while lesser pointed index <larger pointed index. If the input array is sorted, this will definitely be an optimization to the aformentioned O(n) solution! Otherwise, the sort will bottleneck the performance of this solution to O(n lg n).

 

Do share better ideas for solving this, that cross your mind!

 

Cheers!!

<3