1345. Jump Game IV

January 14, 2022

Description:

Given an array of integers arr, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

i + 1 where: i + 1 < arr.length.
i - 1 where: i - 1 >= 0.
j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the last index of the array.

Notice that you can not jump outside of the array at any time.

Example 1:

1
2
3

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.

Example 2:

1
2
3

Input: arr = [7]
Output: 0
Explanation: Start index is the last index. You do not need to jump.

Example 3:

1
2
3

Input: arr = [7,6,9,6,9,6,9,7]
Output: 1
Explanation: You can jump directly from index 0 to index 7 which is last index of the array.

Constraints:

1 <= arr.length <= 5 * 10^4
-10^8 <= arr[i] <= 10^8

The length of the array is up to 10^4, the algorithm is expected to be bounded by ==O(nlogn)==

Brute Force:

Each round, you can jump front or back one step, or jump to the place with the same value.

Traverse all possibilities that start from index 0, with #step = 0, minStep = INT_MAX
- Each time, try out 3 possibilities, #step++
  - When reaching the end, update the minStep = min(minStep,#step)

It’s obvious that this method has a factorial time complexity. We can make a little modification, that is, each place can only be visited at most once, or it can’t be the minimum number of steps.

An Graph-like Intuition:

Each place is a node on the graph, nodes are sequentially linked according to their order in the array.
If there are nodes with the same value, link them with an edge.
Since we can move forward and backward at each place, the graph is a undirected graph.
Use BFS for solution (Use queue)

In actual implementation, a graph is not necessary, we can just keep. a hash map, where key is the value, value is the position of these values.

Complexity:

Vertices = N, Edges at max, all nodes have same value, $O(N^2)$, at min, 0.

Time Complexity: O(V+E)
Space Complexity: O(V+E) (Use Graph), O(V) (Not using extra graph)

Problem:

In the implementation, our time complexity depends on the number of edges. In cases of the same value, there could be edges at $O(N^2)$. (All nodes have the same value), which is obviously gonna give us a TLE.

Solution:

In the BFS Step, after we enqueue nodes with the same value, we can clear the entry in the hash map.

while (!q.empty())
{
    auto [src, dest] = q.front();
    q.pop();
    shortestPath[dest] = min(shortestPath[dest], shortestPath[src] + 1);
    if (dest == arr.size() - 1)
        return shortestPath[dest];
	
    //same value
    for (const auto &newDest : sameValueSet[arr[dest]])
    {
        if (shortestPath[newDest] == INT32_MAX)
            q.push(make_pair(dest, newDest));
    }

    //core step, this will get us away from redundant search
    //this step ensures nodes of the same value won't get enqueued overly
    //actually, enqueue nodes of the same value once is enough
    //so we clear out the entry 
    sameValueSet[arr[dest]].clear();

    //neighbors
    if (dest > 0 && shortestPath[dest - 1] == INT32_MAX)
        q.push(make_pair(dest, dest - 1));
    if (dest < (arr.size() - 1) && shortestPath[dest + 1] == INT32_MAX)
        q.push(make_pair(dest, dest + 1));
}

Code:

#include "header.hpp"

class Solution
{
public:
    int minJumps(vector<int> &arr)
    {
        //<value,position>
        unordered_map<int, vector<int>> sameValueSet;
        for (int i = 0; i < arr.size(); i++)
        {
            sameValueSet[arr[i]].push_back(i);
        }

        queue<pair<int, int>> q;
        vector<int> shortestPath(arr.size(), INT32_MAX);
        shortestPath[0] = 0;

        if (arr.size() == 1)
        {
            return 0;
        }

        q.push(make_pair(0, 1));
        for (const auto &i : sameValueSet[arr[0]])
        {
            if (i != 0)
                q.push(make_pair(0, i));
        }

        while (!q.empty())
        {
            auto [src, dest] = q.front();
            q.pop();
            shortestPath[dest] = min(shortestPath[dest], shortestPath[src] + 1);
            if (dest == arr.size() - 1)
                return shortestPath[dest];

            for (const auto &newDest : sameValueSet[arr[dest]])
            {
                if (shortestPath[newDest] == INT32_MAX)
                    q.push(make_pair(dest, newDest));
            }
            sameValueSet[arr[dest]].clear();

            if (dest > 0 && shortestPath[dest - 1] == INT32_MAX)
                q.push(make_pair(dest, dest - 1));
            if (dest < (arr.size() - 1) && shortestPath[dest + 1] == INT32_MAX)
                q.push(make_pair(dest, dest + 1));
        }

        return shortestPath[arr.size() - 1];
    }
};

int main()
{
    Solution s;
    vector<int> arr = {100, -23, -23, 404, 100, 23, 23, 23, 3, 404};
    cout << s.minJumps(arr) << endl;
    return 0;
}

Load Comments