LeetCode 1: Two Sum Optimized Solution (O(n) Hash Map)

by

Welcome to Episode 7 of our 50-Day Competitive Programming Challenge! In our previous episode, we tackled the legendary Two Sum problem using the “Brute Force” method with nested loops.

While Brute Force is a great baseline to show an interviewer, its O(n^2) time complexity is too slow for massive datasets. Today, we are going to optimize our solution to run in blazing fast O(n) time by introducing one of the most powerful tools in a programmer’s arsenal: The Hash Map.

The Goal: Trading Space for Speed

Our objective is to find the two numbers that add up to our target, but we are only allowed to loop through the array one single time.

To do this, we use a Hash Map (unordered_map in C++). A Hash Map allows us to store data in Key-Value Pairs and look it up instantly in $O(1)$ time.

  • The Key: The actual number we saw in the array.
  • The Value: The index position where we saw it.

The “Complement” Logic

Instead of using two pointers to guess combinations, we use basic algebra. If we know the current number we are looking at, and we know our target, we can easily calculate the exact partner we need to win:

Complement = Target - Current Number

As we loop through the array, we ask our Hash Map: “Have I already passed my Complement?”

  • If Yes: We win! Return the current index and the index stored in the map.
  • If No: We store our current number and its index in the map, and move to the next number.

The Universal Pseudocode

Before we write the C++, here is the language-independent algorithm. You can apply this exact logic whether you are coding in Java, Python, or JavaScript!

Step 1: Input Setup
array nums[n], answers[2] | int target
hashmap seenNumbers

STEP 2: Loop Logic
LOOP : A ( i : 0 to n -1 )

    var complement = target - nums[i]
    
    IF (complement EXISTS IN seenNumbers) THEN ->
        answers[0] = seenNumbers[complement]
        answers[1] = i
        return answers[]
    END IF
    
    seenNumbers[ nums[i] ] = i

END LOOP : A

return answers[]

C++ Code Implementation

Here is the clean, fully optimized C++ solution utilizing the unordered_map.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        // Step 1: Input Setup
        vector<int> answers(2);              // Array to hold our final 2 indices
        unordered_map<int, int> seenNumbers; // Our dictionary (Key: Number, Value: Index)
        
        // STEP 2: Loop through the array exactly once
        for (int i = 0; i < nums.size(); i++) {
            
            // Calculate the specific partner we need
            int complement = target - nums[i];
            
            // Check if the partner exists in our map's Keys
            if (seenNumbers.find(complement) != seenNumbers.end()) {
                
                // MATCH FOUND! Grab the old index from the map, and our current index
                answers[0] = seenNumbers[complement];
                answers[1] = i;
                
                return answers; // Return immediately
            }
            
            // If not found, write the current number and its index into the map
            seenNumbers[nums[i]] = i;
        }
        
        return answers; // Fallback return
    }
};

Complexity Analysis

  • Time Complexity: $O(n)$. We only loop through the array a single time. Looking up our complement inside the Hash Map takes $O(1)$ instant time.
  • Space Complexity: $O(n)$. To achieve this incredible speed, we had to use extra memory to build our dictionary. If the answer is at the very end of a massive array, our map will hold almost every number. We successfully traded Space for Speed!

Conclusion

Congratulations! You have just solved the most famous interview question in the world using a highly optimized, professional approach. Understanding how to utilize Hash Maps to reduce time complexity is a massive milestone in your programming journey.

Want to see the visual “Rear-View Mirror” dry run of how the map populates step-by-step? Watch the full video tutorial below!

Hit the “Join” button on our YouTube channel to become a Snippet Supporter! You’ll get instant access to our downloadable ad-free Master Notes, featuring the complete code and step-by-step logic breakdown so you can confidently review before your placement drives. Link to join our Youtube Channel Simple Snippets : https://www.youtube.com/channel/UCRIWTSgd7hGtZhx4RYoASEg/join

Leave a Comment