Greedy Algorithm
A problem I tried
Mar 30, 2024
Recently, I’ve tried this problem.
https://leetcode.com/problems/jump-game/description/?envType=study-plan-v2&envId=top-interview-150
At first, my algorithm was O(N²). Personally, I was confident about the solution because I used recursion and computing it from the tail was excellent for me.
However, there is a better solution than mine, which is greedy algorithm. The time complexity is O(n).
What is greedy?
Greedy algorithm is literally greedy, which means it keeps selecting the biggest number. This the example is below.
The algo doesn’t care about if the pointer goes beyond the last index or not. It just selects the furthest distance at any rate. This is a trick of greedy algo.
