Two Sum 🧠

LeetCode Link: Two Sum

Difficulty: Easy

Problem Explanation 📝

Problem: LeetCode 1 - Two Sum

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

Intuition: To find the pair of numbers that add up to the target, we can utilize a hash map. By iterating through the array and checking if the complement (target - current number) exists in the hash map, we can efficiently find the desired pair.

Approach:

1. Initialize an empty hash map to store the elements and their indices.
2. Iterate through each element num and its index in the input array nums:

• Calculate the complement as target - num.
• If the complement exists in the hash map, return the indices [map[complement], index].
• Otherwise, add the current element num and its index to the hash map.

3. If no solution is found, return an empty vector or handle it as per the problem's requirement.

⌛ Time Complexity: The time complexity of this approach is O(n), where n is the size of the input array nums. This is because we iterate through the array once and perform constant-time operations for each element.

💾 Space Complexity: The space complexity is O(n), as the hash map can potentially store all elements of the input array.

Solutions 💡

Cpp 💻

class Solution {
  public:
    vector<int> twoSum(vector<int> &nums, int target) {
        unordered_map<int, int> numMap;

        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];

            if (numMap.count(complement) > 0) {
                return {numMap[complement], i};
            }

            numMap[nums[i]] = i;
        }

        return {}; // Handle no solution as per problem's requirement
    }
};

// class Solution {
// public:
//     vector<int> twoSum(vector<int>& nums, int target) {
//         unordered_map<int, int> M;
//         vector<int> res;
//         for(int i = 0; i < nums.size(); i++) {
//             int compliment = target - nums[i];

//             // If we find the compliment
//             if(M.find(compliment) != M.end()) {
//                 // returning i and index of compliment
//                 res.push_back(M[compliment]);
//                 res.push_back(i);
//             }
//             else // insert pair
//                 M.insert( {nums[i], i});
//         }
//         return res;
//     }
// };

Python 🐍

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        prevMap = {}  # val -> index

        for i, n in enumerate(nums):
            diff = target - n
            if diff in prevMap:
                return [prevMap[diff], i]
            prevMap[n] = i