Two Sum

#cpp #dsa #leetcode #learning

Problem Link - Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Naive Approach
Simply iterate through the array and for each element x, find remaining element(target-x) in the rest of the array
Code

    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {}; // No solution found
    }

Time Complexity - O(N^2) - for each element,we are trying to find another element in the rest array that forms a target which takes O(N)

Sorting & Two-Pointer Approach

first sort the array - takes O(NlogN) time complexity
take 2 pointers, left pointer starts from 0th index, right pointer starts from n-1th index.
we will iterate through until left<right(because we need to find 2 different indices that makes up the target)
check for the following 3 cases:
arr[left]+arr[right]==target
means we found a pair that makes the target so return the indices
arr[left]+arr[right]>target
the sum of elements pointeed by left and right pointer is greater,so we need to reduce the sum such that it comes closer to target, so decrement the right pointer(right pointer points to highest number, array is sorted)
arr[left]+arr[right]<target
the sum of elements pointeed by left and right pointer is lesser than target,so we need to increase the sum such that it comes closer to target, so increment the left pointer(left pointer points to smallest number, array is sorted) Code


  vector<int> twoSum(vector<int>& arr, int target) {
     sort(arr.begin(),arr.end());
     int left = 0, right = arr.size()-1;
     while(left < right) {
        if(arr[left] + arr[right] < target) {
          left++; // we need next bigger number
        } 
        else if(arr[left] + arr[right] > target) {
           right--; // we need next smaller number
        } 
        else {
          return {left,right};
        }
      }
      return {};
  }

Time Complexity - O(N(logN+1))~ O(NlogN) -sort array and then a single traversal O(N)
Hashing + Single Traversal

we could optimize the naive approach, like instead of linearly searching the rest of array for rem element that makes up the target, we could use the hashmap, where we can check the element in O(1) time complexity.
start traversing the array, for each element, find its complement and check whether it is there in hashmap.
if yes then it is a pair.
if not store the curr element in hashmap, so that it could be useful in the future for another element where it makes a pair with this current one.


  vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap;
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            int complement = target - nums[i];
            if (numMap.count(complement)) {
                return {numMap[complement], i};
            }
            numMap[nums[i]] = i;
        }

        return {}; // No solution found
    }

Time Complexity - O(N) - single traversal
Space Complexity - O(N) - map that stores index of all elements