Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem 4: Next Greater Element

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 2 years ago

I think the stack solution has a time complexity of O(n^2) in the worst case.

Consider this input: [4, 1, 2, 3, 5]

If we start from the end of the array, by the time we reach 0th index, the stack would have the following elements:

1

2

3

5

So as we compare the current element 4 with the top element in stack we would end up popping all 1, 2, 3. We have to pop till 5 to get next greater element to 4. So, our inner loop ends up running 4 times (for elements 1, 2, 3, 5 in stack) for our array arr of size 5 in this case. Therefore I believe the worst case time complexity must be O(n^2).

Show 1 reply
A

Anonymous

· 2 years ago

I have a question regarding time complexity. Does using while loop not considered a nested iteration of the given input?

If yes then the time-complexity should be O(n^2).

Show 1 reply
A

Anonymous

· 3 years ago

I tried to solve this problem by iterating from the beginning, but couldn't solve it. How do we know that we will need to start looking from the last index instead of starting from the beginning?

Show 2 replies
A

Anonymous

· 3 years ago

Problem:


public List<Integer> nextLargerElement(List<Integer> arr) {}

Solution:


int[] printNGE(int arr[]) {}

Reading Progress

0%

Vote for new content