हिन्दी flagहिन्दी  
CLOSE

Suggested:

Problem Statement

Given an array of integers arr[] and an integer target.

There could be two variant of it:

1 – Return Yes or No

Given an array of integers arr[] and an integer target, the objective is to determine whether there exist two numbers in the array whose sum is equal to the target. If such pairs exist, the algorithm should return “Yes”, otherwise, it should return “No”.

2 – Return Indices of Pairs

Given an array of integers arr[]and the target value, the goal is to find the indices of two numbers in the array whose sum equals the target. If such pair exist, the algorithm should return the indices of the two numbers as a pair; otherwise, it should return {-1, -1} to indicate no such pairs exist. Again, each element of the array can be used at most once in a pair.

Examples

Example 1:

Input: nums = [1, 2, 6, 3, 10], target = 7
Output: [0, 2]

Explanation: nums[0] + nums[2] = 1 + 6 = 7
Example 2:

Input: nums = [1, 3, 5, -7, 6, -3], target = 0
Output: [1, 5]

Explanation: nums[1] + nums[5] = 3 + (-3) = 0

Different Approaches

1️⃣ Brute Force Approach

Variant 1

#include <vector>
#include <iostream>

using namespace std;

string twoSumExists(const vector<int>& nums, int target) {
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (nums[i] + nums[j] == target) {
                return "YES";
            }
        }
    }
    return "NO";
}

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    cout << twoSumExists(nums, target) << endl; // Output: YES
    return 0;
}

// Output
YES

Variant 2 - Return Indices of Pairs:

#include <vector>
#include <iostream>

using namespace std;

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

int main() {
    vector<int> nums = {2, 7, 11, 15};
    int target = 9;
    vector<int> result = twoSumIndices(nums, target);
    cout << result[0] << " " << result[1] << endl; // Output: 0 1
    return 0;
}

Complexity Analysis:

  • Time Complexity: O(N ^ 2) There are two nested loops, each running for approximately N times.
  • Space Complexity:O(1)

2️⃣ Using Hashing

The problem tells us that there are two numbers x and y in the array such that:

x + y = target

This can be rearranged as:

y = target - x

So, if we know one number x, we can calculate the required counterpart y (or complement) as:

complement = target - x

So, when iterating the elements we get x and check if (10 - x) which is y present in the HashTable, also this is a constant lookup time.

Intuition:

The idea is to traverse the array and use a HashMap to check if for each element, an element in the HashMap exists, such that sum of both of the elements is equal to the target. This method trims down the search space and provides a better time complexity.

Approach:

  1. Iterate in array from 0 to last index of the array (lets call this variable i).
  2. Then check if the other required element(i.e. target-arr[i]) exists in the hashMap.
    1. If that element exists, then return the current index i.e. i, and the index of the element found using map.
    2. If that element does not exist, then just store the current element in the hashMap along with its index. Because in the future, the current element might be a part of our answer.
  3. If at the end we have traversed whole array and no pair is found, that means that the target is unachievable. In this case, return {-1, -1}.

Dry Run:

       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  6  |  2  | 10  |  3  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
First Iteration:
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  6  |  2  | 10  |  3  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
          ^
          |
          i
      +--------+
map = | empty  |
      +--------+
target = 7

 num = nums[i] = 1
 moreNeeded = target - num
            = 7 - 1 = 6
 Check if moreNeeded exist in map
 It does not exist in map, insert {num, i} = {1, 0} into map

i++
Second Iteration:
       +-----+-----+-----+-----+-----+-----+
nums = |  1  |  6  |  2  | 10  |  3  |  9  |
       +-----+-----+-----+-----+-----+-----+
          0     1     2     3     4     5
                ^
                |
                i
      +--------+
map = | {1, 0} |
      +--------+
target = 7

num = nums[i] = 6
moreNeeded = target - num
           = 7 - 6 = 1

Check if moreNeeded exists in map
Yes it does. return {map[moreNeeded], i} which is {0, 1}
two-sum.jpg

Variant 1:

#include <bits/stdc++.h>
using namespace std;

string twoSum(int n, vector<int> &arr, int target) {
    unordered_map<int, int> mpp;
    for (int i = 0; i < n; i++) {
        int num = arr[i];
        int moreNeeded = target - num;
        if (mpp.find(moreNeeded) != mpp.end()) {
            return "YES";
        }
        mpp[num] = i;
    }
    return "NO";
}

int main()
{
    int n = 5;
    vector<int> arr = {2, 6, 5, 8, 11};
    int target = 14;
    string ans = twoSum(n, arr, target);
    cout << "This is the answer for variant 1: " << ans << endl;
    return 0;
}

Variant 2:

#include <bits/stdc++.h>
using namespace std;

vector<int> twoSum(int n, vector<int> &arr, int target) {
    // Map to store (element, index) pairs
    unordered_map<int, int> mpp;
    // Size of the nums vector
    int n = nums.size();
    
    for (int i = 0; i < n; i++) {
        // Current number in the vector
        int num = arr[i];
        // Number needed to reach the target
        int moreNeeded = target - num;
        
        // Check if the complement exists in map
        if (mpp.find(moreNeeded) != mpp.end()) {
            // Return the indices of the two numbers that sum up to target
            return {mpp[moreNeeded], i};
        }
        // Store current number and its index in map.
        mpp[num] = i;
    }
    
    // If no such pair found, return {-1, -1}
    return { -1, -1};
}

int main()
{
    int n = 5;
    vector<int> arr = {2, 6, 5, 8, 11};
    int target = 14;
    vector<int> ans = twoSum(n, arr, target);
    cout << "This is the answer for variant 2: [" << ans[0] << ", "
         << ans[1] << "]" << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(N), where N = size of the array.

  • The loop runs N times in the worst case and searching in a hashmap takes O(1) generally. So the time complexity is O(N).

Note: In the worst case, the unordered_map takes O(N) to find an element. If we use map instead of unordered_map, the time complexity will be O(N *logN) as the map data structure takes logN time to find an element.

Space Complexity: O(N) as we use the map data structure.

3️⃣ Optimized Approach (using two-pointer)

Note: It is applicable if the array is sorted.

The Two Pointer approach involves using two pointers that traverse through the array from different ends simultaneously.

Algorithm:

  1. Sort the given array in non-decreasing order.
  2. Initialize two pointer, one at the beginning (left end) of the array and the other at the end (right end) of the array.
  3. While the left pointer is less than the right pointer:
    1. Calculate the sum of elements pointed by the left and right pointers.
    2. If the sum equals the target:
      1. Return the indices of the elements by the left and right pointers.
      2. If the sum is less than the target:
        1. Increment the left pointer.
      3. If the sum is greater than the target:
        1. Decrement the right pointer.
  4. If no such pair is found, return {-1, -1}

Code:

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> twoSum(std::vector<int>& nums, int target) {
    std::vector<int> result;
    int left = 0;
    int right = nums.size() - 1;

    // Sort the array
    std::sort(nums.begin(), nums.end());

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            result.push_back(left);
            result.push_back(right);
            return result;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    // No solution found
    result.push_back(-1);
    result.push_back(-1);
    return result;
}

int main() {
    std::vector<int> nums = {2, 7, 11, 15};
    int target = 9;

    std::vector<int> indices = twoSum(nums, target);

    if (indices[0] != -1 && indices[1] != -1) {
        std::cout << "Indices: " << indices[0] << ", " << indices[1] << std::endl;
        std::cout << "Numbers: " << nums[indices[0]] << ", " << nums[indices[1]] << std::endl;
    } else {
        std::cout << "No solution found." << std::endl;
    }

    return 0;
}

// Output
Indices: 0, 1
Numbers: 2, 7

Complexity Analysis:

  • Time Complexity:
    • Sorting the array: The time complexity of sorting the array using std::sort typically uses, O(n log n).
    • Traversing the array with two pointers: In the worst-case scenario, where we need to traverse the entire array once, the time complexity of this step is O(n), where n is the number of elements in the array.
    • Therefore, the overall time complexity is dominated by the sorting step, making it O(n log n).
  • Space Complexity:O(1) as we are not using any extra array space.

Your experience on this site will be improved by allowing cookies Cookie Policy