01-Two-Sum.md

Two Sum

Problem Link

https://leetcode.com/problems/two-sum/

---

Pattern

• Hashing
• Array

---

Approach

Use a hashmap to store previously seen numbers and their indices. For each number check if target - num exists in map; if yes return indices.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int diff = target - nums[i];

            if (map.containsKey(diff)) {
                return new int[]{map.get(diff), i};
            }

            map.put(nums[i], i);
        }

        return new int[]{};
    }
}

---

Explanation

• We scan once and use hashing for O(1) lookups. This returns the first valid pair.
• Edge cases: assume exactly one solution exists as per problem statement; handle duplicates correctly because map stores the earliest index.