Two Sum – Pair with Given Sum

Given an array arr[] of positive integers and another integer target. Determine if there exists two distinct indices such that the sum of there elements is equals to target.

Examples:

Input: arr[] = [1, 4, 45, 6, 10, 8], target = 16
Output: true
Explanation: arr[3] + arr[4] = 6 + 10 = 16.

Input: arr[] = [1, 2, 4, 3, 6], target = 11
Output: false
Explanation: None of the pair makes a sum of 11.

Constraints:
1 ≤ arr.size ≤ 10⁵
1 ≤ arr[i] ≤ 10⁵
1 ≤ target ≤ 2*10⁵

Approach 01:

#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool twoSum(vector<int>& numbers, int target) {
        unordered_map<int, int> frequencyMap;
        
        for (int number : numbers) {
            // Check if the complement exists in the frequency map
            if (frequencyMap[target - number] > 0) {
                return true;
            }
            // Add the current number to the frequency map
            ++frequencyMap[number];
        }

        return false;
    }
};

class Solution:
    def twoSum(self, numbers, target):
        frequencyMap = {}
        
        for number in numbers:
            # Check if the complement exists in the frequency map
            if frequencyMap.get(target - number, 0):
                return True
            # Add the current number to the frequency map
            frequencyMap[number] = frequencyMap.get(number, 0) + 1
    
        return False

Time Complexity

• Iterating Through the Array:
  • The algorithm iterates through the array of size \( n \) once, making the iteration time complexity \( O(n) \).
• Lookup and Insertion in the Hash Map:
  • For each number in the array, a lookup and insertion operation is performed on the hash map. These operations have an average time complexity of \( O(1) \).
  • Thus, for \( n \) numbers, the combined complexity of lookup and insertion is \( O(n) \).
• Overall Time Complexity:

  The total time complexity is: \( O(n) \).

Space Complexity

• Hash Map Storage:
  • The hash map stores at most \( n \) elements in the worst case, where \( n \) is the size of the array.
  • This requires \( O(n) \) space.
• Auxiliary Variables:
  • Additional variables like number and target use \( O(1) \) space.
• Overall Space Complexity:

  The total space complexity is: \( O(n) \).