Find the Indices of Two Numbers in an Array That Add Up to a Target

Given an array of integers nums and an integer target, find the indices of two elements within the given array that add up to the given target and return them as an array. Here, we should not use the same element twice, and exactly one pair of numbers in nums adds up to the target. This is the Two Sum problem on LeetCode.

Constraints:-

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

For example, given nums = [4, 5, 6, 3] and target = 8, then indices = [1,3] because nums[1] + nums[3] = 8.

We are going to solve this problem using Java with different approaches, discuss complexity, and understand the logic used in each approach.

Brute Force Approach

In this approach, we simply run two loops from 0 to nums.length, one inside the other, and compare each pair with the target. If the sum and target are the same, we return the indices.

public int[] twoSum(int[] nums, int target) {
    int n = nums.length;
    int indices[] = new int[2];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(nums[i]+nums[j]==target && i!=j){
               indices[0]=i;
               indices[1]=j;
            }
        }
    }
    return indices;
}

This approach takes fixed space and has O(n²) time complexity. It is the worst approach because we compare the same pair multiple times.

For example, if nums = [1, 2, 3, 4], then the pairs we compare are at indices [{0,1}, {0,2}, {0,3}, {1,0}, {1,2}, {1,3}, {2,0}, {2,1}, {2,3}, {3,0}, {3,1}, {3,2}], but the loops run 16 times, where duplicate pairs are eliminated by i != j. We can see pairs {0,1} & {1,0}, {0,2} & {2,0}, and so on—only one of them needs to be compared.

Duplicate Pair-Free Approach

In this approach, we again run two loops, but this time, the outer loop runs n-1 times, and the inner loop runtime decreases from n-1 to 1 as i increases. This way, we eliminate all duplicate pairs and only use unique pairs.

In the previous example,

• In the 1st iteration, the inner loop compares [{0,1}, {0,2}, {0,3}]
  
• In the 2nd iteration, it compares [{1,0}, {1,2}, {1,3}]
• In the 3rd iteration, it compares [{2,0}, {2,1}, {2,3}], and so on.

We can see that as i increases, the number of duplicate pairs that would have been compared in the inner loop increases. For example, {1,0} in the second iteration was already compared as {0,1} in the first iteration. Similarly, [{2,0}, {2,1}] in the third iteration was already compared as {0,2} in the first and {1,2} in the second iterations.

From this analysis, we can say that we need to start the inner loop just after the outer loop index and run the outer loop up to index n-2, because when i is n-1, then j becomes n, which is out of bounds.

    public int[] twoSum(int[] nums, int target) {
        for(int i=1;i<nums.length-1;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    return new int[] {i,j};
                }
            }
        }
        return new int[] {};
    }

This approach also takes fixed space but less than the first approach and has O(n²) time complexity according to Big-O notation, but here the loop runs exactly (n-1) * n / 2 times.

In the worst case, when n = 10,000,

• The first approach’s loop runs 100,000,000 times
• The second approach’s loop runs 49,995,000 times, which is less than half of the first approach.

This is the best approach because it compares only the required pairs without using extra space.

If we modify the code slightly like this, its efficiency increases to the most optimal solution according to LeetCode submissions:

public int[] twoSum(int[] nums, int target) {
    for(int i = 1; i < nums.length; i++) { 
        for(int j = i; j < nums.length; j++) { 
            if(nums[j] + nums[j - i] == target) { 
                return new int[] {j - i, j}; 
            }
        }
    }
    return new int[] {};
}

Both functions above achieve the same result but in different ways. The first function iterates from left to right, eliminating duplicates, while the second function iterates slightly randomly.

HashMap Approach

In this approach, we use a HashMap to store numbers with their indices so that we have quick access to the indices of all previous numbers.

When we have access to indices of all previous numbers at a particular iteration of the loop, we subtract the current number from the target, and the result is the number we are looking for. If it is available in the HashMap, we simply return an array containing the current index and the index from the HashMap. Otherwise, we store the current number as a key and its index as a value.

public static int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> previous = new HashMap<>();
    for(int i=0;i<nums.length;i++){
        int number = nums[i];
        int required = target-number;
        if(previous.containsKey(required)){
            return new int[]{i,previous.get(required)};
        }else previous.put(number,i);
    }
    return new int[] {};
}

So this is how we solve this problem with different approaches. I hope you find this post helpful, informative, and enjoyable.

Happy Coding!