Two Sum – Day 6 | 100 Days of Code

0
245
Day 7 - Two Sum featured image
- Advertisement -

Welcome to Day 6 of 100 Days of Code where we solve the most frequently asked Easy level Array problem – Two Sum. Let us look at the problem:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

For Eg, If we were given an int array a = [3,2,4] and target = 6, then we know that 2+4 = 6 whose indices are 1 and 2 in the given array a. Hence we will return [1,2].

Here’s the Leetcode link for the same:

https://leetcode.com/problems/two-sum/description/

Now let us look into the solution

class Solution {
public int[] twoSum(int[] nums, int target) {
// Hashmap to store remainder as key and current index as value
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])) {
// checks if map already contains value
return new int[]{i, map.get(nums[i])};
} else {
// putting remainder and current index in map
map.put(target – nums[i], i);
}
}
return null;
}
}
view raw TwoSum.java hosted with ❤ by GitHub

We are using HashMap in the above problem to store the target – nums[i] as key and the current index as value.

Time and space Complexity:

Since we need to go through all the values in nums[], the time complexity will be O(N).

As we are using HashMap as additional Data Structure and in worst case we might need to store all the values, space complexity will be O(N).

Hope you enjoyed Day 6 Problem of our Coderefer DSA Sheet. Follow our instagram for brief informative reels on the sheet and let us connect on our next article on Day 7.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.