Two Sum

   

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 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Ans- most optimised way is to use Hashmap .

import java.util.HashMap;

class Solution {
 public int[] twoSum(int[] nums, int target) {
 // HashMap to store the number and its index
 HashMap<Integer, Integer> map = new HashMap<>();

// Traverse the array once (O(n) time complexity)
 for (int i = 0; i < nums.length; i++) {
 int complement = target — nums[i]; // The number needed to reach the target
 
 // Check if complement exists in the HashMap
 if (map.containsKey(complement)) {
 return new int[] { map.get(complement), i }; // Return indices of the two numbers
 }

// Store the current number with its index
 map.put(nums[i], i);
 }

// Edge case: If no solution found (shouldn’t happen as per problem constraints)
 throw new IllegalArgumentException(“No two sum solution”);
 }
}

Time & Space Complexity

Approach	Time Complexity	Space Complexity
Brute Force (Nested Loop)	O(n²)	O(1)
Sorting + Two Pointers	O(n log n)	O(1)
HashMap (Your Code)	O(n)	O(n)

Brute Force (Nested Loop)---->

class Solution {

    public int[] twoSum(int[] nums, int target) {

        int n = nums.length;

        // Try every pair (O(n²) time complexity)

        for (int i = 0; i < n; i++) {

            for (int j = i + 1; j < n; j++) {

                // Check if the sum equals the target

                if (nums[i] + nums[j] == target) {

                    return new int[] {i, j};

                }

            }

        }

        // If no solution is found (shouldn't happen as per problem constraints)

        throw new IllegalArgumentException("No two sum solution");

    }

}

🛑 Common Interview Follow-Up Questions

📌 Q1: What’s the time complexity of your solution?
👉 O(n) since we traverse the array once and each map.containsKey() lookup is O(1) on average.

📌 Q2: Can you optimize space?
👉 Yes! We can use Sorting + Two Pointers (O(1) space, O(n log n) time), but sorting changes the original order.

📌 Q3: What if there are multiple solutions?
👉 The question asks for one valid solution. If multiple exist, this code returns the first one found.

📌 Q4: What if no solution exists?
👉 Instead of returning null, we throw an exception (IllegalArgumentException), which is a good practice in Java.