# Minimum steps to reach end of array under constraints

• Difficulty Level : Hard
• Last Updated : 05 Jul, 2022

Given an array containing one digit numbers only, assuming we are standing at first index, we need to reach to end of array using minimum number of steps where in one step, we can jump to neighbor indices or can jump to a position with same value.
In other words, if we are at index i, then in one step you can reach to, arr[i-1] or arr[i+1] or arr[K] such that arr[K] = arr[i] (value of arr[K] is same as arr[i])

Examples:

```Input : arr[] = {5, 4, 2, 5, 0}
Output : 2
Explanation : Total 2 step required.
and in second step we move to value 0 (End of arr[]).

Input  : arr[] = [0, 1, 2, 3, 4, 5, 6, 7, 5, 4,
3, 6, 0, 1, 2, 3, 4, 5, 7]
Output : 5
Explanation : Total 5 step required.
0(0) -> 0(12) -> 6(11) -> 6(6) -> 7(7) ->
(18)
(inside parenthesis indices are shown)```

This problem can be solved using BFS. We can consider the given array as unweighted graph where every vertex has two edges to next and previous array elements and more edges to array elements with same values. Now for fast processing of third type of edges, we keep 10 vectors which store all indices where digits 0 to 9 are present. In above example, vector corresponding to 0 will store [0, 12], 2 indices where 0 has occurred in given array.

Another Boolean array is used, so that we donâ€™t visit same index more than once. As we are using BFS and BFS proceeds level by level, optimal minimum steps are guaranteed.

Implementation:

## C++

 `// C++ program to find minimum jumps to reach end``// of array``#include ``using` `namespace` `std;` `//  Method returns minimum step to reach end of array``int` `getMinStepToReachEnd(``int` `arr[], ``int` `N)``{``    ``// visit boolean array checks whether current index``    ``// is previously visited``    ``bool` `visit[N];` `    ``// distance array stores distance of current``    ``// index from starting index``    ``int` `distance[N];` `    ``// digit vector stores indices where a``    ``// particular number resides``    ``vector<``int``> digit[10];` `    ``//  In starting all index are unvisited``    ``memset``(visit, ``false``, ``sizeof``(visit));` `    ``//  storing indices of each number in digit vector``    ``for` `(``int` `i = 1; i < N; i++)``        ``digit[arr[i]].push_back(i);` `    ``//  for starting index distance will be zero``    ``distance[0] = 0;``    ``visit[0] = ``true``;` `    ``// Creating a queue and inserting index 0.``    ``queue<``int``> q;``    ``q.push(0);` `    ``//  loop until queue in not empty``    ``while``(!q.empty())``    ``{``        ``// Get an item from queue, q.``        ``int` `idx = q.front();        q.pop();` `        ``//  If we reached to last index break from loop``        ``if` `(idx == N-1)``            ``break``;` `        ``// Find value of dequeued index``        ``int` `d = arr[idx];` `        ``// looping for all indices with value as d.``        ``for` `(``int` `i = 0; i= 0 && !visit[idx - 1])``        ``{``            ``visit[idx - 1] = ``true``;``            ``q.push(idx - 1);``            ``distance[idx - 1] = distance[idx] + 1;``        ``}` `        ``//  checking condition for next index``        ``if` `(idx + 1 < N && !visit[idx + 1])``        ``{``            ``visit[idx + 1] = ``true``;``            ``q.push(idx + 1);``            ``distance[idx + 1] = distance[idx] + 1;``        ``}``    ``}` `    ``//  N-1th position has the final result``    ``return` `distance[N - 1];``}` `//  driver code to test above methods``int` `main()``{``    ``int` `arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 5,``                 ``4, 3, 6, 0, 1, 2, 3, 4, 5, 7};``    ``int` `N = ``sizeof``(arr) / ``sizeof``(``int``);``    ``cout << getMinStepToReachEnd(arr, N);``    ``return` `0;``}`

## Java

 `// Java program to find minimum jumps``// to reach end of array``import` `java.util.*;``class` `GFG``{` `// Method returns minimum step``// to reach end of array``static` `int` `getMinStepToReachEnd(``int` `arr[],``                                ``int` `N)``{``    ``// visit boolean array checks whether``    ``// current index is previously visited``    ``boolean` `[]visit = ``new` `boolean``[N];` `    ``// distance array stores distance of``    ``// current index from starting index``    ``int` `[]distance = ``new` `int``[N];` `    ``// digit vector stores indices where a``    ``// particular number resides``    ``Vector []digit = ``new` `Vector[``10``];``    ``for``(``int` `i = ``0``; i < ``10``; i++)``        ``digit[i] = ``new` `Vector<>();` `    ``// In starting all index are unvisited``    ``for``(``int` `i = ``0``; i < N; i++)``        ``visit[i] = ``false``;` `    ``// storing indices of each number``    ``// in digit vector``    ``for` `(``int` `i = ``1``; i < N; i++)``        ``digit[arr[i]].add(i);` `    ``// for starting index distance will be zero``    ``distance[``0``] = ``0``;``    ``visit[``0``] = ``true``;` `    ``// Creating a queue and inserting index 0.``    ``Queue q = ``new` `LinkedList<>();``    ``q.add(``0``);` `    ``// loop until queue in not empty``    ``while``(!q.isEmpty())``    ``{``        ``// Get an item from queue, q.``        ``int` `idx = q.peek();    ``        ``q.remove();` `        ``// If we reached to last``        ``// index break from loop``        ``if` `(idx == N - ``1``)``            ``break``;` `        ``// Find value of dequeued index``        ``int` `d = arr[idx];` `        ``// looping for all indices with value as d.``        ``for` `(``int` `i = ``0``; i < digit[d].size(); i++)``        ``{``            ``int` `nextidx = digit[d].get(i);``            ``if` `(!visit[nextidx])``            ``{``                ``visit[nextidx] = ``true``;``                ``q.add(nextidx);` `                ``// update the distance of this nextidx``                ``distance[nextidx] = distance[idx] + ``1``;``            ``}``        ``}` `        ``// clear all indices for digit d,``        ``// because all of them are processed``        ``digit[d].clear();` `        ``// checking condition for previous index``        ``if` `(idx - ``1` `>= ``0` `&& !visit[idx - ``1``])``        ``{``            ``visit[idx - ``1``] = ``true``;``            ``q.add(idx - ``1``);``            ``distance[idx - ``1``] = distance[idx] + ``1``;``        ``}` `        ``// checking condition for next index``        ``if` `(idx + ``1` `< N && !visit[idx + ``1``])``        ``{``            ``visit[idx + ``1``] = ``true``;``            ``q.add(idx + ``1``);``            ``distance[idx + ``1``] = distance[idx] + ``1``;``        ``}``    ``}` `    ``// N-1th position has the final result``    ``return` `distance[N - ``1``];``}` `// Driver Code``public` `static` `void` `main(String []args)``{``    ``int` `arr[] = {``0``, ``1``, ``2``, ``3``, ``4``, ``5``, ``6``, ``7``, ``5``,``                 ``4``, ``3``, ``6``, ``0``, ``1``, ``2``, ``3``, ``4``, ``5``, ``7``};``    ``int` `N = arr.length;``    ``System.out.println(getMinStepToReachEnd(arr, N));``}``}` `// This code is contributed by 29AjayKumar`

## Python3

 `# Python 3 program to find minimum jumps to reach end# of array` `# Method returns minimum step to reach end of array``def` `getMinStepToReachEnd(arr,N):``    ` `    ``# visit boolean array checks whether current index``    ``# is previously visited``    ``visit ``=` `[``False` `for` `i ``in` `range``(N)]` `    ``# distance array stores distance of current``    ``# index from starting index``    ``distance ``=` `[``0` `for` `i ``in` `range``(N)]` `    ``# digit vector stores indices where a``    ``# particular number resides``    ``digit ``=` `[[``0` `for` `i ``in` `range``(N)] ``for` `j ``in` `range``(``10``)]` `    ``# storing indices of each number in digit vector``    ``for` `i ``in` `range``(``1``,N):``        ``digit[arr[i]].append(i)` `    ``# for starting index distance will be zero``    ``distance[``0``] ``=` `0``    ``visit[``0``] ``=` `True` `    ``# Creating a queue and inserting index 0.``    ``q ``=` `[]``    ``q.append(``0``)` `    ``# loop until queue in not empty``    ``while``(``len``(q)> ``0``):``        ` `        ``# Get an item from queue, q.``        ``idx ``=` `q[``0``]``        ``q.remove(q[``0``])` `        ``# If we reached to last index break from loop``        ``if` `(idx ``=``=` `N``-``1``):``            ``break` `        ``# Find value of dequeued index``        ``d ``=` `arr[idx]` `        ``# looping for all indices with value as d.``        ``for` `i ``in` `range``(``len``(digit[d])):``            ``nextidx ``=` `digit[d][i]``            ``if` `(visit[nextidx] ``=``=` `False``):``                ``visit[nextidx] ``=` `True``                ``q.append(nextidx)` `                ``# update the distance of this nextidx``                ``distance[nextidx] ``=` `distance[idx] ``+` `1` `        ``# clear all indices for digit d, because all``        ``# of them are processed` `        ``# checking condition for previous index``        ``if` `(idx``-``1` `>``=` `0` `and` `visit[idx ``-` `1``] ``=``=` `False``):``            ``visit[idx ``-` `1``] ``=` `True``            ``q.append(idx ``-` `1``)``            ``distance[idx ``-` `1``] ``=` `distance[idx] ``+` `1` `        ``# checking condition for next index``        ``if` `(idx ``+` `1` `< N ``and` `visit[idx ``+` `1``] ``=``=` `False``):``            ``visit[idx ``+` `1``] ``=` `True``            ``q.append(idx ``+` `1``)``            ``distance[idx ``+` `1``] ``=` `distance[idx] ``+` `1` `    ``# N-1th position has the final result``    ``return` `distance[N ``-` `1``]` `# driver code to test above methods``if` `__name__ ``=``=` `'__main__'``:``    ``arr ``=` `[``0``, ``1``, ``2``, ``3``, ``4``, ``5``, ``6``, ``7``, ``5``, ``4``, ``3``, ``6``, ``0``, ``1``, ``2``, ``3``, ``4``, ``5``, ``7``]``    ``N ``=` `len``(arr)``    ``print``(getMinStepToReachEnd(arr, N))``    ` `# This code is contributed by``# Surendra_Gangwar`

## C#

 `// C# program to find minimum jumps``// to reach end of array``using` `System;``using` `System.Collections.Generic;` `class` `GFG``{` `// Method returns minimum step``// to reach end of array``static` `int` `getMinStepToReachEnd(``int` `[]arr,``                                ``int` `N)``{``    ``// visit boolean array checks whether``    ``// current index is previously visited``    ``bool` `[]visit = ``new` `bool``[N];` `    ``// distance array stores distance of``    ``// current index from starting index``    ``int` `[]distance = ``new` `int``[N];` `    ``// digit vector stores indices where a``    ``// particular number resides``    ``List<``int``> []digit = ``new` `List<``int``>[10];``    ``for``(``int` `i = 0; i < 10; i++)``        ``digit[i] = ``new` `List<``int``>();` `    ``// In starting all index are unvisited``    ``for``(``int` `i = 0; i < N; i++)``        ``visit[i] = ``false``;` `    ``// storing indices of each number``    ``// in digit vector``    ``for` `(``int` `i = 1; i < N; i++)``        ``digit[arr[i]].Add(i);` `    ``// for starting index distance will be zero``    ``distance[0] = 0;``    ``visit[0] = ``true``;` `    ``// Creating a queue and inserting index 0.``    ``Queue<``int``> q = ``new` `Queue<``int``>();``    ``q.Enqueue(0);` `    ``// loop until queue in not empty``    ``while``(q.Count != 0)``    ``{``        ``// Get an item from queue, q.``        ``int` `idx = q.Peek();    ``        ``q.Dequeue();` `        ``// If we reached to last``        ``// index break from loop``        ``if` `(idx == N - 1)``            ``break``;` `        ``// Find value of dequeued index``        ``int` `d = arr[idx];` `        ``// looping for all indices with value as d.``        ``for` `(``int` `i = 0; i < digit[d].Count; i++)``        ``{``            ``int` `nextidx = digit[d][i];``            ``if` `(!visit[nextidx])``            ``{``                ``visit[nextidx] = ``true``;``                ``q.Enqueue(nextidx);` `                ``// update the distance of this nextidx``                ``distance[nextidx] = distance[idx] + 1;``            ``}``        ``}` `        ``// clear all indices for digit d,``        ``// because all of them are processed``        ``digit[d].Clear();` `        ``// checking condition for previous index``        ``if` `(idx - 1 >= 0 && !visit[idx - 1])``        ``{``            ``visit[idx - 1] = ``true``;``            ``q.Enqueue(idx - 1);``            ``distance[idx - 1] = distance[idx] + 1;``        ``}` `        ``// checking condition for next index``        ``if` `(idx + 1 < N && !visit[idx + 1])``        ``{``            ``visit[idx + 1] = ``true``;``            ``q.Enqueue(idx + 1);``            ``distance[idx + 1] = distance[idx] + 1;``        ``}``    ``}` `    ``// N-1th position has the final result``    ``return` `distance[N - 1];``}` `// Driver Code``public` `static` `void` `Main(String []args)``{``    ``int` `[]arr = {0, 1, 2, 3, 4, 5, 6, 7, 5,``                ``4, 3, 6, 0, 1, 2, 3, 4, 5, 7};``    ``int` `N = arr.Length;``    ``Console.WriteLine(getMinStepToReachEnd(arr, N));``}``}` `// This code is contributed by PrinciRaj1992`

## Javascript

 ``

Output

`5`

This article is contributed by Utkarsh Trivedi. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

My Personal Notes arrow_drop_up