Two Sum

Intuition

For each element of the given array, try to find another element such that their sum equals the target. If such two numbers exist, return their indices; otherwise, return -1.

Approach

Iterate in array from 0 to last index of the array (lets call this variable i). Now, run another loop say(j) from i+1 to last index of the array.

If sum of arr[i] and arr[j] equals to target then return the i and j. If no such indices are found then return -1 and -1.

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

class Solution {
public:
    /*Function to find two indices in the array `nums`
    such that their elements sum up to `target`.*/
  
    vector<int> twoSum(vector<int>& nums, int target) {
        
        int n = nums.size();
        //create ans vector to store ans
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                
                /*if nums[i] + nums[j] is equal to 
                target put i and j in ans*/
                if (nums[i] + nums[j] == target) {
                    ans.push_back(i);
                    ans.push_back(j);
                    return ans;
                }
                
            }
        }
        
        // Return {-1, -1} if no such pair is found
        return {-1, -1}; 
    }
};

int main() {
    int n = 5;
    vector<int> nums = {2, 6, 5, 8, 11};
    int target = 14;
    
    // Create an instance of the Solution class
    Solution sol;
    
    // Call the twoSum method to find the indices
    vector<int> ans = sol.twoSum( nums, target);
    
    // Print the result
    cout << "This is the answer: [" << ans[0] << ", " << ans[1] << "]" << endl;
    
    return 0;
}
import java.util.*;

class Solution {
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    public int[] twoSum(int[] nums, int target) {
        
        int n = nums.length;
        //create ans array to store ans
        int[] ans = new int[2];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                
                /* if nums[i] + nums[j] is equal to 
                   target put i and j in ans */
                if (nums[i] + nums[j] == target) {
                    ans[0] = i;
                    ans[1] = j;
                    return ans;
                }
                
            }
        }
        
        // Return {-1, -1} if no such pair is found
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int n = 5;
        int[] nums = {2, 6, 5, 8, 11};
        int target = 14;
        
        // Create an instance of the Solution class
        Solution sol = new Solution();
        
        // Call the twoSum method to find the indices
        int[] ans = sol.twoSum(nums, target);
        
        // Print the result
        System.out.println("This is the answer: [" + ans[0] + ", " + ans[1] + "]");
    }
}
from typing import List

class Solution:
    """
    Function to find two indices in the array `nums`
    such that their elements sum up to `target`.
    """
    def twoSum(self,nums: List[int], target: int) -> List[int]:
        
        n = len(nums)
        # Create ans list to store the indices
        ans = [0, 0]
        for i in range(n):
            for j in range(i + 1, n):
                
                """If nums[i] + nums[j] is equal to target
                put i and j in ans"""
                if nums[i] + nums[j] == target:
                    ans[0] = i
                    ans[1] = j
                    return ans
        
        # Return [-1, -1] if no such pair is found
        return [-1, -1]

if __name__ == "__main__":
    n = 5
    nums = [2, 6, 5, 8, 11]
    target = 14
    
    # Create an instance of the Solution class
    sol = Solution()
    
    # Call the twoSum method to find the indices
    ans = sol.twoSum(nums, target)
    
    # Print the result
    print(f"This is the answer: [{ans[0]}, {ans[1]}]")
class Solution {
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    twoSum(nums, target) {
        
        const n = nums.length;
        //create ans array to store ans
        let ans = [0, 0];
        
        for (let i = 0; i < n; i++) {
            for (let j = i + 1; j < n; j++) {
                
                 /* if nums[i] + nums[j] is equal to 
                   target put i and j in ans */
                if (nums[i] + nums[j] === target) {
                    ans[0] = i;
                    ans[1] = j;
                    return ans;
                }
                
            }
        }
        
        //Return {-1, -1} if no such pair is found
        return [-1, -1];
    }
}

const nums = [2, 6, 5, 8, 11];
const target = 14;

// Create an instance of the Solution class
const sol = new Solution();

// Call the twoSum method to find the indices
const ans = sol.twoSum(nums, target);

console.log(`This is the answer: [${ans[0]}, ${ans[1]}]`);

Complexity Analysis

Time Complexity:O(N ²), For using two nested loops to traverse the array, where N is the length of that array. Space Complexity: O(1), not using extra space.

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

Iterate in array from 0 to last index of the array (lets call this variable i).
Then check if the other required element(i.e. target-arr[i]) exists in the hashMap.
- If that element exists, then return the current index i.e. i, and the index of the element found using map.
- 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.
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}.

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

class Solution {
public:
/* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    vector<int> twoSum(vector<int>& nums, 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 = nums[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() {
    vector<int> nums = {2, 6, 5, 8, 11};
    int target = 14; 

    //create an instance of Solution class
    Solution sol;
    
    // Call the twoSum method from Solution class
    vector<int> ans = sol.twoSum(nums, target);

    // Print the result
    cout << "Indices of the two numbers that sum up to " << target << " are: [" << ans[0] << ", " << ans[1] << "]" << endl;

    return 0;
}
import java.util.*;

class Solution {
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    public int[] twoSum(int[] nums, int target) {
        
        // Map to store (element, index) pairs
        Map<Integer, Integer> mpp = new HashMap<>();
        
        // Size of the nums array
        int n = nums.length;
        
        for (int i = 0; i < n; i++) {
            // Current number in the array
            int num = nums[i];
            
            // Number needed to reach the target
            int moreNeeded = target - num;

            // Check if the complement exists in map
            if (mpp.containsKey(moreNeeded)) {
                /* Return the indices of the two
                numbers that sum up to target*/
                return new int[]{mpp.get(moreNeeded), i};
            }

            // Store current number and its index in map
            mpp.put(num, i);
        }

        // If no such pair found, return {-1, -1}
        return new int[]{-1, -1};
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 6, 5, 8, 11};
        int target = 14;

        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the twoSum method from Solution class
        int[] ans = sol.twoSum(nums, target);

        // Print the result
        System.out.println("Indices of the two numbers that sum up to " + target + " are: [" + ans[0] + ", " + ans[1] + "]");
    }
}
from typing import List

class Solution:
    """ Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    """
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Dictionary to store (element, index) pairs
        mpp = {}
        
        # Length of the nums list
        n = len(nums)
        
        for i in range(n):
            # Current number in the list
            num = nums[i]
            
            # Number needed to reach the target
            more_needed = target - num

            # Check if complement exists in dictionary
            if more_needed in mpp:
                """ Return the indices of the two
                numbers that sum up to target"""
                return [mpp[more_needed], i]

            """Store current number and 
            its index in dictionary"""
            mpp[num] = i
        
        # If no such pair found, return [-1, -1]
        return [-1, -1]


if __name__ == "__main__":
    nums = [2, 6, 5, 8, 11]
    target = 14

    # Create an instance of Solution class
    sol = Solution()
    
    # Call the twoSum method from Solution class
    ans = sol.twoSum(nums, target)

    # Print the result
    print(f"Indices of the two numbers that sum up to {target} are: [{ans[0]}, {ans[1]}]")
class Solution {
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    twoSum(nums, target) {
        // Map to store (element, index) pairs
        const mpp = new Map();
        
        // Size of the nums array
        const n = nums.length;
        
        for (let i = 0; i < n; i++) {
            // Current number in the array
            const num = nums[i];
            
            // Number needed to reach the target
            const moreNeeded = target - num;

            // Check if the complement exists in map
            if (mpp.has(moreNeeded)) {
                /* Return the indices of the 
                two numbers that sum up to target*/
                return [mpp.get(moreNeeded), i];
            }

            // Store current number and its index in map
            mpp.set(num, i);
        }

        // If no such pair found, return [-1, -1]
        return [-1, -1];
    }
}


function main() {
    const nums = [2, 6, 5, 8, 11];
    const target = 14;

    // Create an instance of Solution class
    const sol = new Solution();
    
    const ans = sol.twoSum(nums, target);

    // Print the result
    console.log(`Indices of the two numbers that sum up to ${target} are: [${ans[0]}, ${ans[1]}]`);
}

// Call the main function
main();

Complexity Analysis

Time Complexity:O(N), where N is the 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(which rarely happens), the unordered_map takes O(N) to find an element. In that case, the time complexity will be O(N²). 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) for using the map data structure.

Intuition

Imagine being at a market with a list of ingredients, each with different calorie counts. You want to create a dish that meets a specific calorie target.

To find the right pair of ingredients, first organize your ingredients from lowest to highest calories. This way, you can easily adjust your choices based on the total calories you need.

Start with the lowest calorie ingredient and the highest calorie ingredient. By comparing their combined calories to target, decide whether to increase the total (by choosing a higher calorie ingredient) or decrease it (by choosing a lower calorie ingredient). This method allows you to efficiently zero in on the right pair, just like adjusting ingredients in a recipe until it tastes just right. If you find the perfect match, conclude that as your dish! If not, conclude there’s no suitable pair.

Approach

Sort the given array and initialize two pointers i.e. left, which points to the 0th index, and right, which points to the last index.
Now, using a loop, check the sum of arr[left] and arr[right] until left less than right.
- If sum of arr[left] and arr[right] greater than target, decrement the right pointer.
- If sum of arr[left] and arr[right] less than target, increment the left pointer.
- If sum of arr[left] and arr[right] equals to target, return the result. Finally, if no results are found we will return {-1, -1}.

Dry Run

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

class Solution {
public:
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    vector<int> twoSum(vector<int>& nums, int target) {
        // Size of the nums vector
        int n = nums.size(); 
        
        // Vector to store indices of two numbers
        vector<int> ans; 
        
        vector<vector<int>> eleIndex;
        for(int i = 0; i < nums.size(); i++){
            eleIndex.push_back({nums[i], i});
        }
        
        //Sort by first element in ascending order
        sort(eleIndex.begin(), eleIndex.end(), [](const vector<int>& a, const vector<int>& b) {
           return a[0] < b[0]; 
        });

        /* Two pointers: one starting 
        from left and one from right*/
        int left = 0, right = n - 1; 

        while (left < right) {
             /* Calculate sum of elements
             at left and right pointers*/
            int sum = eleIndex[left][0] + eleIndex[right][0];

            if (sum == target) {
                
                /* If sum equals target, 
                store indices and return*/
                ans.push_back(eleIndex[left][1]);
                ans.push_back(eleIndex[right][1]);
                return ans;
                
            } else if (sum < target) {
                
                /* If sum is less than target, 
                move left pointer to the right*/
                left++;
                
            } else {
                
                /* If sum is greater than target,
                move right pointer to the left*/
                right--;
                
            }
        }

        // If no such pair found, return {-1, -1}
        return {-1, -1};
    }
};

int main() {
    vector<int> nums = {2, 6, 5, 8, 11};
    int target = 14;

    // Create an instance of Solution class
    Solution sol;

    // Call the twoSum method from Solution class
    vector<int> ans = sol.twoSum(nums, target);

    // Print the result
    cout << "Indices of the two numbers that sum up to " << target << " are: [" << ans[0] << ", " << ans[1] << "]" << endl;

    return 0;
}
import java.util.*;

class Solution {
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    public int[] twoSum(int[] nums, int target) {
        // Size of the nums array
        int n = nums.length;
        
        // Array to store indices of two numbers
        int[] ans = new int[2];
        
        // 2D array to store {element, index} pairs
        int[][] eleIndex = new int[n][2];
        for (int i = 0; i < nums.length; i++) {
            eleIndex[i][0] = nums[i];
            eleIndex[i][1] = i;
        }
        
        /* Sort eleIndex by the first
        element in ascending order*/
        Arrays.sort(eleIndex, new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                return Integer.compare(a[0], b[0]);
            }
        });

        /* Two pointers: one starting 
        from left and one from right*/
        int left = 0, right = n - 1;

        while (left < right) {
            /* Calculate sum of elements at
            left and right pointers*/
            int sum = eleIndex[left][0] + eleIndex[right][0];

            if (sum == target) {
                
                /* If sum equals target, 
                store indices and return*/
                ans[0] = eleIndex[left][1];
                ans[1] = eleIndex[right][1];
                return ans;
                
            } else if (sum < target) {
                
                /* If sum is less than target,
                move left pointer to the right*/
                left++;
                
            } else {
                
                /* If sum is greater than target,
                move right pointer to the left*/
                right--;
                
            }
        }

        // If no such pair found, return {-1, -1}
        return new int[]{-1, -1};
    }
}

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 6, 5, 8, 11};
        int target = 14;

        // Create an instance of Solution class
        Solution sol = new Solution();

        int[] ans = sol.twoSum(nums, target);

        // Print the result
        System.out.println("Indices of the two numbers that sum up to " + target + " are: [" + ans[0] + ", " + ans[1] + "]");
    }
}
from typing import List

class Solution:
    """ Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    """
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Size of the nums array
        n = len(nums)
        
        # List to store indices of two numbers
        ans = [-1, -1]
        
        # 2D list to store [element, index] pairs
        eleIndex = []
        for i in range(len(nums)):
            eleIndex.append([nums[i], i])
        
        """ Sort eleIndex by the first
        element in ascending order"""
        eleIndex.sort(key=lambda x: x[0])

        """ Two pointers: one starting 
         from left and one from right"""
        left, right = 0, n - 1

        while left < right:
            """ Calculate sum of elements
            at left and right pointers"""
            sum_val = eleIndex[left][0] + eleIndex[right][0]

            if sum_val == target:
                
                """ If sum equals target,
                store indices and return"""
                ans[0] = eleIndex[left][1]
                ans[1] = eleIndex[right][1]
                return ans
                
            elif sum_val < target:
                
                """ If sum is less than target,
                move left pointer to the right"""
                left += 1
                
            else:
                
                """ If sum is greater than target,
                move right pointer to the left"""
                right -= 1

        # If no such pair found, return [-1, -1]
        return ans

if __name__ == "__main__":
    nums = [2, 6, 5, 8, 11]
    target = 14

    # Create an instance of Solution class
    sol = Solution()

    ans = sol.twoSum(nums, target)

    # Print the result
    print(f"Indices of the two numbers that sum up to {target} are: [{ans[0]}, {ans[1]}]")
class Solution {
    /* Function to find two indices in the array `nums`
       such that their elements sum up to `target`.
    */
    twoSum(nums, target) {
        // Size of the nums array
        let n = nums.length;
        
        // Array to store indices of two numbers
        let ans = [-1, -1];
        
        // 2D array to store [element, index] pairs
        let eleIndex = [];
        for (let i = 0; i < nums.length; i++) {
            eleIndex.push([nums[i], i]);
        }
        
        /* Sort eleIndex by the first
        element in ascending order*/
        eleIndex.sort((a, b) => a[0] - b[0]);

        /* Two pointers: one starting
        from left and one from right*/
        let left = 0, right = n - 1;

        while (left < right) {
            /* Calculate sum of elements 
            at left and right pointers*/
            let sumVal = eleIndex[left][0] + eleIndex[right][0];

            if (sumVal === target) {
                
                /* If sum equals target,
                store indices and return*/
                ans[0] = eleIndex[left][1];
                ans[1] = eleIndex[right][1];
                return ans;
                
            } else if (sumVal < target) {
                
                /* If sum is less than target,
                move left pointer to the right*/
                left++;
                
            } else {
                
                /* If sum is greater than target,
                move right pointer to the left*/
                right--;
            }
        }

        // If no such pair found, return [-1, -1]
        return ans;
    }
}

// Main function to test the solution
let nums = [2, 6, 5, 8, 11];
let target = 14;

// Create an instance of Solution class
let sol = new Solution();

let ans = sol.twoSum(nums, target);

// Print the result
console.log(`Indices of the two numbers that sum up to ${target} are: [${ans[0]}, ${ans[1]}]`);

Complexity Analysis

Time Complexity: O(N) + O(NxlogN), where N is size of the array. As the loop will run at most N times & sorting the array will take N * logN time complexity. Space Complexity: O(1) not using any extra space.

Note: Here we are distorting the given array. So, if we need to consider this change, the space complexity will be O(N).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis

Intuition

Approach

Complexity Analysis

Intuition

Approach

Dry Run

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts