The Two Sum problem is one of the most commonly asked coding questions in interviews
(including Accenture, Infosys, Tech Mahindra, Capgemini, etc.).
✅ Problem: Two Sum - LeetCode #1
Given an array of integers nums and an integer target, return indices of the
two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you
may not use the same element twice.
You can return the answer in any order.
📥 Example:
Input:
nums = [2, 7, 11, 15], target = 9
Output:
[0, 1]
Explanation: nums[0] + nums[1] == 2 + 7 == 9
✅ Java Solution (Using HashMap – O(n) Time Complexity)
java
CopyEdit
import java.util.*;
class TwoSumSolution {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>(); // value →
index
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i}; // return
indices
}
map.put(nums[i], i);
}
// In case there's no solution
return new int[]{-1, -1};
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("Indices: " + Arrays.toString(result));
}
}
🔍 Explanation:
● Use a HashMap to store numbers and their indices as you iterate.
● For each element nums[i], check if (target - nums[i]) already exists in the
map.
● If it does, return both indices.
● This avoids the need for a nested loop, reducing time from O(n²) to O(n).
🧠 Follow-Up (For Interviews):
● Q: What if the array is sorted?
A: Use the Two-pointer approach for O(n) time and O(1) space.
Let me know if you want:
● The brute-force solution (O(n²)),
● A step-by-step dry run, or
● A PDF of this question and solution.
You said:
give detailed explanation and breakdown of each line in the code
ChatGPT said:
Absolutely! Let's go through the Two Sum Java solution line by line, with a clear and
detailed explanation of each part:
✅ Problem Recap:
You are given an array nums and an integer target. You need to find the indices of two
numbers such that they add up to the target.
Example:
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9
✅ Code with Breakdown:
java
CopyEdit
import java.util.*;
● This line imports the Java utility library, which gives us access to classes like
HashMap and Arrays.
java
CopyEdit
class TwoSumSolution {
● This defines a class named TwoSumSolution. Java programs are structured using
classes.
java
CopyEdit
public static int[] twoSum(int[] nums, int target) {
● This defines a method named twoSum.
● public: accessible from anywhere.
● static: can be called without creating an object of the class.
● int[]: the return type is an array of integers.
● Parameters:
○ int[] nums: the input array.
○ int target: the target sum.
java
CopyEdit
Map<Integer, Integer> map = new HashMap<>();
● Creates a HashMap named map to store number → index.
● Integer is used for both key and value.
● Why a map?
○ It helps in constant time lookup (O(1)) to check if the complement (target -
current number) exists.
java
CopyEdit
for (int i = 0; i < nums.length; i++) {
● A for loop that goes through each element of the array using the index i.
java
CopyEdit
int complement = target - nums[i];
● complement is what we need to add to nums[i] to get the target.
● Example: if target = 9 and nums[i] = 2, then complement = 7.
java
CopyEdit
if (map.containsKey(complement)) {
● Check if the complement is already stored in the map.
● If it is, it means we found the two numbers that sum to the target!
java
CopyEdit
return new int[]{map.get(complement), i};
● If found, return the indices of:
○ map.get(complement): index of the first number (complement).
○ i: index of the second number (current number).
● Example: map.get(2) = 0, i = 1, so return [0, 1].
java
CopyEdit
}
map.put(nums[i], i);
● If complement is not found, store the current number and its index in the map.
● This helps us check for it in future iterations.
● Example: map.put(2, 0)
java
CopyEdit
}
return new int[]{-1, -1};
● This line is just a fallback in case no such pair is found (even though the problem
guarantees one).
● Returns [-1, -1] to indicate "not found".
java
CopyEdit
}
public static void main(String[] args) {
● This is the main method. The starting point of any Java program.
java
CopyEdit
int[] nums = {2, 7, 11, 15};
int target = 9;
● Sample input:
○ Array: nums
○ Target value: 9
java
CopyEdit
int[] result = twoSum(nums, target);
● Call the twoSum() method with the input.
● Store the result (indices) in result.
java
CopyEdit
System.out.println("Indices: " + Arrays.toString(result));
● Print the output.
● Arrays.toString(result) converts the array to a readable string like [0, 1].
✅ Output:
makefile
CopyEdit
Indices: [0, 1]
