Hello coders! Today we will be discussing the various solutions to the Two Sum LeetCode Problem.
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.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: 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 <= 104-109Ā <= nums[i] <= 109-109<= target <= 109Only one valid answer exists.
Approach 1: Brute Force
In this problem we're trying to find two numbers from the given array that add up to a target - so why don't we try all possible solutions by adding every number in the array to all the other numbers?
This clearly won't be the most optimal approach, but at least it is a working solution.
Implementation
1public int[] twoSum(int[] nums, int target) {
2 if (nums == null) {
3 return new int[]{-1, -1};
4 }
5 for (int i = 0; i < nums.length - 1; i++) {
6 for (int j = i + 1; j < nums.length; j++) {
7 if (nums[i] + nums[j] == target) {
8 return new int[]{i, j};
9 }
10 }
11 }
12 return new int[]{-1, -1};
13}
Time Complexity
Let the number of elements in the array be n. This means that:
The first loop will loop through
(n - 1)elements (excluding the element itself)The second loop will loop through
(n - 2)elements (excluding the element itself and the previous element)The third loop will loop through
(n - 3)elements (excluding the element itself and the previous elements)etc...
So the time complexity can be modeled with the equation [(n - 1) + (n - 2) + (n - 3) ... + 2 + 1] which can be simplified as (n * (n - 1)) / 2 using the sum of natural numbers formula. Simplifying this gives us (n2/2 - n/2). Remember, big O notation allows you to drop the constants - so we can say the time complexity is O(n2).
Space Complexity
Since we aren't using any additional data structures, the space complexity is constant, or O(1).
Approach 2: Using a Map
In this problem we are looking to solve the equation array[a] + array[b] = target where a and b are the solution indices. This equation can be rewritten as target - array[a] = array[b] - meaning when we get to an element, we are looking for the value target - array[a].
Using this equation, we can iterate through every element and check for it's "complement", or in other words, the number that will solve the equation target - array[a] = array[b] where a is the current index. More simply put, we're saying I am at index a with the value array[a], is there a number that I have seen that equals target - array[a]?
For this, we need to keep track of all the numbers we have seen as well as the index that number is at. A map (or dictionary, depending on the coding language you are using) is the perfect data structure for this use case.
Implementation
1import java.util.HashMap;
2import java.util.Map;
3
4public int[] twoSum(int[] nums, int target) {
5 if (nums == null) {
6 return new int[]{-1, -1};
7 }
8 Map<Integer, Integer> map = new HashMap<>();
9 for (int i = 0; i < nums.length; i++) {
10 if (map.containsKey(target - nums[i])) {
11 return new int[]{map.get(target - nums[i]), i};
12 }
13 map.put(nums[i], i);
14 }
15 return new int[]{-1, -1};
16}
Time Complexity
If the number of elements in the array is n, in the worst case we are visiting n elements. We are simply visiting every element at most one time, meaning the time complexity is linear, or O(n).
Space Complexity
In this solution, we are using an auxiliary data structure to keep track of the elements and their index. This means that in the worst case, we are storing n elements, meaning the space complexity is linear, or O(n).
Conclusion
The two sum problem can be solved in O(n) time and O(n) space. All the code can be found on my github - if you found this helpful, please leave the repo a star!
Recommended Blogs