# LeetCode #1 - Two Sum

Hello happy people 👋! Today we are going to discuss the very first problem on the LeetCode.

## Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to 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.

### Constraints

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

## Analysis

So, we have to find two numbers among all the numbers in an array such that when they are added, they give us a third number equals to target.

For e.g.,

If nums = [2,7,11,15] and target = 9,
then we should return 2 and 7 because 2 + 7 = 9

In simpler words, we need to find -

c = a + b
where,
c => target
a and b => elements from the given array

Also, the given constraints suggest that there is only ONE valid answer along with the ranges of the elements in the array and the target.

## Approach

After we have analyzed our problem, now it’s time to think about the solution.

### Approach #1

The first solution that comes to mind is -

• Take one element
• Add this element with every other element
• After adding, compare the sum with the given target
• If the sum is equal to the target, return the indices of these two elements
• If the sum is not equal to the target, we check for the next pair

Pretty simple, eh 😉? Let’s analyze the time and space complexities.

• Time Complexity

Let’s say the array has n elements then -

For 1st element - we will check for (n - 1) elements
For 2nd element - we will check for (n - 2) elements
For 3rd element - we will check for (n - 3) elements
and so on...

Thus, the total iterations would be - [(n - 1) + (n - 2) + (n - 3) + ... + 2 + 1]

If we simplify the above expression we will get -

n * (n - 1) / 2 = n2 - 2n ≈ n2

Thus, our time complexity would be - O(n2).

• Space Complexity

Since we are not using any extra data structure hence our space complexity would be O(1).

This approach is simple and intuitive but it takes quadratic time which is bad for large inputs. Let’s see if we have any efficient approach to solve this problem. As a matter of fact, we do 😄!

### Approach #2

In the earlier approach, we did what naturally came to us. But let’s try to really think through this problem. Hmm… 🤔

When we were analyzing the problem, we came across the following equation

c = a + b

but can we write the above equation as -

b = c - a

Of course we can. We are mathematicians after all 😁.

The benefit of writing this equation is that now we can iterate through the array only once and calculate the difference of target (c) and the current element (a) and find the other element (b). The idea is as follows -

• Loop through the array
• Check if we have encountered the current element before
• If we have, we will return the index of this element and the index of the difference of the target and the current element. We will only encounter this element before only if we have saved the difference of target and the element which when added to the current element gives the target itself. This is confusing I know but once it clicks, it’s very obvious.
• If we haven’t, the we will save the difference of the target and current element.
• Repeat the process

Since we need to store our difference, we need a data structure which can store the difference and its corresponding index. So what do you think, which data structure can help us? Of course, we need a Map where we will store the difference as key and the corresponding index as value.

• Time Complexity

Since we are iterating the array only once, the time complexity would be O(n).

• Space Complexity

Since we need a Map of the size of the array, the space complexity would be O(n).

## Code

Now we have an approach to solve this problem, let’s write some code -

### Java

package org.redquark.tutorials.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class TwoSum {

public int[] twoSum(int[] nums, int target) {
// Array to store result
int[] result = new int[2];
// This map will store the difference and the corresponding index
Map<Integer, Integer> map = new HashMap<>();
// Loop through the entire array
for (int i = 0; i < nums.length; i++) {
// If we have seen the current element before
// It means we have already encountered the other number of the pair
if (map.containsKey(nums[i])) {
// Index of the current element
result[0] = i;
// Index of the other element of the pair
result[1] = map.get(nums[i]);
}
// If we have not seen the current before
// It means we have not yet encountered any number of the pair
else {
// Save the difference of the target and the current element
// with the index of the current element
map.put(target - nums[i], i);
}
}
return result;
}
}

### Python

from typing import List

def twoSum(nums: List[int], target: int) -> List[int]:
# List to store results
result = []
# Dictionary to store the difference and its index
index_map = {}
# Loop for each element
for i, n in enumerate(nums):
# Difference which needs to be checked
difference = target - n
if difference in index_map:
result.append(i)
result.append(index_map[difference])
break
else:
index_map[n] = i
return result

### JavaScript

var twoSum = function (nums, target) {
// Array to store the result
result = [];
// Map to store the difference and its index
index_map = new Map();
// Loop for each element in the array
for (let i = 0; i < nums.length; i++) {
let difference = target - nums[i];
if (index_map.has(difference)) {
result[0] = i;
result[1] = index_map.get(difference);
break;
} else {
index_map.set(nums[i], i);
}
}
return result;
};

### Kotlin

package org.redquark.tutorials.leetcode

fun twoSum(nums: IntArray, target: Int): IntArray {
// Array to store result
val result = IntArray(2)
// This map will store the difference and the corresponding index
val map: MutableMap<Int, Int> = HashMap()
// Loop through the entire array
for (i in nums.indices) {
// If we have seen the current element before
// It means we have already encountered the other number of the pair
if (map.containsKey(nums[i])) {
// Index of the current element
result[0] = i
// Index of the other element of the pair
result[1] = map[nums[i]]!!
break
} else {
// Save the difference of the target and the current element
// with the index of the current element
map[target - nums[i]] = i
}
}
return result
}

## Conclusion

I hope you liked this post. Here, we solved the very first problem on LeetCode in O(n) time and O(n) space.

You can find the complete source code on GitHub. If you find it useful, consider giving it a star ⭐.

• Java
• Python
• JavaScript