Why didn't school teach me how to solve this in O(n)?

Why didn't school teach me how to solve this in O(n)?

Attached: L739.jpg (1440x2543, 288.63K)

>Why didn't school teach me
Nice dogwhistle, chud. /qa/ lost.

Attached: 1657198471167.png (255x375, 45.22K)

godson thread now.

Attached: 34723847239847238.gif (300x300, 2.44M)

Much harder than what I thought. I was reasoning about inverse sorting permutations (which can be computed in linear time) but I couldn't figure out the solution so I looked it up online and it has nothing to do with it.
I'm curious, is there any "off the shelf" algorithm that use this jump strategy?
result[i] += result[i+result[i]]

>Much harder than what I thought
Yeah monotonic stack problems are always unintuitive to me

Assuming you went to a university to study computer science, you should have been given the knowledge of how to design algorithms on your own, and how to evaluate their time complexity and space complexity. You should also have been given plenty of assignments to practice your ability to do this with a wide variety of problems. Although you would not be shown every problem, you would have the skills to adapt to new problems.

You DID do all of your homework, right? And you did it yourself instead of asking someone to do it for you, or googling for the answers, right?

zoomer memes are so fucking bad jesus christ

basedjack is more of a late-millenial meme than a zoomer meme

I've never encountered a monotonic stack problem in textbooks or exams

O log n to sort
O n to find the days

Amirite?

The only thing school really teaches you is how to follow a boss

>sort
You dumb fucking retard.
People like you is the reason why software is so shit these days.
Do the world a favour and quit programming or just kys.

You don't need to be able to learn every kind of problem, you just need to be able to learn how to approach algorithmic problems in general so you can figure out a solution yourself.

>O log n to sort
It's n log n to sort.Which is, strictly speaking, more than n.

Why would you sort?

result = [0] * len(temperatures)
stack = []
for i, t in enumerate(temperatures):
while stack and stack[-1][0] < t:
j = stack[-1][1]
result[j] = i - j
stack.append((t, i))
print(result)

oops, should be
j = stack.pop()[1]

Be honest, are you be able to solve this exercise (in linear time) without looking at the solution?

Assuming the input array is Input and the output is Answer:
for(int i = Input.size()-1;i > 0;i--){
if(Input[i] > Input[i-1])
Answer[i-1] = 1;
else
Answer[i-1] = Answer[i] != 0 ? Answer[i] : 0;
}

not for sufficiently small values of n

yes. there are a number of other problems analogous to it that you should have encountered in an undergraduate computer science class that it should be straightforward to solve for anyone who paid attention and is capable of actually *thinking* rather than just regurgitating memorized snippets of code.

Oh I think I get it. You walk right maintaining every element you see. Then for each new element you see, you check whether it can eliminate some elements from the ones you've seen so far recent first. Because of the elimination, the elements you maintain are necessarily in decreasing order.
It's O(n) because we advance one element each step and each element is "eliminated" once. Something like that.