# Accepted O(n) solution to Two Sum problem(handles duplicate numbers too)

• O(n) time complexity.
O(n) space complexity

It also handle the case where we have the target being the sum of the same number occurring twice in the array.

Example:- numbers = [3,3] and target = 6

Would love some feedback on my code :-)

``````public class Solution {
public int[] twoSum(int[] nums, int target) {

// The result array that we will return
int[] result = new int[2];

// A map of numbers to a list of their indices(as numbers may occur multiple times)
Map<Integer, List<Integer>> numIndexMap = new HashMap<>();

for (int i = 0; i < nums.length; i++) {
int currentNumber = nums[i];

// If the number has already been added to the map, it looks we have another occurence of the same number
if (numIndexMap.containsKey(currentNumber)) {

} else {
// This is the first time we have seen this number.
// Create a new list and add this index to it

List<Integer> indexList = new ArrayList<>();

numIndexMap.put(currentNumber, indexList);
}
}

// Now, time to solve the problem :-)

for (int i = 0; i < nums.length; i++) {

// Get the current number and the remainder
final int currentNumber = nums[i];
final int remainder = target - currentNumber;

// The condition is self-explanatory
if (currentNumber == remainder) {

// First check if there indeed are two or more copies of the same number in the array
// This is where storing the list of indices comes in handy
if (numIndexMap.get(currentNumber).size() < 2) {
// Looks like we don't really have another copy of the number. Continue
continue;
}

// We have multiple copies of the same number. The first index is the current one a.k.a "i"
result[0] = i;

// We will have to use two different indices.
// Since we cannot use the same index twice, we find the indexList index of "i"
// using binary search(indices added in increasing order, so its already sorted)
// and then get the next available index for currentNumber
List<Integer> indexList = numIndexMap.get(currentNumber);

// Find location of current index i
final int indexOfI = Collections.binarySearch(indexList, i);
// Get the next index
result[1] = indexList.get((indexOfI + 1) % indexList.size());
break;

} else {

// Check if remainder exists in the array
if (!numIndexMap.containsKey(remainder))
continue;

result[0] = i;

// Get the first available index
result[1] = numIndexMap.get(remainder).get(0);
break;
}

}

return result;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.