Introduction 📝
In this article, we’ll be looking at the problem named minimum steps required to reach the end of the array under constraints. We will solve this problem with the help of the graph concept. We will also discuss the step-wise algorithm and the time and space complexity.
Problem Statement 🖥️
You are given an array containing single-digit numbers only, assuming you are standing at the first index, you need to find the minimum steps required to reach the end of the array under constraints. where in one step, you can jump to neighbor indices or can jump to a position with the same value. I.e, if you are at index i, you can go to arr[i+1] or arr[i-1] or arr[j]. Where arr[j] = arr[i]
Examples:
Input : arr[] = {5, 4, 2, 5, 0}
Output: 2
Explanation: A total of 2 steps are required.
We start from arr[0], in the first step jump to the next 5 arr[3]
and in the second step, we move to value 0 (End of arr[]). Hence the minimum steps required to reach the end of the array under constraints is 2.
Input : arr[] = [0,3,1,2,1,5,6,7,8,3,1]
Output: 3
Explanation: A total of 3 steps are required. The minimum steps required to reach the end of the array under constraints is 3.
arr[0] → arr[1] → arr[10] → arr[11]
Algorithm 🌐
-
Initialize a map to store the indexes of the values.
-
Create the graph for the given values of the array.
- Apply BFS traversal to find the minimum steps required to reach the end of the array, which is the destination node.
Code 📝
/* Program for Minimum steps required to reach the end of the array under constraints.*/
#include <bits/stdc++.h>
using namespace std;
// Helper Function to find the answer.
void helper(vector<int> &vec, int n)
{
// Map to store the indexes of the values.
map<int, vector<int>> mp;
// Create graph.
vector<vector<int>> graph(n + 1);
int i = 0;
for (i = 0; i < n; i++)
{
mp[vec[i]].push_back(i);
}
for (int i = 0; i < n; i++)
{
// Add edge from i to i-1.
if (i != 0)
graph[i].push_back(i - 1);
// Add edge from i to i+1.
if (i != n - 1)
graph[i].push_back(i + 1);
// Add edges for duplicate elements.
for (auto it : mp[vec[i]])
if (it != i)
graph[i].push_back(it);
}
// Queue for BFS.
queue<int> q;
q.push(0);
// Boolean visited array.
vector<bool> vis(n, 0);
int ans = 0;
vis[0] = 1;
while (not q.empty())
{
int sz = q.size();
while (sz)
{
int p = q.front();
q.pop();
// Answer Matched.
// Breaking Loop.
if (p == n - 1)
break;
for (auto it : graph[p])
{
if (vis[it] == 0)
{
vis[it] = 1;
q.push(it);
}
}
sz--;
}
if (sz > 0)
break;
ans++;
}
cout << ans;
}
int main()
{
int n;
cin >> n;
vector<int> vec(n);
// Taking vector as an input.
for (auto &it : vec)
cin >> it;
// Function Call.
helper(vec, n);
return 0;
}
Input
19
0, 1, 2, 3, 4, 5, 6, 7, 5, 4, 3, 6, 0, 1, 2, 3, 4, 5, 7
Output
5
Explanation:
The minimum steps required to reach the end of the array under constraints is 5.
📍Time complexity: O(n+e)
Where n is no of nodes and e is the number of edges.
📍Auxiliary Space: O(n+e)
Where n is no of nodes and e is the number of edges.
Check out this problem - Find Duplicate In Array
569+ registered 
