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

  • 0

    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?

    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

    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.