Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 📝
2.
Problem Statement 🖥️
2.1.
Algorithm 🌐
2.2.
Code 📝
3.
Frequently Asked Question ❓
3.1.
What is an array?
3.2.
What is Hashing?
3.3.
What is an unordered set in data structure?
3.4.
Whаt is Graph Data Structure?
3.5.
What is a queue in data structure?
4.
Conclusion ✉️
Last Updated: Mar 27, 2024
Medium

Find the minimum steps required to reach the end of the array under constraints

Author Alok Pandey
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

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.

Minimum steps required to reach the end of the array under constraints

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]                                                          

Minimum steps required to reach the end of the array under constraints

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:

Minimum steps required to reach the end of the array under constraints

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Question ❓

What is an array?

An array is a collection of homogeneous values stored at contiguous memory locations. It is like a staircase, in which each value of placed at every step, and elements can be accessed by knowing the stair number (or index number).

What is Hashing?

Hashing is a technique using which a given value can be transformed into another value. It makes searching more accessible and quicker.

What is an unordered set in data structure?

An unordered set is a data structure that is an associative container that holds a collection of singular Key objects. Average constant-time complexity characterizes search, insertion, and removal. Internally, the components are arranged into buckets rather than being sorted in any specific sequence.

Whаt is Graph Data Structure?

A non-linear data structure made up of vertices and edges is called a graph. In a graph, the edges are the lines or arcs that link any two nodes, while the vertices are occasionally also referred to as nodes. 

What is a queue in data structure?

The queue is an Abstract Data Type (ADT) that operates on the First-In-First-Out principle, which states that the element that is placed first gets accessed/deleted/processed first. A queue has two ends known as the front and back.

Conclusion ✉️

In this article, we have extensively discussed the problem of the minimum steps required to reach the end of the array under constraints.. We hope that this blog has helped you enhance your knowledge of the implementation of graph data structure and array traversal and if you would like to learn more, check out our articles on
 

 

Recommended problems -

 

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. 

Enroll in our courses and refer to the mock test and problems available.

Take a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Find Length of the Largest Region in the Boolean Matrix
Next article
Find the Height of a Generic Tree from Parent Array
Live masterclass