How to make an BFS algorithm from an array of integers

Question

There is such a task:

There is an array of integers, you need to get from the very first element of the array to the last one in the minimum number of moves. You can move in two ways:

1 way: you can move between adjacent numbers. That is, if a number is in the i place, then from it you can get either to the i -1 number or to the i +1 number.

2 way: if the i number occurs two or more times in the array, then you can jump all the numbers in the interval between these equal numbers (that is, for example, if elements 2 and 5 are equal, then you can immediately jump from the second element to the 5th element, bypassing elements 3 and 4).

Example 1:

Input data: 3 5 2 2 5

Output data: 2

Example 2:

Input data: 11 -86 -86 201 11 86 86 86 3 201

Output data: 3

As I understand, this can be done using the BFS algorithm, but I don’t understand how to create a graph in this case?

Or maybe there are alternative ways to solve this problem?

Answer 1

You don't really have to create the graph, as the graph is already implicitly encoded in the input array. The rules define what are the edges of your graph.

At any given index you can determine by inspecting the input array which are the possible jumps: these are the edges from the current node (the current index) to the child nodes of the BFS tree.

To avoid scanning the array for duplicate values over and over again, it would make sense however to first collect the indices that have the same value, so that for a given value you can look up the list of indices that have that same value and do so more efficiently than having to inspect the whole array again.

Here is an implementation in JavaScript -- I didn't use any advanced features of that language:

function solve(arr) {
    const n = arr.length;
    // Preprocessing to improve efficiency: 
    //     gather the indices occupied by each distinct value
    const map = new Map(); // A hashmap keyed by input values, giving list of indices
    for (let i = 0; i < n; i++) {
        const val = arr[i];
        if (!map.has(val)) map.set(val, []); // assign an empty array to this value
        map.get(val).push(i); // Add the current index to this list
    }
    // Main BFS algorithm
    let currLevel = [0]; // Start at index 0; this is the first level
    const visited = new Set(); // Set of indices that have been visited
    visited.add(0);
    let depth = 0;
    while (true) {
        let nextLevel = [];
        for (let i of currLevel) { // Traverse indices at the same level of the BFS tree
            if (i == n - 1) return depth; // Bingo!
            // Get the possible jumps to the same value elsewhere:
            const children = map.get(arr[i]);
            // Also consider just stepping one step forward
            children.push(i + 1);
            for (let child of children) {
                if (visited.has(child)) continue; // Don't visit a second time
                visited.add(child);
                nextLevel.push(child);
            }
        }
        currLevel = nextLevel;
        depth++;
    }
}

// Example call:
let test = [1,3,8,9,10,11,2,4,12,1,2,5,6,7,4];
console.log(solve(test)); // 5

I've used as example this less trivial input:

[1,3,8,9,10,11,2,4,12,1,2,5,6,7,4]

...because the shortest path involves jumping backwards:

    [1,3,8,9,10,11,2,4,12,1,2,5,6,7,4]
     └────────────────────┐             1. jump to other 1
                          └─┐           2. step forward
                   ┌────────┘           3. jump to other 2
                   └─┐                  4. step forward
                     └──────────────┐   5. jump to other 4
                                  done