Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid First Name
*Invalid Last Name
*Invalid Phone Number
By sharing your contact details, you agree to our privacy policy.
Select your webinar time
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

2 Sum In An Array Problem

2 Sum In An Array Problem Statement

Given an array and a target number, find the indices of the two values from the array that sum up to the given target number.

Example One

{
"numbers": [5, 3, 10, 45, 1],
"target": 6
}

Output:

[0, 4]

Sum of the elements at index 0 and 4 is 6.

Example Two

{
"numbers": [4, 1, 5, 0, -1],
"target": 10
}

Output:

[-1, -1]

Notes

  • The function returns an array of size two where the two elements specify the input array indices whose values sum up to the given target number.
  • In case when no answer exists, return an array of size two with both values equal to -1, i.e., [-1, -1].
  • In case when multiple answers exist, you may return any of them.
  • The order of the returned indices does not matter.
  • A single index cannot be used twice.

Constraints:

  • 2 <= array size <= 105
  • -105 <= array elements <= 105
  • -105 <= target number <= 105
  • Array can contain duplicate elements.

We provided two solutions.

Throughout this editorial, we will refer to the input array as numbers, its size as numbers_size and the target integer as target.

2 Sum In An Array Solution 1: Brute Force

A brute force is to run two nested loops and check the sum of every pair of elements present in the array. If any pair sums up to the target, we will return the indices of that pair of elements.

Otherwise, we will return [-1, -1].

Time Complexity

O((numbers_size)2).

Total number of possible pairs: (numbers_size * (numbers_size - 1)) / 2.

Auxiliary Space Used

O(1).

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In An Array Solution 1: Brute Force

    /*
    * Asymptotic complexity in terms of the size of \`numbers\` = \`n\`:
    * Time: O(n^2).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static ArrayList<Integer> two_sum(ArrayList<Integer> numbers, Integer target) {
        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < numbers.size(); i++) {
            // For every element in numbers we find it complementary pair that sum to
            // target.
            for (int j = i + 1; j < numbers.size(); j++) {
                if (numbers.get(i) + numbers.get(j) == target) {
                    result.add(i);
                    result.add(j);
                    return result;
                }
            }
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

2 Sum In An Array Solution 2: Hashing

While iterating through the array, let say we are at a number current. Being at this number, we need to check whether target - current has occurred at a smaller index in the array or not.

To check the occurrence of target - current, one way is to run another loop on the array to linearly search for that element. But as discussed above, this won’t be very efficient.

We can check whether target - current has previously occurred in the array or not in O(1) time using hashing. We will maintain a hashmap which stores the index of an element present in the array and will keep building this hashmap as we iterate through the array. Now, being at any number current, we will use this hashmap to check whether target - current has previously occurred in the array or not. If it has occurred, we will store the current index and the index of target - current in an array of size two and return it.

In case we didn’t find any such pair after the complete traversal of the array, we will return [-1, -1].

Time Complexity

O(numbers_size).

We iterate through each element in the numbers array exactly once and are doing a constant amount of work in each iteration.

Auxiliary Space Used

O(numbers_size).

At most, we will be storing all the elements in the hashmap.

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(numbers_size).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In An Array Solution 2: Hashing

    /*
    * Asymptotic complexity in terms of the size of \`numbers\` = \`n\`:
    * Time: O(n).
    * Auxiliary space: O(n).
    * Total space: O(n).
    */

    static ArrayList<Integer> two_sum(ArrayList<Integer> numbers, Integer target) {
        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        // This Map stores the array element as Key and its index as Value.
        HashMap<Integer, Integer> array_index = new HashMap<Integer, Integer>();

        for (int i = 0; i < numbers.size(); i++) {
            int current = numbers.get(i);
            int required = target - current; // complementary target pair
            if (array_index.containsKey(required)) {
                result.add(array_index.get(required)); // store index of required in result
                result.add(i);
                return result;
            }
            // Add every element to map after checking for required.
            // This ensures that element does not match itself (indices to be unique).
            array_index.put(current, i);
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

We hope that these solutions to the 2 Sum in an Array problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

‍To learn more, register for the FREE webinar.

Try yourself in the Editor

Note: Input and Output will already be taken care of.

2 Sum In An Array Problem

2 Sum In An Array Problem Statement

Given an array and a target number, find the indices of the two values from the array that sum up to the given target number.

Example One

{
"numbers": [5, 3, 10, 45, 1],
"target": 6
}

Output:

[0, 4]

Sum of the elements at index 0 and 4 is 6.

Example Two

{
"numbers": [4, 1, 5, 0, -1],
"target": 10
}

Output:

[-1, -1]

Notes

  • The function returns an array of size two where the two elements specify the input array indices whose values sum up to the given target number.
  • In case when no answer exists, return an array of size two with both values equal to -1, i.e., [-1, -1].
  • In case when multiple answers exist, you may return any of them.
  • The order of the returned indices does not matter.
  • A single index cannot be used twice.

Constraints:

  • 2 <= array size <= 105
  • -105 <= array elements <= 105
  • -105 <= target number <= 105
  • Array can contain duplicate elements.

We provided two solutions.

Throughout this editorial, we will refer to the input array as numbers, its size as numbers_size and the target integer as target.

2 Sum In An Array Solution 1: Brute Force

A brute force is to run two nested loops and check the sum of every pair of elements present in the array. If any pair sums up to the target, we will return the indices of that pair of elements.

Otherwise, we will return [-1, -1].

Time Complexity

O((numbers_size)2).

Total number of possible pairs: (numbers_size * (numbers_size - 1)) / 2.

Auxiliary Space Used

O(1).

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(1).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In An Array Solution 1: Brute Force

    /*
    * Asymptotic complexity in terms of the size of \`numbers\` = \`n\`:
    * Time: O(n^2).
    * Auxiliary space: O(1).
    * Total space: O(n).
    */

    static ArrayList<Integer> two_sum(ArrayList<Integer> numbers, Integer target) {
        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        for (int i = 0; i < numbers.size(); i++) {
            // For every element in numbers we find it complementary pair that sum to
            // target.
            for (int j = i + 1; j < numbers.size(); j++) {
                if (numbers.get(i) + numbers.get(j) == target) {
                    result.add(i);
                    result.add(j);
                    return result;
                }
            }
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

2 Sum In An Array Solution 2: Hashing

While iterating through the array, let say we are at a number current. Being at this number, we need to check whether target - current has occurred at a smaller index in the array or not.

To check the occurrence of target - current, one way is to run another loop on the array to linearly search for that element. But as discussed above, this won’t be very efficient.

We can check whether target - current has previously occurred in the array or not in O(1) time using hashing. We will maintain a hashmap which stores the index of an element present in the array and will keep building this hashmap as we iterate through the array. Now, being at any number current, we will use this hashmap to check whether target - current has previously occurred in the array or not. If it has occurred, we will store the current index and the index of target - current in an array of size two and return it.

In case we didn’t find any such pair after the complete traversal of the array, we will return [-1, -1].

Time Complexity

O(numbers_size).

We iterate through each element in the numbers array exactly once and are doing a constant amount of work in each iteration.

Auxiliary Space Used

O(numbers_size).

At most, we will be storing all the elements in the hashmap.

Space Complexity

O(numbers_size).

Space used for input: O(numbers_size).

Auxiliary space used: O(numbers_size).

Space used for output: O(1).

So, total space complexity: O(numbers_size).

Code For 2 Sum In An Array Solution 2: Hashing

    /*
    * Asymptotic complexity in terms of the size of \`numbers\` = \`n\`:
    * Time: O(n).
    * Auxiliary space: O(n).
    * Total space: O(n).
    */

    static ArrayList<Integer> two_sum(ArrayList<Integer> numbers, Integer target) {
        // A list to store the pair of indices that adds to target.
        ArrayList<Integer> result = new ArrayList<Integer>();

        // This Map stores the array element as Key and its index as Value.
        HashMap<Integer, Integer> array_index = new HashMap<Integer, Integer>();

        for (int i = 0; i < numbers.size(); i++) {
            int current = numbers.get(i);
            int required = target - current; // complementary target pair
            if (array_index.containsKey(required)) {
                result.add(array_index.get(required)); // store index of required in result
                result.add(i);
                return result;
            }
            // Add every element to map after checking for required.
            // This ensures that element does not match itself (indices to be unique).
            array_index.put(current, i);
        }

        // If no such pair of indices exist, add -1, -1 to list.
        result.add(-1);
        result.add(-1);
        return result;
    }

We hope that these solutions to the 2 Sum in an Array problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

‍To learn more, register for the FREE webinar.

Worried About Failing Tech Interviews?

Attend our free webinar to amp up your career and get the salary you deserve.

Hosted By
Ryan Valles
Founder, Interview Kickstart
Accelerate your Interview prep with Tier-1 tech instructors
360° courses that have helped 14,000+ tech professionals
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts