Leetcode 1345. Jump Game IV

Problem Explanation

The problem is asking us to find the minimum number of steps to reach the last index of a given array, starting from the first index. The game's rules allow us to make a jump in three different ways:

• To the next index (i + 1), as long as it is within the array's boundaries
• To the previous index (i - 1), as long as it is within the array's boundaries
• To any index that contains the same value as the current index

Let's Discuss an example

Consider arr = [100,-23,-23,404,100,23,23,23,3,404]. The minimum number of steps to reach the last index (index 9) is 3.

Here's how that works:

• We start at index 0 (value 100)
• We jump to index 4 because index 4 also contains the value 100
• We jump to index 3 because it's the next index (i + 1)
• We finally jump to index 9 because it contains the same value 404 as index 3

So, the path is 0 --> 4 --> 3 --> 9, total 3 steps.

Solution Approach

To solve this problem, we will use breadth-first search (BFS), which is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (in our case the first index of the array) and explores the neighbor nodes at the current depth level before moving to nodes at the next depth level.

We will keep track of visited indices using seen[] array to avoid visiting same index multiple times.

At each step (or level in terms of BFS), we will explore all available moves (i + 1, i - 1 and indices having same value as current index) and add them to the queue for the next level of BFS, until we reach the last index.

Python Solution

1
2python
3from collections import deque
4def minJumps(arr):
5    size = len(arr)
6    # Construct graph
7    graph = {}
8    for i, value in enumerate(arr):
9        if value not in graph:
10            graph[value] = []
11        graph[value].append(i)
12    # BFS from node 0
13    queue = deque([(0, 0)])  # (index, steps)
14    visited = {0}
15    while queue:
16        index, steps = queue.popleft()
17        # Reached last index
18        if index == size - 1:
19            return steps
20        # Check neighbors
21        neighbors = graph[arr[index]] + [index - 1, index + 1]
22        for neighbor in neighbors:
23            if 0 <= neighbor < size and neighbor not in visited:
24                visited.add(neighbor)
25                queue.append((neighbor, steps + 1))
26        graph[arr[index]].clear()  # avoid checking same value again
27    return -1

Java Solution

1
2java
3import java.util.*;
4public class Solution {
5  public int minJumps(int[] arr) {
6    int size = arr.length;
7    // Construct the graph
8    Map<Integer, List<Integer>> graph = new HashMap<>();
9    for (int i = 0; i < size; i++) {
10      graph.putIfAbsent(arr[i], new ArrayList<>());
11      graph.get(arr[i]).add(i);
12    }
13    // BFS from node 0
14    Queue<int[]> queue = new LinkedList<>();
15    queue.add(new int[]{0, 0});  // (index, steps)
16    boolean[] visited = new boolean[size];
17    visited[0] = true;
18    while (!queue.isEmpty()) {
19      int[] current = queue.poll();
20      int index = current[0], steps = current[1];
21      // Reached the last index
22      if (index == size - 1)
23        return steps;
24      // Check neighbors
25      List<Integer> neighbors = new ArrayList<>(graph.get(arr[index]));
26      neighbors.add(index - 1);
27      neighbors.add(index + 1);
28      for (int neighbor : neighbors) {
29        if (neighbor >= 0 && neighbor < size && !visited[neighbor]) {
30          visited[neighbor] = true;
31          queue.add(new int[]{neighbor, steps + 1});
32        }
33      }
34      graph.get(arr[index]).clear();  // avoid checking same value again
35    }
36    return -1;
37  }
38}

Javascript Solution

1
2javascript
3var minJumps = function(arr) {
4    let size = arr.length;
5    // Construct the graph
6    let graph = {};
7    for (let i = 0; i < size; i++) {
8      if (!(arr[i] in graph)) 
9        graph[arr[i]] = [];
10      graph[arr[i]].push(i);
11    }
12    // BFS from node 0
13    let queue = [[0, 0]];  // (index, steps)
14    let visited = new Set([0]);
15    while (queue.length) {
16      let [index, steps] = queue.shift();
17      // Reached the last index
18      if (index == size - 1) 
19        return steps;
20      // Check neighbors
21      let neighbors = [...graph[arr[index]], index - 1, index + 1];
22      for (let neighbor of neighbors) {
23        if (0 <= neighbor && neighbor < size && !visited.has(neighbor)) {
24          visited.add(neighbor);
25          queue.push([neighbor, steps + 1]);
26        }
27      }
28      graph[arr[index]] = [];  // avoid checking same value again
29    }
30    return -1;
31};

C++ Solution

1
2c++
3#include <unordered_map>
4#include <vector>
5#include <queue>
6using namespace std;
7class Solution {
8public:
9  int minJumps(vector<int>& arr) {
10    int size = arr.size();
11    unordered_map<int, vector<int>> graph;
12    vector<int> visited(size, 0);
13    for (int i = 0; i < size; ++i)
14      graph[arr[i]].push_back(i);
15    queue<pair<int, int>> queue;  // (index, steps)
16    queue.push({0, 0});
17    while (!queue.empty()) {
18      auto [index, steps] = queue.front(); queue.pop();
19      if (index == size - 1) // Reached the last index
20        return steps;
21      if (visited[index]) 
22        continue;
23      visited[index] = 1;
24      // add neighbors
25      if (index + 1 < size)
26        queue.push({index + 1, steps + 1});
27      if (index - 1 >= 0) 
28        queue.push({index - 1, steps + 1});
29      for (int neighbor : graph[arr[index]]) 
30        queue.push({neighbor, steps + 1});
31      graph[arr[index]].clear();  // avoid checking same value again
32    }
33    return -1;
34  }
35};

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5public class Solution {
6    public int MinJumps(int[] arr) {
7        int size = arr.Length;
8        // Construct the graph
9        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
10        for (int i = 0; i < size; i++) {
11            if (!graph.ContainsKey(arr[i]))
12                graph[arr[i]] = new List<int>();
13            graph[arr[i]].Add(i);
14        }
15        // BFS from node 0
16        Queue<(int, int)> queue = new Queue<(int, int)>();  // (index, steps)
17        queue.Enqueue((0, 0));
18        bool[] visited = new bool[size];
19        visited[0] = true;
20        while (queue.Count > 0) {
21            var (index, steps) = queue.Dequeue();
22            // Reached the last index
23            if (index == size - 1)
24                return steps;
25            // Check neighbors
26            List<int> neighbors = new List<int>(graph[arr[index]]);
27            neighbors.Add(index - 1);
28            neighbors.Add(index + 1);
29            foreach (int neighbor in neighbors) {
30                if (neighbor >= 0 && neighbor < size && !visited[neighbor]) {
31                    visited[neighbor] = true;
32                    queue.Enqueue((neighbor, steps + 1));
33                }
34            }
35            graph[arr[index]].Clear();  // avoid checking same value again
36        }
37        return -1;
38    }
39}

As you can see, solving this problem involves traversing the array using a breadth-first search algorithm. The basic structure of the solution is similar across all programming languages — Python, Java, Javascript, C++, and C#.

The primary difference between implementations lies in the specific language syntax and function calls.

Our BFS approach works regardless of the language used. The key elements remain the same: we maintain a queue to store indexes to visit and their respective step count and a data structure to track visited elements. We iterate through the queue, exploring neighbors to find the minimum steps to reach the last index of the array.

The complexity of this algorithm is O(n), where n is the size of the given array. We visit every index exactly once, thus making it a linear solution. However, constructing and iterating through the graph might add a degree of computational complexity. However, the time complexity will still remain linear, making this solution efficient and workable for large datasets.

In conclusion, the minimum jump game problem can be effectively solved using BFS traversal regardless of the language used. Python, Java, Javascript, C++, and C# solutions presented here maintain the same logical flow and exhibit minor variations owing to the specific language syntax and function calls.