Arrays & Hashing

Two Sum

Problem Information

Leetcode problem: https://leetcode.com/problems/two-sum/description/
Neetcode problem: https://neetcode.io/problems/two-integer-sum
Difficulty: Easy

Solution

The optimal solution is to use a map that has as key the values of the array nums and as values the positions in the array.

We then iterate the nums array and check if there is an element in the map that has as key target - n and is different that the position of the element n. If so, then return the position of n along with the value of the numsMap found.

Time Complexity: O(n)
Space Complexity: O(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // The key is the value of num[i], while the value
        // is i.
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
                map.put(nums[i], i);
        }

        for (int i = 0; i < nums.length; i++) {
            int difference = target - nums[i];

            if (map.containsKey(difference) && map.get(difference) != i) {
                return new int[]{i, map.get(difference)};
            }
        }

        return new int[]{-0, -0};
    }
}