Two Sum Problem

Two Sum

My Thinking and Approach

---

Introduction

In this problem, I was given an array of integers and asked to find two numbers such that their sum equals a given target.

This problem is simple but important for understanding optimization techniques.

---

Problem Statement

• Given an array of integers nums
• Given an integer target
• Return indices of two numbers such that:

nums[i] + nums[j] = target

• Conditions:

  • Only one valid solution exists
  • Cannot use the same element twice
  • Return indices in any order

---

My Initial Thought

At first, I considered:

• Using two loops
• Checking all possible pairs

But this approach takes more time and is not efficient.

---

Key Observation

Instead of checking all pairs:

• For each number, I can calculate the complement
• Complement = target - current number

If the complement already exists, I found the answer.

---

Optimized Approach

I decided to:

• Use a dictionary (hashmap)
• Store numbers and their indices
• Check for complement while traversing

Logic:

• If complement exists → return indices
• Else → store the current number

---

My Approach (Step-by-Step)

1. Create an empty dictionary num_map
2. Traverse the list using index
3. For each number:

• Find complement = target - num
• If complement exists in dictionary → return indices
• Else → store number in dictionary

---

Code (Python)

Below is the implementation clearly separated inside a code block:

def twoSum(nums, target):
    num_map = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in num_map:
            return [num_map[complement], i]

        num_map[num] = i

---

Example Walkthrough

Input:

nums = [2, 7, 11, 15], target = 9

Steps:

• Index 0 → number = 2 → complement = 7 → not found → store
• Index 1 → number = 7 → complement = 2 → found

Output:

[0, 1]

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

---

Key Takeaways

• Brute force approach is not efficient
• Hashmap helps in faster lookup
• Complement concept is important

---

Conclusion

This problem helped me understand how to optimize a solution using a dictionary.

Instead of checking all pairs, I used a smarter approach to reduce time complexity.

---