Q-1 LeetCode: Two Sum — Efficient Algorithm Using HashMap and Two-Pointers in Java
3 min readNov 19, 2023
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
- Initialize an empty
HashMap
to store numbers from the array and their corresponding indices. - Use two pointers,
i
andj
, initially pointing to the start and end of the array. - In each iteration of the loop, check if the complement of the current number (
target - nums[i]
ortarget - nums[j]
) is already in theHashMap
. If it is, return the indices of the two numbers. - If the complement is not found, add the current number and its index to the
HashMap
. - Move the pointers (
i
andj
) towards the center of the array untili
is greater thanj
. - 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:
- Iteration 1 (i = 0, j = n-1):
- Check ifmap
contains the complement ofnums[0]
(i.e.,target - nums[0]
). If not, addnums[0]
and its index (0
) to themap
.
- Move pointers:i
becomes1
, andj
becomesn-2
. - Iteration 2 (i = 1, j = n-2):
- Check ifmap
contains the complement ofnums[1]
. If not, addnums[1]
and its index (1
) to themap
.
- Move pointers:i
becomes2
, andj
becomesn-3
. - Iteration 3 (i = 2, j = n-3):
- Check ifmap
contains the complement ofnums[2]
. If not, addnums[2]
and its index (2
) to themap
.
- Continue this process, moving pointers towards the center. - Solution Found (i = x, j = y):
- At some point, the complement of a number is found in themap
. Return the indices of the two numbers. - No Solution Found (i>j):
- If no solution is found during the iteration, return[0, 0]
as a placeholder.
Resources
- LeetCode Q-1 Solution: https://github.com/Neelesh-Janga/Java-Programs/tree/main/0001-linked-list-cycle
- 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
- LinkedIn — https://www.linkedin.com/in/neelesh-janga/
- GitHub — https://github.com/Neelesh-Janga