Problem Statement
This is an easy algorithm question that appears on Leetcode. In this article we’re gonna solve the given question in two ways. First is bruteforce solution and second is more effective way. According to problem statement it gives us an array of integers nums and an integer target, and then they want us from to return indices of the two numbers such that they add up to target. We may assume that each input has exactly one solution, and we may not use the same element twice. We can return the answer in any order.
Examples
Input: nums=[2,7,11,15], target = 9
Output: [0, 1]
Explanation: Because nums[0] + nums[1] == 9, we can return [0,1]
Input: nums=[3,2,4], target = 6
Output: [1, 2]
Input: nums=[3,3], target = 6
Output: [0, 1]
Constraints
- 2 <= nums.length <= 10000
- -1,000,000,000 <= nums[i] <= 1,000,000,000
- -1,000,000,000 <= target <= 1,000,000,000
- Only one valid answer exists
And in this problem they want us to come up with an algorithm that does better then O(n) square.
So lets discuss the two solution.
Solution 1 (Brute Force)
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
for(int j = i + 1; i < nums.length; j++) {
if(nums[i] + nums[j] == target) {
return new int[] {i ,j};
}
}
}
throw new IllegalStateException("no pair found");
}
}
In this solution we iterate through the nums array twice and every time we sum the current number and number after the current number. And then compare sum value with the target. If they are equal we return a new array with index of those two number.
Solution 2
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> indexMap = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
int kalan = target - nums[i];
if(indexMap.containsKey(kalan)) {
return new int[] {indexMap.get(kalan), i};
}
indexMap.put(nums[i], i);
}
throw new IllegalStateException("no pair found");
}
}
In this solution, instead of iterating the nums array twice, we create an HashMap to store index of numbers in the nums array. We iterate the nums array one time. In the loop we calculate the complement of the current number by extracting current number from the target value. And then we check the map if it contains the complement. If it is then we assume that we found a pair. If map does not contains the complement then we put the current number with it’s index to the map. After the loop is finished, if we still couldn’t found a pair, we throw an illegal state exception.
In this post i tried to explain leetcode two sum question. I hope it is useful for you. Thanks for reading, see you next time :)
