Задача: 1345. Jump Game IV
Сложность: hard

Дан массив целых чисел arr, изначально вы находитесь на первом индексе массива.

За один шаг вы можете прыгнуть с индекса i на индекс:

- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.

Вернуть минимальное количество шагов, чтобы достичь последнего индекса массива.

Обратите внимание, что нельзя прыгать за пределы массива в любой момент времени.

Пример:

Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.

👨‍💻 Алгоритм:

1⃣Построить граф, где ключи - значения из массива, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.

2⃣Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.

3⃣Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.

😎 Решение:

class Solution {
  minJumps(arr) {
    const n = arr.length;
    if (n <= 1) return 0;

    const graph = new Map();
    for (let i = 0; i < n; i++) {
      if (!graph.has(arr[i])) {
        graph.set(arr[i], []);
      }
      graph.get(arr[i]).push(i);
    }

    let curs = [0];
    const visited = new Set();
    visited.add(0);
    let step = 0;

    while (curs.length > 0) {
      const nex = [];

      for (const node of curs) {
        if (node === n - 1) return step;

        for (const child of graph.get(arr[node])) {
          if (!visited.has(child)) {
            visited.add(child);
            nex.push(child);
          }
        }

        graph.get(arr[node]).length = 0;

        if (node + 1 < n && !visited.has(node + 1)) {
          visited.add(node + 1);
          nex.push(node + 1);
        }
        if (node - 1 >= 0 && !visited.has(node - 1)) {
          visited.add(node - 1);
          nex.push(node - 1);
        }
      }

      curs = nex;
      step++;
    }

    return -1;
  }
}

Ставь 👍 и забирай 📚 Базу знаний