Java O(n) HashMap method, beats 95% currently

  • 6
    public int[] nextGreaterElement(int[] findNums, int[] nums) {
        Map<Integer, Integer> m = new HashMap<>();
        // go through each element in nums and set its location in HashMap
        for(int i =0;i<nums.length;++i)
            m.put(nums[i],i); //since every element is unique, there is no need (getOrDefault)
        //scan each element in the first array    
        for(int i=0;i<findNums.length;++i)
            int minIndex =-1;  //initially, set the finding index to be -1
            int index = m.get(findNums[i]); //findout the corresponding index in the second (nums) array.
            while(++index < nums.length) 
                    minIndex =index;
            if(minIndex ==-1) findNums[i] = -1;
            else findNums[i] = nums[minIndex];
        return findNums;

  • 0

    This is super fast, but I'm not sure why it uses less time than stack. The second for-loop seems more complex than stack.

  • 0

    Can you explain why is this O(n)? It seems you're iterating the findNums array and then iterating the nums Array until you find an element, that should be N(n * m) isn't it?

  • 0

    @carlosmve I think so

  • 0

    @hfu Because the first for-loop just go through the findNums array.

Log in to reply

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