# Two Sum Problem - Leet Code Solution

July 08, 2019

## Problem Statement

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].``````

## Solution

### Brute force solution, O(n^2)

Simply iterate over array 2 times, and look if the sum equals to target.

``````public int[] twoSum(int[] nums, int target) {
int l = nums.length;
for (int i=0; i<l; i++) {
for (int j=i+1; j<l; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}

return null;
}``````

### Optimized approach, using HashMap/HashSet

Whenever this kind of problem comes, one thing came in mind is using HashSet. But, this problem is not asking you to return the values that sum upto a target value. It is asking you to return indexes of numbers.

So, you have to maintain a HashMap<Integer, Integer>, which Key is the number itself, and value is its index in the original array.

HashMap has the property of searching its key and value in O(1).

While iterating, we just have to check whether HashMap has the remaining difference. If its there, its a match. Else, keep a copy of this value and index in HashMap.

For this purpose, we are keeping a copy of array values and its index into a HashMap.

``````public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashMap = new HashMap<>();
int l = nums.length;
for (int i=0; i<l; i++) {
int pairValue = target-nums[i];
if (hashMap.containsKey(pairValue)) {
return new int[]{i, hashMap.get(pairValue)};
}

if (!hashMap.containsKey(nums[i])) {
hashMap.put(nums[i], i);
}
}

return null;
}``````

## Similar Posts

### Replace all spaces in a string with %20

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

### Calculate Max Profit - Buy and Sell Stocks Multiple Times - Leet Code Solution

Problem Statement Say you have an array prices for which the ith element is the…

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Reverse digits of a signed integer - Leet Code Solution

Problem Statement Given a signed integer, reverse digits of an integer. Return…

### Integer to Roman conversion - Leet Code Solution

Problem Statement Roman numerals are represented by seven different symbols: I…

### Check whether an integer number given is palindrome or not - Leet Code Solution

Problem Statement Determine whether an integer is a palindrome. An integer is a…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…