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


  • 0
    K

    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
                // Add the new index to the already created list
                if (numIndexMap.containsKey(currentNumber)) {
    
                    numIndexMap.get(currentNumber).add(i);
    
                } 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<>();
                    indexList.add(i);
    
                    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;
        }
    }
    

Log in to reply
 

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