Java: Two Sum

Thought Process

To solve the Two Sum problem, we use a hash map to store numbers and their indices as we iterate through the array. For each number, we calculate its complement i.e target - nums[i]. If the complement exists in the map, we return the current index and the stored index. Otherwise, we store the current number and its index in the map. 

class Solution {
    public int[] twoSum(int[] nums, int target) {
          
        int[] ans = new int[2];
        Map<Integer,Integer> mp = new HashMap<>();
        for(int i=0;i<nums.length;i++){
  
            int complement = target - nums[i];
            if(mp.containsKey(complement)){
                ans[0] = i;
                ans[1] = mp.get(complement);
            }
            else{
                mp.put(nums[i],i);
            }
        }
        return ans;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once, and each lookup/insert operation in the map is O(1) on average.

Space Complexity: O(n)

The map stores at most n key-value pairs, where 'n' is the size of the input array.

Code copied!