1345. Jump Game IV

Time: O(n)

Space: O(n)

Intuition

In a standard BFS, we explore layer by layer. The key optimization here is the value-to-indices graph: all indices with the same value are just one "jump" away. By clearing each value's adjacency list after processing, we avoid re-exploring the same connections in future layers.

Algorithm

1Build a graph: map each value to a list of indices where it appears.
2Initialise BFS queue with index 0 and track visited indices.
3For each BFS layer (step):
4 Dequeue an index i. If i == n-1, return step.
5 Enqueue neighbors: i-1, i+1 (if valid) and all indices in graph[arr[i]].
6 Clear graph[arr[i]] after processing to prevent re-visiting the same edges.
7Return step when reaching index n-1.

Example Walkthrough

Input: arr = [100,-23,-23,404,100,23,23,23]

1.From 0: can jump to 1 (100-1) or any index with value 100 (indices 0, 4).
2.From 1: can jump to 0,2 (adjacency) or any with value -23 (indices 1,2).
3.From 4: can jump to 3,5 (adjacency) and others with value 100; index 7 eventually reachable.

Output: 3

Common Pitfalls

•Without clearing the value's edge list, you re-process the same indices multiple times, turning O(n) into O(n²).
•Do not confuse this with adjacency in a standard graph; edges depend on both position (i±1) and value (equal arr values).
•Visited check must happen before enqueueing to avoid processing the same index multiple times.

1345.cs

// Approach: BFS where from index i you can reach i±1 or any index with arr[i]==arr[j].
// Build a graph: value -> list of indices with that value.
// Clear each value's list after processing to avoid redundant edge checks.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MinJumps(int[] arr)
    {
        int n = arr.Length;
        // {a: indices}
        var graph = new Dictionary<int, List<int>>();
        var q = new Queue<int>();
        q.Enqueue(0);
        var seen = new bool[n];
        seen[0] = true;

        for (int i = 0; i < n; ++i)
        {
            if (!graph.ContainsKey(arr[i]))
                graph[arr[i]] = new List<int>();

            graph[arr[i]].Add(i);
        }

        for (int step = 0; q.Count > 0; ++step)
        {
            int sz = q.Count;
            for (; sz > 0; --sz)
            {
                int i = q.Dequeue();
                if (i == n - 1)
                    return step;
                seen[i] = true;
                int u = arr[i];
                if (i + 1 < n)
                    graph[u].Add(i + 1);
                if (i - 1 >= 0)
                    graph[u].Add(i - 1);
                foreach (int v in graph[u])
                {
                    if (seen[v])
                        continue;
                    q.Enqueue(v);
                }
                graph[u].Clear();
            }
        }

        throw new ArgumentException();
    }
}

Was this solution helpful?