LeetCode Solution: 1. Two Sum

1. Two Sum 🟢 Easy: Your First Step into LeetCode Magic!

2. Problem Explanation: The Quest for the Perfect Pair

Imagine you have a list of numbers, like [2, 7, 11, 15]. Your goal is to find two numbers from this list that, when added together, equal a specific target number, say 9.

Sounds simple, right? But there's a catch! You don't just return the numbers themselves, you need to return their positions (or indices) in the original list.

Let's look at our example: nums = [2, 7, 11, 15], target = 9.

• If we take 2 (at index 0) and 7 (at index 1), their sum is 2 + 7 = 9. Bingo!
• So, our answer would be [0, 1].

A few important rules:

• Exactly one solution: You're guaranteed to find one pair that works. No need to worry about multiple pairs or no pairs at all.
• No duplicates: You can't use the same number twice. If nums = [3, 3] and target = 6, you use the 3 at index 0 and the 3 at index 1. You can't use the 3 at index 0 with itself.
• Order doesn't matter: [0, 1] is the same as [1, 0].

This problem, "Two Sum," is often the very first problem people encounter on coding platforms like LeetCode. It's a fantastic way to start building your algorithmic thinking!

3. Intuition: From Brute Force to Brilliant!

When faced with a problem like this, the first thought for many beginners (and even seasoned pros!) is often: "How can I check every single possibility?"

The "Brute Force" Idea (and why we want something better):
You could pick the first number, then go through all the other numbers to see if any of them add up to the target. Then pick the second number, and again, check all subsequent numbers. This looks like nested loops:

For each number 'num1' in the array:
    For each *other* number 'num2' in the array (that hasn't been checked with num1):
        If num1 + num2 == target:
            Return their indices!

This approach works! But imagine our list nums has 10,000 numbers. The outer loop runs 10,000 times, and the inner loop also runs nearly 10,000 times for each outer loop iteration. That's roughly 10,000 * 10,000 = 100,000,000 operations! That's a lot, and for larger lists, it becomes too slow. We call this a O(n^2) (read as "O of n squared") solution, and we can do better!

The "Aha!" Moment: What are we really looking for?

Let's say we pick a number num. If we want num + another_num = target, then another_num must be equal to target - num.

So, for every num we encounter, we're not just looking for any other number. We're looking for a very specific complement number: target - num.

If we could quickly ask, "Hey, have I seen complement before, and if so, where was it?", we could solve this much faster! This is where the magic of a Hash Map (or unordered_map in C++ and dictionary in Python) comes in.

4. Approach: Leveraging the Power of Hash Maps

A hash map is like a super-fast dictionary. You give it a key (like a word), and it immediately tells you its value (like the definition), or if it hasn't seen that key before. This "immediate" lookup usually takes constant time, O(1), which is incredibly efficient!

Here's how we can use a hash map to solve Two Sum in a single pass:

1. Initialize an empty hash map: This map will store numbers we've seen so far, along with their indices. So, number_value -> its_index.

   • Example: {2: 0, 7: 1} means "the number 2 was found at index 0, and the number 7 was found at index 1".

2. Iterate through the nums array, one number at a time, along with its index.

3. For each num at current_index:
   a. Calculate the complement we need: complement = target - num.
   b. Check if complement exists in our hash map.
   * If YES, it means we've previously encountered the complement number. We've found our pair!
   * The current number is num (at current_index).
   * The other number is complement (whose index is stored in the hash map).
   * Return [current_index, hash_map[complement]].
   * If NO, the complement is not in our map yet. This means num isn't part of a pair with any number we've seen so far.
   * So, we add num and its current_index to our hash map: hash_map[num] = current_index. This way, if a future number needs num as its complement, it can find it quickly.

Let's walk through nums = [2, 7, 11, 15], target = 9:

• Start: map = {} (empty)

• Iteration 1:

  • num = 2, current_index = 0
  • complement = 9 - 2 = 7
  • Is 7 in map? No.
  • Add 2 to map: map = {2: 0}

• Iteration 2:

  • num = 7, current_index = 1
  • complement = 9 - 7 = 2
  • Is 2 in map? YES! Its index is 0.
  • We found the pair! Return [current_index (1), map[2] (0)], which is [1, 0]. (Remember, order doesn't matter, so [0, 1] is also correct).

And just like that, we found the pair in a single pass through the array!

5. Code: Bringing it to Life in C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // We'll use an unordered_map (hash map) to store numbers
        // we've seen and their corresponding indices.
        // Key: The number itself
        // Value: The index where that number was found
        unordered_map<int, int> pairIdx;

        // Iterate through the array `nums` from left to right
        for (int i = 0; i < nums.size(); ++i) {
            int num = nums[i]; // Get the current number

            // Calculate the 'complement' needed:
            // If num + complement = target, then complement = target - num
            int complement = target - num;

            // Check if this 'complement' already exists in our map.
            // If it does, we've found our pair!
            if (pairIdx.find(complement) != pairIdx.end()) {
                // If complement is found, return its index (from the map)
                // and the current number's index (i).
                return {pairIdx[complement], i}; 
            }

            // If the complement wasn't found, it means the current 'num'
            // doesn't form a pair with any number we've seen so far.
            // So, we add the current 'num' and its 'index' to our map
            // for future numbers to potentially find it as their complement.
            pairIdx[num] = i;
        }

        // According to the problem constraints, there's always exactly one solution,
        // so this line should technically never be reached in a valid test case.
        return {}; 
    }
};

6. Time & Space Complexity Analysis

Understanding how efficient our code is crucial for competitive programming and real-world development! We measure efficiency using "Big O" notation.

Brute Force Approach (nested loops):

• Time Complexity: O(n^2)
  • We have two nested loops. If n is the number of elements in nums, the outer loop runs n times, and the inner loop runs approximately n times for each outer iteration. This leads to n * n operations in the worst case.
• Space Complexity: O(1)
  • This approach uses a constant amount of extra space (just a few variables for loop counters, etc.), regardless of the input array size.

Hash Map Approach (our solution):

• Time Complexity: O(n)
  • We iterate through the nums array only once.
  • Inside the loop, hash map operations (find and insertion []) take O(1) time on average. In the worst case (due to hash collisions), they can degrade to O(n), but this is rare with good hash functions and typically averaged out.
  • Since we do a constant amount of work for each of the n elements, the total time complexity is linear, O(n). This is significantly faster than O(n^2) for large n!
• Space Complexity: O(n)
  • In the worst-case scenario, if no pair is found until the very last element, our hash map could end up storing all n elements from the nums array. Each element stored takes up some memory. Thus, the space required grows linearly with the input size n.

This is a classic example of a time-space trade-off: by using extra space (for the hash map), we dramatically reduce the time it takes to find the solution!

7. Key Takeaways

1. The Power of Hash Maps: For problems requiring fast lookups (checking if an element exists, or getting its associated value), hash maps (or hash tables) are your best friend! They can often turn O(n) or O(n^2) search problems into O(1) average-time lookups.
2. Complementary Thinking: Many "sum" or "difference" problems can be reframed. Instead of searching for any two numbers, think: if I have X, what Y do I need (target - X)? Then, how fast can I find Y?
3. Time-Space Trade-off: Sometimes, using more memory (space) can lead to much faster execution times. This is a common design pattern in algorithms.
4. Foundation Problem: Two Sum is a fundamental problem. Mastering it builds a strong foundation for tackling more complex algorithmic challenges! It teaches you to look beyond the obvious brute-force and consider data structures that optimize specific operations.

8. Submission Details

• Author Account: ahB1IK4YXF
• Publishing Time: 2026-05-31 22:38:38