🧠 Two Sum Problem – Python Solution

Hi All,

Today I solved a popular problem from LeetCode called Two Sum.

---

📌 Problem Statement

Given an array of integers nums and an integer target, return the indices of two numbers such that they add up to the target.

Conditions:

• Each input has exactly one solution
• You cannot use the same element twice
• You can return the answer in any order

---

💡 Approach

🔹 Brute Force (Not efficient)

• Check every pair using two loops
• Time Complexity: O(n²)

🔹 Optimized Approach (Used)

• Use a dictionary (hash map)
• Store number and its index
• For each element:
  • Find target - current number
  • Check if it exists in dictionary

👉 This reduces time complexity to O(n)

---

💻 Python Code

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

        for i in range(len(nums)):
            complement = target - nums[i]

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

            num_map[nums[i]] = i

---

🔍 Example Walkthrough

Input:

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

Steps:

• i = 0 → num = 2 → complement = 7 → not found → store {2:0}
• i = 1 → num = 7 → complement = 2 → found

Output:

[0, 1]

---

🖥️ Sample Outputs

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

---

🧠 Explanation

• num_map stores values and their indices
• For each number:
  • Compute complement = target - num
  • Check if complement exists
• If yes → return indices
• Else → store current number

---

⚡ Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

---

✅ Conclusion

This problem helped me understand:

• Efficient searching using hash maps
• Reducing time complexity from O(n²) to O(n)
• Writing optimized and clean code

🚀 This is a very important problem for coding interviews!

---