Leetcode 1019: Finding the next greatest node — the Domino effect

Hack it yourself!

The Problem and example I/O:

The problem statement is to find the next greatest element in a linked List. So for the ith node we have to find the jth node, such that node value of j is greater than ith.

The catch here is that we have to find the most recent one. Let’s take an example:

[2,1,5]

output => [5,5,0]

notice that for i=0, the greatest element after 2 is 5

for i = 1, next greatest = 5

for i = 2, does not have any next greatest, hence the zero 0

Another example,

[1,7,5,1,9,2,5,1]

output => [7,9,9,9,0,5,0,0]

running it by the previous explanation, it is apparent that reasoning behind the output

The Intuition

The idea is to think of it as a domino.

for the input:

[2,7,4,3,5]

let’s visualize how it would look like in a dominos:

domino for [2,7,4,5]

Now, think each of them as tiles. Which ones can drop as we go from left to right?