What's the time complexity of my code? O(n) or O(n^2)?


  • 0
    Y

    I use nextGreater to find the next greater number of nums[i] in array nums, then for each elements in nums, I put nums[i]and its next greater number into the HashMap.
    I think the best case for my code is O(N)(ascending order), worst case isO(N^2)(descending order). BUT,its runtime is less than O(N) stack solution. So is my analysis of time conplexity correct?
    Thanks

    public class Solution {
        public int[] nextGreaterElement(int[] findNums, int[] nums) {
            int[] res=new int[findNums.length];
            Map<Integer,Integer> map=new HashMap<>();
            for(int i=0;i<nums.length;i++) map.put(nums[i],nextGreater(nums,i));
            for(int i=0;i<res.length;i++) res[i]=map.get(findNums[i]);
            return res;
            
        }
        
        public int nextGreater(int[] nums, int i) {
            if(i==nums.length-1) return -1;
            for(int m=i+1;m<nums.length;m++)
                if(nums[m]>nums[i]) return nums[m];
            return -1;
        }
        
    }
    

  • 0
    P

    Your code is O(n^2) time and O(n) space.

    Stack solution has faster asymptotic runtime but as you see the O(n^2) algorithm is faster for small imputs.


Log in to reply
 

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