LeetCode Next Greater Element I Solution Explained - Java

[@LuisMorales-yx8di]

It would be cool if you could discuss time and space complexity.

[@kdkwarteng7610]

Could you possibly discuss runtime as you go through these

[@LuisMorales-yx8di]

+1

[@namansharma5128]

@@LuisMorales-yx8di [phone]

[@chaoluncai1607]

as the worst case scenario is stack push and pop each element in nums2[] once, and we have to loop through every element in nums1[] for the result, hence I think it's O(2*nums2.length + nums1.length) = O(nums1.length+nums2.length)

[@darod6098]

I thought that i could do it without the stack, going through the array from 1 to n-1 but with the decreasing case at the end you made me realize that i can't. Thank you

[@Sobioytccc]

public static int[] nextGreaterElement(int[] nums1, int[] nums2) { int[] nextGreaterElements = new int[nums1.length]; int nextGreaterElement = -1; for (int k = 0; k < nums1.length; ++k) { nextGreaterElement = -1; for (int i = 0; i < nums2.length; ++i) { if (nums2[i] == nums1[k]) { for (int j = i + 1; j < nums2.length; ++j) { if (nums2[j] > nums1[k]) { nextGreaterElement = nums2[j]; break; } } break; } } nextGreaterElements[k] = nextGreaterElement; } return nextGreaterElements; }

[@AmgadDeyaa]

the stack is an array with some constraints literally you can implement the stack using array but here we are using the concept of the stack

[@vivekshokeen1192]

We should traverse from the backside of the nums2 array for more intuitive approach

[@yusselrosario5208]

It is a bad idea to modify nums1. If a function returns an array you don't expect the input array to be modified. It also makes the code less readable;

[@MeetManga]

there is a bug : if there are some duplicted numbers in the array, then the value of key in the hasMap will be overwrited.

[@frankf5398]

It's guranteed that there's no duplicates

[@anupamsingh8925]

sir how to get this level approach for doing such types of question?

[@ronaldo7rik]

Practice

[@amrholo4445]

Thanks a lot, sir may you discuss the time and space complexity please, I find it hard to come up with it myself

[@shubhammishra6119]

what if array is ar1=[1,2,3,4] ar2=[1,4,2,3] stack [1]-> 4 comes , hashmap becomes ->(1,4) stack[4]-> 2 comes , False stack[4,2]-> 3 comes False Final answer -> [4,-1,-,1,-1] expected -[4,3,-1,-1] for this condition your code is not working? let me know if i am understanding your code wrong-> else solution.

[@shubhammishra6119]

Instead of Peek you should stack last element

[@MohitSinha4]

Your explanation is just wow!

[@alind_singh]

Can anyone help me with the time complexity of the nested loops in the given solution?

[@zihaosong1514]

Thanks for your explanation!

[@lifeofme3172]

I don't like hit me up 😂 good explanation

[@VinayKumar-xs6el]

You are just a Legend

[@syedmehdiabbas1588]

I love your humor Nick

[@bisujin1685]

Very good explanation thanks

[@srinadhp]

great explanation! Thank yoU!

[@amaan0]

Brooooo! Awesome explaination .❤

[@rahuldabas8233]

great explanation dude!!

[@rafishaik2496]

explain nge2 leet code solution

[@chodingninjas7415]

great explanation

[@quirkyquester]

amazing explanation! Thank you!

[@АдемаЕргара]

Your runtime complexity here is O(N^2 ), right?

[@alaaeldin-khaled]

nope. watch Abdul Bari videos about time complexity on youtube

[@harshithahprabhu6220]

what's the time complexity?

[@iamnoob7593]

O(nums1.length + nums2.length) ~ O(m+n)

[@sumansumann8947]

@@iamnoob7593 as there is a while loop inside the first for loop ,, how it would be linear time complexity??

[@iamnoob7593]

@@sumansumann8947 worst case if u keep inserting elements in stack. After inserting last element in stack.. for is done no more.... It's linear. Analyze on paper.

[@aravindhravi2307]

This is beautiful

[@pranshusati5115]

Hey Nick I know its 4 years sice the upload can you still help me solve this can't figure out whats the mistake in this public int[] nextGreaterElement(int[] nums1, int[] nums2) { HashMap mp = new HashMap(); int p = -1; // int[] reversedNums2 = Arrays.copyOf(nums2, nums2.length); // reverseArray(reversedNums2); mp.put(nums2[nums2.length -1],-1); int max = nums2[nums2.length-1]; for(int i = nums2.length-2; i>=0; i--){ int current= nums2[i]; if(current < max){ if(i!=nums2.length && nums2[i+1] > current) max = nums2[i+1]; mp.put(current,max ); } else mp.put(current,-1); max = Math.max(current,max); } int[] res = new int [nums1.length]; for(int i =0; i< nums1.length; i++){ res[i] = mp.get(nums1[i]); } return res; }

[@whoami8247]

Why did you reverse the array

[@pranshusati5115]

@@whoami8247 that line has been commented plz look closely