1696. Jump Game VI

This page provides solutions for the leetcode problem 1696. Jump Game VI.

Problem Explanation

The problem requires us to calculate maximum score you can get in jump game with following rules.

You are initially standing at index $\text{0}$. In one move, you can jump at most $\text{k}$ steps forward without going outside the boundaries of the array. That is, you can jump from index $\text{i}$ to any index in the range $\text{[i + 1, min(n - 1, i + k)]}$ inclusive.

You want to reach the last index of the array $\text{index = n - 1}$. Your score is the sum of all $\text{nums[j]}$ for each index $\text{j}$ you visited in the array.

Solution

This problem can be solved using the Deque data Structure. More such problem can be found here.

Java

class Solution {
  public int maxResult(int[] nums, int k) {
    int n = nums.length;
    int[] score = new int[n];
    Deque<Integer> dq = new LinkedList<>();
    score[0] = nums[0];
    dq.offer(0);

    for(int i = 1; i < n; i++) {
      while(!dq.isEmpty() && i - dq.peekFirst() > k) dq.pollFirst();
      score[i] = score[dq.peekFirst()] + nums[i];
      while(!dq.isEmpty() && score[dq.peekLast()] <= score[i]) dq.pollLast();
      dq.offer(i);
    }
    return score[n - 1];
  }
}

Complexity

Let's say there are $\text{N}$ elements in an array.

Time Complexity

Each index is visited only once, so time complexity will be:

$$\text{O}(\text{N})$$

Space Complexity

At any given point deque will have $\text{N}$ elements, so space complexity will be:

$$\text{O}(\text{N})$$