Accepted Java O(n) Solution - 2ms. Currently beats 100%


  • 0
    C

    I believe this solution has space complexity O(n) and time complexity of O(n) where n is the length of the input arrayl. There are two hashmaps for this solution. One that stores the value as a Key and index in the input array as the Value. The other hashmap is for storing values that show up more than once. This stems for the problem's constraint of there existing only one solutution.

    Bare with me as this is my first post. Any constructive feedback is appreciated!

    public class Solution {
        public int[] twoSum(int[] nums, int target) {
            if(nums == null){
                return null;
            }
            
            // <val,index>
            Map<Integer,Integer> map = new HashMap<Integer,Integer>();
            
            // <val,index>
            Map<Integer,Integer> moreThanOnce = new HashMap<Integer,Integer>();
            
            for(int i = 0; i < nums.length; i++){
                if(map.containsKey(nums[i])){
                    moreThanOnce.put(nums[i], i);
                }
                map.put(nums[i], i);
            }
            
            int sub = 0;
            int[] ret = new int[2];
            for(int i = 0; i < nums.length; i++){
                sub = target - nums[i];
                
                if(sub == nums[i]){
                    if(moreThanOnce.containsKey(nums[i])){
                        ret[0] = i;
                        ret[1] = moreThanOnce.get(nums[i]);
                        return ret;
                    }
                } else if(map.containsKey(sub)){
                    ret[0] = i;
                    ret[1] = map.get(sub);
                    return ret;
                }
            }
            
            return ret;
        }
    }
    

  • 0
    B

    I got Runtime: 15 ms with your code, and I even got Runtime: 1ms with a solution using ArrayList. Please don't believe the judge of leetcode in Runtime.


  • 0
    C

    @brekov hmm odd.. gotchya


Log in to reply
 

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