Q-1 LeetCode: Two Sum — Efficient Algorithm Using HashMap and Two-Pointers in Java

Given an array of integers nums and an integer target, find and return the indices of two numbers in the array that add up to the target. It is guaranteed that there is exactly one solution, and each element in the array can only be used once.

Examples:
1. Input: nums = [2,7,11,15], target = 9
   Output: [0,1]
   Explanation: nums[0] + nums[1] == 9, so the indices are [0, 1].

2. Input: nums = [3,2,4], target = 6
   Output: [1,2]

3. Input: nums = [3,3], target = 6
   Output: [0,1]

Constraints:
1. 2 <= nums.length <= 10^4
2. -10^9 <= nums[i] <= 10^9
3. -10^9 <= target <= 10^9
4. Only one valid answer exists.

Follow-up: Can you devise an algorithm with time complexity less than O(n²)?

Complexity Analysis

• Time Complexity: O(n)
  - Runtime: 0 ms (Beats 100% of Java submissions in LeetCode)
• Space Complexity: O(n)
  - Memory Consumed: 43.9 MB

Code

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

Algorithm Overview

1. Initialize an empty HashMap to store numbers from the array and their corresponding indices.
2. Use two pointers, i and j, initially pointing to the start and end of the array.
3. In each iteration of the loop, check if the complement of the current number (target - nums[i] or target - nums[j]) is already in the HashMap. If it is, return the indices of the two numbers.
4. If the complement is not found, add the current number and its index to the HashMap.
5. Move the pointers (i and j) towards the center of the array until i is greater than j.
6. If no solution is found during the iteration, return an array [0, 0] as a placeholder.

Step-by-Step Execution

— Initialization:

• Create an empty HashMap (map) to store numbers and indices.

— Loop Iterations:

1. Iteration 1 (i = 0, j = n-1):
   - Check if map contains the complement of nums[0] (i.e., target - nums[0]). If not, add nums[0] and its index (0) to the map.
   - Move pointers: i becomes 1, and j becomes n-2.
2. Iteration 2 (i = 1, j = n-2):
   - Check if map contains the complement of nums[1]. If not, add nums[1] and its index (1) to the map.
   - Move pointers: i becomes 2, and j becomes n-3.
3. Iteration 3 (i = 2, j = n-3):
   - Check if map contains the complement of nums[2]. If not, add nums[2] and its index (2) to the map.
   - Continue this process, moving pointers towards the center.
4. Solution Found (i = x, j = y):
   - At some point, the complement of a number is found in the map. Return the indices of the two numbers.
5. No Solution Found (i>j):
   - If no solution is found during the iteration, return [0, 0] as a placeholder.

Resources

1. LeetCode Q-1 Solution: https://github.com/Neelesh-Janga/Java-Programs/tree/main/0001-linked-list-cycle
2. Good news, I took an initiative of writing 1 coding question per day for 365 days in an easy and beginner-friendly standard yet efficient. Refer this repository for more: https://github.com/Neelesh-Janga/Java-Programs

Social Accounts

1. LinkedIn — https://www.linkedin.com/in/neelesh-janga/
2. GitHub — https://github.com/Neelesh-Janga