Two Sum | Leetcode # 1 | Easy

In this post I will discuss the solution to the leetcode problem — Two Sum.

Problem:

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.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

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

Solutions:

Approach 1:

The first solution that comes naturally to the mind is to check every number in the array with the rest of numbers in the array and check if their sum is equal to the target. The solution looks as follows—

public int[] twoSum(int[] nums, int target) {
  for (int i = 0; i < nums.length; 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 is more of a brute-force solution. As you can see, it involves 2 for loops and hence the time complexity of this algorithm is O(n²)

Approach 2:

Let’s see if we can do better than the first approach which if the input size grows, can take a long time to find the result.

We can do it in linear time but we need to compromise on the space a little bit. If we keep a map of numbers and their indices we can easily find the output in 1 iteration of the array i.e. O(n). The solution looks like this —

public int[] twoSum(int[] nums, int target) {
  Map<Integer, Integer> numToIndexMap = new HashMap<>();
  for (int i = 0; i < nums.length; i++) {
    int complement = target - nums[i];
    if (numToIndexMap.get(complement) != null) {
      return new int[]{numToIndexMap.get(complement), i};
    }
    numToIndexMap.put(nums[i], i);
  }
  return new int[]{};
}

Here is how the algorithms works —

1. Create a map called numToIndexMap which stores the number and it’s index in the array.
2. Iterate over the input array and for every element in the array follow steps #3 to #5
3. Subtract the number from target and store it in the variable complement
4. If there is a key in the numToIndexMap for the complement , that means we have a pair which sums up to the target and return it as the output.
5. Otherwise, store the number and it’s index in the numToIndexMap
6. After iterating the whole array, if we couldn’t return the result, return an empty array.

Hope this helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems