Leetcode #1 - Two Sum

 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.

Bruteforce Approach:

The idea here is that we have to find the two values from the array whose sum is equal to target. the brute force approach would be to loop through all the elements in the array and another nested loop to loop from the next elements onwards.

Code:

class Solution {
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[] {0,0};
}
}

Time Complexity: O(n*n)

Space Complexity: O(1)

As we can see, in the brute force approach, the time complexity is O(n*n). We can refine our solution and use the extra linear space and improve the time complexity to linear time.

Optimal Approach:

In this approach, we will be using a HashMap to store the elements with arrayValue as Key and index as value. We will loop through all the elements of the array, and for each element, we check if the map already contains `target - currentValue`. If it exists we return the value from the Map and the current index, else we add the current value into the map along with its index.

Code:

class Solution { public int[] twoSum(int[] nums, int target) { HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); int[] ans = new int[2]; for(int i=0; i< nums.length; i++) { if(hm.containsKey(target - nums[i])) { ans[0] = hm.get(target - nums[i]); ans[1] = i; } else { hm.put(nums[i], i); } } return ans; } }

Time Complexity: O(n)

Space Complexity: O(n)

LeetCode link: https://leetcode.com/problems/two-sum/