Day 1 of solving LeetCode problems to prepare for FAANG/MAANG interviews.

The Two Sum problem is arguably the most famous introductory question in competitive programming. It’s simple to understand but demands an elegant solution for efficiency. Mastering this problem—and its complexity trade-offs—is essential for any aspiring software engineer targeting top tech companies like FAANG or MAANG.

Here’s a complete breakdown of the problem, its constraints, and the two primary methods to solve it.

---

🎯 Understanding the Goal

Given an array of integers (nums) and a specific integer (target), the challenge is to find two distinct numbers within the array that add up to the target.

The Crucial Output

We don’t return the numbers themselves; we must return the indices (positions) of those two numbers within the original array.

Example:

• nums = [2, 7, 11, 15]
• target = 9
• Solution: 2 + 7 = 9. Since 2 is at index 0 and 7 is at index 1, the required output is [0, 1].

---

📝 Key Constraints to Remember

1. Exactly One Solution: You are guaranteed that a unique pair exists. This means you can stop searching immediately upon finding the first match.
2. No Same Element Twice (Unique Indices): You cannot reuse the element at the same index. If you have duplicates (e.g., two 3s), you can use them both because they are at different indices.
3. Inputs: nums (array of integers) and target (the required sum).

---

1. The Brute-Force Approach (The Slow Way 🐢)

The simplest way to solve this is to try every combination.

Concept: Nested Loops

The brute-force solution relies on two nested loops to check every possible pair:

1. The outer loop (i) picks the first number.
2. The inner loop (j) picks the second number, ensuring it starts after i (i.e., j = i + 1) to avoid checking the same pair twice or using the same element twice.
3. If nums[i] + nums[j] equals the target, you return the indices [i, j].

Code Example (Python)

Python

def twoSumBruteForce(nums, target):
    n = len(nums)
    for i in range(n):
        # Inner loop starts one position after i
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]

Complexity Analysis

• Time Complexity: O(n^2) (Quadratic). For an array of size n, the loops run approximately n^2 times. This is inefficient for large datasets.
• Space Complexity: O(1). We only use a few constant variables.

---

2. The Optimized Approach (The Fast Way 🚀)

To avoid the O(n^2) time trap, we can use a Hash Map (or Dictionary in Python) to achieve a linear time solution.

Concept: One-Pass Hash Map

Instead of searching for the second number, we calculate what the second number must be and check if we’ve seen it before.

1. As we iterate through the array, we calculate the complement :
   • complement = target -current_number
2. We check our Hash Map to see if this complement already exists.
   • If it exists: We have found the solution! We return the index stored in the map (the complement’s index) and the current index.
   • If it doesn’t exist: We store the current number and its index in the map for future checks.

This approach ensures that we visit each element only once, cutting the search time dramatically.

Code Example (Python)

Python

def twoSumOptimized(nums, target):
    # Map stores {number: index}
    num_map = {} 
    
    for i, num in enumerate(nums):
        complement = target - num
        
        # Check step: O(1) time
        if complement in num_map:
            # Solution found!
            return [num_map[complement], i]
        
        # Store step: O(1) time
        num_map[num] = i

Complexity Analysis

• Time Complexity: O(n) (Linear). We pass through the list once, and lookups/insertions in a Hash Map are virtually constant time O(1). This is optimal.
• Space Complexity: O(n). We use extra space proportional to the size of the input array to store elements in the hash map.

The O(n) solution is the required and preferred standard for interview settings. It demonstrates a strong grasp of data structures and complexity analysis!