TeachingBee

Two Sum LeetCode: Check if a pair with given sum exists in Array

Two Sum LeetCode-Teachingbee
  • teachingbee
  • October 27, 2023

In this article we will solve Check if a pair with given sum exists in Array or also known as Two Sum LeetCode Problem using various approaches.

Difficulty: Easy, Asked-in: Amazon, Microsoft, Meta, Google.

Problem Statement

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

You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Input:

  • An array of integers nums
  • An integer target

Output: 

Return an array of two indices that add up to the target.

Constraints:

  • (2 ≤ nums.length ≤ 10^4)
  • (-10^9 ≤ target ≤ 10^9)

Examples:

Input: nums = [1, 5, 10, 20], target = 15
Output: [1, 2]
Explanation: nums[1] + nums[2] = 5 + 10 = 15, so we return [1, 2].

Input: nums = [4, 6, 12, 18], target = 10
Output: [0, 1]
Explanation: nums[0] + nums[1] = 4 + 6 = 10, so we return [0, 1].

Input: nums = [8, 3, 7, 2], target = 10
Output: [1, 3]
Explanation: nums[1] + nums[3] = 3 + 7 = 10, so we return [1, 3].

Solution

To solve this problem we will discuss three approaches:

  1. Brute Force
  2. Using HashMap
  3. Two Pointer Technique

1. Brute Force

Intuition

The basic idea behind the brute-force approach is to consider every possible pair of numbers in the array and check if their sum equals the target. We will be using two loops: the outer loop selects one number, and the inner loop searches for the second number.

Algorithm

  1. Initialise two loops: The outer loop runs from i = 0 to n – 2 and the inner loop from j = i + 1 to n – 1.
  2. Check for the sum: For every pair (i, j) where i is from the outer loop and j is from the inner loop, check if arr[i] + arr[j] is equal to the target.
  3. Return indices: If the sum of the elements at indices i and j equals the target, return the indices [i, j].
  4. No pair found: If the loops complete without finding a pair that sums up to the target, return [-1, -1].

Code Implementation

// C Implementation for 2 Sum

#include <stdio.h>
#include <stdlib.h> // Include the necessary header for malloc

int* twoSum(int arr[], int n, int target) {
    for (int i = 0; i < n-1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                int* result = (int*)malloc(2 * sizeof(int)); // Allocate memory for the result array
                result[0] = i; // Store the first index in the result
                result[1] = j; // Store the second index in the result
                return result; // Return the result array
            }
        }
    }
    int* result = (int*)malloc(2 * sizeof(int)); // Allocate memory for the result array
    result[0] = -1; // If no pair is found, store -1 in the result
    result[1] = -1;
    return result; // Return the result array
}

int main() {
    int n = 5;
    int arr[] = {2, 6, 5, 8, 11};
    int target = 14;
    int* ans = twoSum(arr, n, target); // Call the twoSum function
    printf("Indices of the two numbers are: [%d, %d]\n", ans[0], ans[1]);
    free(ans); // Free the dynamically allocated memory
    return 0;
}


// C++ Implementation for 2 Sum

#include <iostream>
#include <vector>

std::vector<int> twoSum(std::vector<int>& arr, int target) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == target) {
                return {i, j}; // Return a vector with the indices
            }
        }
    }
    return {-1, -1}; // If no pair is found, return {-1, -1}
}

int main() {
    int n = 5;
    std::vector<int> arr = {2, 6, 5, 8, 11};
    int target = 14;
    std::vector<int> ans = twoSum(arr, target); // Call the twoSum function
    std::cout << "Indices of the two numbers are: [" << ans[0] << ", " << ans[1] << "]\n";
    return 0;
}


// Java Implementation for 2 Sum

import java.util.*;

public class TwoSumBruteForce {
    // Function to find two numbers in the array that sum up to the target
    public static int[] twoSum(int[] arr, int target) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] + arr[j] == target) {
                    return new int[]{i, j}; // Return the indices of the two numbers
                }
            }
        }
        return new int[]{-1, -1}; // If no such pair is found, return [-1, -1]
    }

    public static void main(String args[]) {
        int n = 5;
        int[] arr = {2, 6, 5, 8, 11};
        int target = 14;
        int[] ans = twoSum(arr, target); // Call the twoSum function
        System.out.println("Indices of the two numbers are: [" + ans[0] + ", " + ans[1] + "]");
    }
}

// Python Implementation for 2 Sum

def twoSum(arr, target):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] + arr[j] == target:
                return [i, j]  # Return a list with the indices
    return [-1, -1]  # If no pair is found, return [-1, -1]

if __name__ == "__main__":
    n = 5
    arr = [2, 6, 5, 8, 11]
    target = 14
    ans = twoSum(arr, target)  # Call the twoSum function
    print(f"Indices of the two numbers are: {ans}")



// JavaScript Implementation for 2 Sum

function twoSum(arr, target) {
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] === target) {
                return [i, j]; // Return an array with the indices
            }
        }
    }
    return [-1, -1]; // If no pair is found, return [-1, -1]
}

const n = 5;
const arr = [2, 6, 5, 8, 11];
const target = 14;
const ans = twoSum(arr, target); // Call the twoSum function
console.log(`Indices of the two numbers are: [${ans[0]}, ${ans[1]}]`);

Code Explanation

Let’s undertstand the code via example

Given an array, nums = [2,1,3,4], and a target value of 4:

  • For index 0, the element is 2. We iterate through indices 1 to 3 to check if 4 - 2 = 2 exists. Since 2 does not exist from index 1 to 3, we move to the next index.
  • For index 1, the element is 1. We iterate through indices 2 to 3 to find if 4 - 1 = 3 exists. 3 exists at index 2, so we return the indices [1, 2].

If no such pair exists in the array that sums up to the target, the function will return [-1, -1].

Complexity

Time Complexity: O(n^2) – The code uses nested loops to compare all pairs of elements in the array.

Space Complexity: O(1) – The code uses a constant amount of additional space for variables and the result array.

2. Using HashMap

Intuition

Instead of using a nested loop to find the complement of a number (i.e., target - num), we can use a hash table to store numbers and their indices. This allows us to quickly check if the complement of a number exists in the array. The idea is to traverse the array once and use the HashMap to keep track of numbers we’ve seen so far and their respective indices.

Algorithm

  1. Initialize a HashMap: This will store the numbers in the array as keys and their indices as values.
  2. Traverse the array: For each number num in the array:
    • Calculate the complement as complement = target - num.
    • Check if the complement exists in the HashMap.
    • If it does, return the current index and the index of the complement from the HashMap.
    • If not, add the current number and its index to the HashMap.
  3. No pair found: If the loop completes without finding a pair that sums up to the target, return [-1, -1].

Code Implementation

// C Implementation for 2 Sum

#include <stdio.h>
#include <stdlib.h>

// Implementation of the Two Sum problem using a hash table (similar to HashMap)
int* twoSum(int arr[], int n, int target) {
    // Create a hash table to store numbers and their corresponding indices
    int* numToIndex = (int*)malloc((target + 1) * sizeof(int));

    // Initialize the hash table with -1 (indicating that the number has not been seen)
    for (int i = 0; i <= target; i++) {
        numToIndex[i] = -1;
    }

    // Iterate through the array
    for (int i = 0; i < n; i++) {
        // Calculate the complement of the current number with respect to the target
        int complement = target - arr[i];

        // Check if the complement exists in the hash table
        if (complement >= 0 && numToIndex[complement] != -1) {
            // If found, return the indices of the two numbers
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = numToIndex[complement];
            result[1] = i;
            free(numToIndex); // Free the allocated memory
            return result;
        }

        // Put the current number and its index into the hash table
        numToIndex[arr[i]] = i;
    }

    free(numToIndex); // Free the allocated memory
    // If no solution is found, return [-1, -1]
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = -1;
    result[1] = -1;
    return result;
}

int main() {
    int arr[] = {2, 6, 5, 8, 11};
    int target = 14;
    int* ans = twoSum(arr, 5, target);

    // Print the result
    printf("Indices of the two numbers are: [%d, %d]\n", ans[0], ans[1]);

    // Free the allocated memory
    free(ans);
    return 0;
}



// C++ Implementation for 2 Sum

#include <iostream>
#include <vector>
#include <unordered_map>

// Implementation of the Two Sum problem using an unordered_map (similar to HashMap)
std::vector<int> twoSum(std::vector<int>& arr, int target) {
    // Create an unordered_map to store numbers and their corresponding indices
    std::unordered_map<int, int> numToIndex;

    // Iterate through the array
    for (int i = 0; i < arr.size(); i++) {
        // Calculate the complement of the current number with respect to the target
        int complement = target - arr[i];

        // Check if the complement exists in the unordered_map
        if (numToIndex.find(complement) != numToIndex.end()) {
            // If found, return the indices of the two numbers
            return {numToIndex[complement], i};
        }

        // Put the current number and its index into the unordered_map
        numToIndex[arr[i]] = i;
    }

    // If no solution is found, return {-1, -1}
    return {-1, -1};
}

int main() {
    std::vector<int> arr = {2, 6, 5, 8, 11};
    int target = 14;
    std::vector<int> ans = twoSum(arr, target);

    // Print the result
    std::cout << "Indices of the two numbers are: [" << ans[0] << ", " << ans[1] << "]\n";

    return 0;
}


// Java Implementation for 2 Sum

import java.util.HashMap;

public class TwoSumUsingHashing {
    // Implementation of the Two Sum problem using HashMap
    public static int[] twoSum(int[] arr, int target) {
        // Create a HashMap to store numbers and their corresponding indices
        HashMap<Integer, Integer> numToIndex = new HashMap<>();

        // Iterate through the array
        for (int i = 0; i < arr.length; i++) {
            // Calculate the complement of the current number with respect to the target
            int complement = target - arr[i];

            // Check if the complement exists in the HashMap
            if (numToIndex.containsKey(complement)) {
                // If found, return the indices of the two numbers
                return new int[]{numToIndex.get(complement), i};
            }

            // Put the current number and its index into the HashMap
            numToIndex.put(arr[i], i);
        }

        // If no solution is found, return [-1, -1]
        return new int[]{-1, -1};
    }

    public static void main(String args[]) {
        int[] arr = {2, 6, 5, 8, 11};
        int target = 14;
        int[] ans = twoSum(arr, target);

        // Print the result
        System.out.println("Indices of the two numbers are: [" + ans[0] + ", " + ans[1] + "]");
    }
}


// Python Implementation for 2 Sum

# Implementation of the Two Sum problem using a dictionary (similar to HashMap)
def twoSum(arr, target):
    # Create a dictionary to store numbers and their corresponding indices
    num_to_index = {}

    # Iterate through the array
    for i, num in enumerate(arr):
        # Calculate the complement of the current number with respect to the target
        complement = target - num

        # Check if the complement exists in the dictionary
        if complement in num_to_index:
            # If found, return the indices of the two numbers
            return [num_to_index[complement], i]

        # Put the current number and its index into the dictionary
        num_to_index[num] = i

    # If no solution is found, return [-1, -1]
    return [-1, -1]

if __name__ == "__main__":
    arr = [2, 6, 5, 8, 11]
    target = 14
    ans = twoSum(arr, target)

    # Print the result
    print(f"Indices of the two numbers are: {ans}")


// JavaScript Implementation for 2 Sum

// Implementation of the Two Sum problem using a JavaScript object (similar to HashMap)
function twoSum(arr, target) {
    // Create an object to store numbers and their corresponding indices
    const numToIndex = {};

    // Iterate through the array
    for (let i = 0; i < arr.length; i++) {
        // Calculate the complement of the current number with respect to the target
        const complement = target - arr[i];

        // Check if the complement exists in the object
        if (numToIndex[complement] !== undefined) {
            // If found, return the indices of the two numbers
            return [numToIndex[complement], i];
        }

        // Put the current number and its index into the object
        numToIndex[arr[i]]

Code Explanation

Let’s understand above solution using example

Given an array, nums = [2,6,5,8,11], and a target value of 14:

  • For index 0, the number is 2. The complement is 14 - 2 = 12. Since 12 is not in the HashMap, we add 2 with its index 0 to the HashMap.
  • For index 1, the number is 6. The complement is 14 - 6 = 8. Since 8 is not in the HashMap, we add 6 with its index 1 to the HashMap.
  • For index 2, the number is 5. The complement is 14 - 5 = 9. Since 9 is not in the HashMap, we add 5 with its index 2 to the HashMap.
  • For index 3, the number is 8. The complement is 14 - 8 = 6. 6 is in the HashMap with index 1, so we return the indices [1, 3].

This approach is more efficient than the brute-force method as it only requires a single pass through the array, leading to a linear time complexity.

Complexity

Time Complexity: O(n) – The code iterates through the array once, and for each element, it performs constant-time operations on the HashMap.

Space Complexity: O(n) – In the worst case, the code may store all n elements in the HashMap.

3. Two Pointer Technique

Intuition

The two-pointer technique is a common approach to solve array-related problems in a more efficient manner. The idea is to maintain two pointers, typically starting at the beginning and end of the array, and move them towards each other based on certain conditions. For the Two Sum problem, this technique requires the array to be sorted. If the array isn’t sorted, we can sort it but we’d also need to keep track of the original indices.

Algorithm

  1. Sort the array: If the array isn’t sorted, sort it but keep track of the original indices.
  2. Initialise two pointers: Now we initialise two pointers: l = 0 and r = n – 1.
  3. Check the sum of the elements at the two pointers:
    • If arr[left] + arr[right] == target, return the indices of these two numbers.
    • If the arr[left] + arr[right] < target, move the left pointer one step to the right.
    • If the arr[left] + arr[right] > target, move the right pointer one step to the left.
  4. Repeat the above step until the left pointer is less than the right pointer.
  5. No pair found: If the pointers cross each other without finding a pair that sums up to the target, return [-1, -1].

Code Implementation

// C Implementation for 2 Sum

#include <stdio.h>
#include <stdlib.h>

// Implementation of the Two Sum problem using two-pointer technique
int* twoSum(int arr[], int n, int target) {

    // Create an array of indices to keep track of the original indices
    int* indices = (int*)malloc(n * sizeof(int));

    // Initialize the indices array with values 0 to n-1
    for (int i = 0; i < n; i++) {
        indices[i] = i;
    }

    // Sort the indices array based on the values in the input array using a custom comparator
    qsort(indices, n, sizeof(int), compareIndices);

    // Initialize two pointers, left and right
    int left = 0, right = n - 1;

    // Move the pointers towards each other
    while (left < right) {
        int sum = arr[indices[left]] + arr[indices[right]];

        if (sum == target) {
            // If the sum matches the target, return the indices of the two numbers
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = indices[left];
            result[1] = indices[right];
            free(indices); // Free the allocated memory
            return result;
        } else if (sum < target) {
            // If the sum is less than the target, move the left pointer to the right
            left++;
        } else {
            // If the sum is greater than the target, move the right pointer to the left
            right--;
        }
    }

    free(indices); // Free the allocated memory
    // If no solution is found, return {-1, -1}
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = -1;
    result[1] = -1;
    return result;
}

// Custom comparator function for sorting indices based on values in the input array
int compareIndices(const void* a, const void* b) {
    return arr[*(int*)a] - arr[*(int*)b];
}

int main() {
    int arr[] = {2, 6, 5, 8, 11};
    int target = 14;
    int* ans = twoSum(arr, 5, target);

    // Print the result
    printf("Indices of the two numbers are: [%d, %d]\n", ans[0], ans[1]);

    // Free the allocated memory
    free(ans);
    return 0;
}


// C++ Implementation for 2 Sum

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

// Implementation of the Two Sum problem using two-pointer technique
std::vector<int> twoSum(std::vector<int>& arr, int target) {
    // Create a vector of indices to keep track of the original indices
    std::vector<int> indices(arr.size());

    // Initialize the indices vector with values 0 to n-1
    for (int i = 0; i < arr.size(); i++) {
        indices[i] = i;
    }

    // Sort the indices vector based on the values in the input vector using a custom comparator
    std::sort(indices.begin(), indices.end(), [&](int a, int b) {
        return arr[a] < arr[b];
    });

    // Initialize two pointers, left and right
    int left = 0, right = arr.size() - 1;

    // Move the pointers towards each other
    while (left < right) {
        int sum = arr[indices[left]] + arr[indices[right]];

        if (sum == target) {
            // If the sum matches the target, return the indices of the two numbers
            return {indices[left], indices[right]};
        } else if (sum < target) {
            // If the sum is less than the target, move the left pointer to the right
            left++;
        } else {
            // If the sum is greater than the target, move the right pointer to the left
            right--;
        }
    }

    // If no solution is found, return {-1, -1}
    return {-1, -1};
}

int main() {
    std::vector<int> arr = {2, 6, 5, 8, 11};
    int target = 14;
    std::vector<int> ans = twoSum(arr, target);

    // Print the result
    std::cout << "Indices of the two numbers are: [" << ans[0] << ", " << ans[1] << "]\n";

    return 0;
}

// Java Implementation for 2 Sum

import java.util.Arrays;
import java.util.Comparator;

public class TwoSumUsingTwoPointer {
    // Implementation of the Two Sum problem using two-pointer technique
    public static int[] twoSum(int[] arr, int target) {
        // Create an array of indices to keep track of the original indices
        Integer[] indices = new Integer[arr.length];
        
        // Initialize the indices array with values 0 to n-1
        for (int i = 0; i < arr.length; i++) {
            indices[i] = i;
        }

        // Sort the indices array based on the values in the input array
        Arrays.sort(indices, Comparator.comparingInt(i -> arr[i]));

        // Initialize two pointers, left and right
        int left = 0, right = arr.length - 1;

        // Move the pointers towards each other
        while (left < right) {
            int sum = arr[indices[left]] + arr[indices[right]];

            if (sum == target) {
                // If the sum matches the target, return the indices of the two numbers
                return new int[]{indices[left], indices[right]};
            } else if (sum < target) {
                // If the sum is less than the target, move the left pointer to the right
                left++;
            } else {
                // If the sum is greater than the target, move the right pointer to the left
                right--;
            }
        }

        // If no solution is found, return [-1, -1]
        return new int[]{-1, -1};
    }

    public static void main(String args[]) {
        int[] arr = {2, 6, 5, 8, 11};
        int target = 14;
        int[] ans = twoSum(arr, target);

        // Print the result
        System.out.println("Indices of the two numbers are: [" + ans[0] + ", " + ans[1] + "]");
    }
}


// Python Implementation for 2 Sum

# Implementation of the Two Sum problem using two-pointer technique
def twoSum(arr, target):
    # Create a list of indices to keep track of the original indices
    indices = list(range(len(arr)))

    # Sort the indices list based on the values in the input list
    indices.sort(key=lambda i: arr[i])

    # Initialize two pointers, left and right
    left, right = 0, len(arr) - 1

    # Move the pointers towards each other
    while left < right:
        sum = arr[indices[left]] + arr[indices[right]]

        if sum == target:
            # If the sum matches the target, return the indices of the two numbers
            return [indices[left], indices[right]]
        elif sum < target:
            # If the sum is less than the target, move the left pointer to the right
            left += 1
        else:
            # If the sum is greater than the target, move the right pointer to the left
            right -= 1

    # If no solution is found, return [-1, -1]
    return [-1, -1]

if __name__ == "__main__":
    arr = [2, 6, 5, 8, 11]
    target = 14
    ans = twoSum(arr, target)

    # Print the result
    print(f"Indices of the two numbers are: {ans}")


// JavaScript Implementation for 2 Sum

// Implementation of the Two Sum problem using two-pointer technique
function twoSum(arr, target) {
    // Create an array of indices to keep track of the original indices
    const indices = [...Array(arr.length).keys()];

    // Sort the indices array based on the values in the input array
    indices.sort((a, b) => arr[a] - arr[b]);

    // Initialize two pointers, left and right
    let left = 0, right = arr.length - 1;

    // Move the pointers towards each other
    while (left < right) {
        const sum = arr[indices[left]] + arr[indices[right]];

        if (sum === target) {
            // If the sum matches the target, return the indices of the two numbers
            return [indices[left], indices[right]];
        } else if (sum < target) {
            // If the sum is less than the target, move the left pointer to the right
            left++;
        } else {
            // If the sum is greater than the target, move the right pointer to the left
            right--;
        }
    }

    // If no solution is found, return [-1, -1]
    return [-1, -1];
}

const arr = [2, 6, 5, 8, 11];
const target = 14;
const ans = twoSum(arr, target);

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

Code Explanation

Let’s undertstand the code via example

Given an array, nums = [2,6,5,8,11], and a target value of 14:

  • After sorting, the array becomes [2,5,6,8,11].
  • Initialize left pointer at index 0 and right pointer at index 4.
  • The sum of elements at left and right is 2 + 11 = 13, which is less than 14. So, move the left pointer one step to the right.
  • Now, left is at index 1 and right is at index 4. The sum is 5 + 11 = 16, which is greater than 14. So, move the right pointer one step to the left.
  • Now, left is at index 1 and right is at index 3. The sum is 5 + 8 = 13, which is less than 14. So, move the left pointer one step to the right.
  • Now, left is at index 2 and right is at index 3. The sum is 6 + 8 = 14, which is equal to the target. So, return the original indices of these numbers, which are [1, 3].

The two-pointer approach is efficient for sorted arrays, leading to a linear time complexity. However, if the array isn’t sorted, the time complexity would be dominated by the sorting step.

Complexity

Time Complexity: O(nlogn) – The code first sorts the indices array, which takes O(nlogn) time due to the sorting algorithm used. After sorting, it iterates through the array once, which takes O(n) time. Therefore, the overall time complexity is dominated by the sorting step.

Space Complexity: O(n) – The code uses an array of indices, which takes O(n) additional space.

I hope You liked the post ?. For more such posts, ? subscribe to our newsletter. Try out our free resume checker service where our Industry Experts will help you by providing resume score based on the key criteria that recruiters and hiring managers are looking for.

90% of Tech Recruiters Judge This In Seconds! 👩‍💻🔍

Don’t let your resume be the weak link. Discover how to make a strong first impression with our free technical resume review!

Claim Your Free Review

Related Articles

Hello World! in C HackerRank Solution 

March 4, 2024

Problem Statement In this challenge, we will learn some basic concepts of C that will get you started with the language. You will need to use the same syntax to

Java
Data Structures And Algorithms
Interview Questions
System Design

Why Aren’t You Getting Interview Calls? 📞❌

It might just be your resume. Let us pinpoint the problem for free and supercharge your job search. 

Get My Free Resume Review

TeachingBee

Be a learner everyday

Teaching bee is a group of industrial professionals with aim to build the required skillset of students using practical hands On. All of our teachers have more than four years of industrial experience in there respective domain therefore having required knowledge not only about the subject but also about the requirements of software industry.

  • help@teachingbee.in
Explore
Recent Posts
[instagram-feed]
Newsletter

Don’t miss out! Subscribe now

Log In

Privacy Policy