1340. Jump Game V

Time: O(n)

Space: O(n)

Intuition

From index i you can jump left/right up to distance d, but only to smaller heights, and the path is blocked by any height greater than or equal to arr[i]. This creates local visibility constraints. A monotonic stack processes bars by height boundaries and allows dynamic programming transitions to be relaxed exactly when a blocking boundary is known.

Algorithm

1Let dp[i] be maximum extra jumps starting from index i (answer is max(dp)+1 for counting nodes).
2Maintain a decreasing stack of indices by arr value.
3Iterate i from 0..n, using i==n as a sentinel flush step.
4While stack top is lower than current height (or at sentinel), pop a group of equal-height indices.
5For each popped index j:
6 If current index i is within d of j, relax dp[i] = max(dp[i], dp[j] + 1).
7 If new stack top exists and is within d of j, relax dp[top] = max(dp[top], dp[j] + 1).
8Push current index to continue processing.
9Return max(dp) + 1.

Example Walkthrough

Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2

1.Index 2 (14) can jump to smaller heights within 2 steps until blocked, such as 1 (4), 3 (6), and 4 (8).
2.DP values from lower heights are computed/propagated first through stack pops.
3.Transitions are only applied when distance <= d and boundary rules allow it.
4.Maximum reachable chain length becomes 4 positions.

Output: 4

Common Pitfalls

•Equal heights must be handled as a group when popping; otherwise transitions between same heights can be mishandled.
•Distance constraint (<= d) applies to every transition; skipping this check overestimates dp.
•Return max(dp)+1 because dp counts jumps, while the problem asks for number of indices visited.

1340.cs

// Approach: DP with a monotonic decreasing stack to propagate best jump counts between valid indices.
// Process heights from left to right (plus a sentinel). When a higher bar appears, pop lower/equal groups,
// and relax transitions within distance d from the left and right boundaries.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MaxJumps(int[] arr, int d)
    {
        int n = arr.Length;
        // dp[i] := the maximum jumps starting from arr[i]
        int[] dp = new int[n];
        // a decreasing stack that stores indices
        Stack<int> stack = new Stack<int>();

        for (int i = 0; i <= n; ++i)
        {
            while (stack.Count > 0 && (i == n || arr[stack.Peek()] < (i < n ? arr[i] : int.MaxValue)))
            {
                List<int> indices = new List<int> { stack.Pop() };
                while (stack.Count > 0 && arr[stack.Peek()] == arr[indices[0]])
                    indices.Add(stack.Pop());
                foreach (int j in indices)
                {
                    if (i < n && i - j <= d)
                        // Can jump from i to j.
                        dp[i] = Math.Max(dp[i], dp[j] + 1);
                    if (stack.Count > 0 && j - stack.Peek() <= d)
                        // Can jump from stack.Peek() to j
                        dp[stack.Peek()] = Math.Max(dp[stack.Peek()], dp[j] + 1);
                }
            }
            stack.Push(i);
        }

        return dp.Max() + 1;
    }
}

Was this solution helpful?