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


  • 6
    Z
    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) 
            {
                if(nums[index]>findNums[i])
                {
                    minIndex =index;
                    break;
                }
            }
            if(minIndex ==-1) findNums[i] = -1;
            else findNums[i] = nums[minIndex];
        }
        return findNums;
    }

  • 0
    H

    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
    C

    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
    K

    @carlosmve I think so


  • 0
    S

    @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.