Solving : Jump Game ||, using Greedy Approch

Today I’m going to solve Jump Game II using a greedy approach.
This solution runs in O(n) time and uses O(1) extra space.

Instead of directly trying to count the jumps at every step, we focus on the maximum coverage (the farthest index we can currently reach). The idea is: in each “window” of indices that we can reach with the current jump, we try to extend our coverage as far as possible, so that the next jump takes us closer to the end.

I struggled with this problem at first. The recursive solution is very slow, and more general methods are also time-consuming. The greedy approach, however, sets everything up in a very efficient and elegant way.

To implement it, I use three main variables:

  • totalJumps – counts how many jumps we have made so far.

  • currentEnd (or destination) – the end of the current coverage window; when we reach this index, we must make a jump.

  • farthest – the farthest index we can reach from any index inside the current window.

As we iterate through the array, for each index i we update farthest = max(farthest, i + nums[i]).
Whenever we reach currentEnd, we increase totalJumps and move currentEnd to farthest. In other words, from all positions in the current window, we choose the jump that gives us maximum coverage, and that defines our next jump boundary.

This way, we greedily expand our coverage window and reach the last index using the minimum number of jumps.




let solve = (nums) =>
{
let jump=0
let cover=0
let ljump=0
let n=nums.length

for(let i=0; i<n-1; i++) {
cover = Math.max(cover, i+nums[i])
if(i == ljump) {
ljump = cover
jump++

if(cover >= n) {
return jump
}
}
}
return jump
}

nums = [2, 4, 1, 2, 3, 1, 1, 2]
console.log(solve(nums))

Comments

Post a Comment

Popular posts from this blog

C linking with Masm64

  Today I learn Masm64 basics and linking with C Modules day 9/19/2025: Today I learn MASM64 basics and linking with a C program. Now I  am a very basic MASM and C programmer, so it was hard for me to create my own printf in MASM. Then an idea came to my mind to link C printf with Masm. To achieve this desire, I created a new program in C named practical.c and practical.asm. After spending hours, I am successful in achieving this. Then, I want to get user input in ASM, as previously I said, this was also hard for me to take input in MASM, so I created a readLine function in this function takes a buffer and maxLen from MASM and gets input, and prints. practical.c /*     Author Danishk Sinha */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <stddef.h> #ifdef __cplusplus extern "C" { #endif char * getTitle ( void ); int readLine ( char * buff, int len); void asmMain ( void ); #ifdef __cplusplus }; #endif int rea...
Read more

Learning Recursion based Permutations

 I'm revising recursion again today. I've already learned it this way, but I need to revise it this way again. Yesterday I learned Grady Algorithms. I had to learn recursion again because this topic is a little difficult, but not impossible. It is quite true that backtracking is perfect for recursion-based permutations. I am learning this because I am trying to solve LeetCode question 46.  Finally, I found the solution: Pardon me if any misslogic, var permute = function ( nums ) { let ans = [] let i = 0 let n = nums . length - 1 getPerm ( nums , ans , i , n ) return ans }; let getPerm = ( nums , ans , idx , n ) => {          if(idx === n) {          ans.push([...ans])          return      }     for(let i=idx; i<n; i++) {                     let tmp = nums[id...
Read more

Learning MergeSort with JS

  Today I learn MergeSort in JS! I Learned mergeSort because this is the fastest sorting algorithm, as it takes O(n log n) time, which is better than bubble sort with time complexity O(n^2). At the end, I understood the main logic of MergeSort, the divide-and-conquer method. which means an array pass to merge_sort(arr), it starts by dividing into subarrays until it reaches 1 element of subarray, then it starts sorting it .  merge-sort.js function merge_sort(arr, l = 0 , h = arr.length - 1 ) {         if (l >= h) return     let m = Math. floor ((l + h) / 2 )     merge_sort (arr, l, m)     merge_sort (arr, m + 1 , h)     merge (arr, l, m, h) } function merge(arr, l, m, h) {         const tmp = []     let i = l, j = m + 1     while (i <= m && j <= h) {         if (arr[i] < arr[j]) tmp. push (arr[i ++ ])       ...
Read more