Find the minimum number of moves to reach end of the array

0 0 9 minutes read

Given an array arr[] of size N where every element is from the range [0, 9]. The task is to reach the last index of the array starting from the first index. From i^th index we can move to (i – 1)^th, (i + 1)^thor to any j^th index where j ? i and arr[j] = arr[i].

Examples:

Input: arr[] = {1, 2, 3, 4, 1, 5}
Output: 2
First move from the 0^th index to the 4^th index
and then from the 4^th index to the 5^th.

Input: arr[] = {1, 2, 3, 4, 5, 1}
Output: 1

Approach: Construct the graph from the given array where the number of nodes in the graph will be equal to the size of the array. Every node of the graph i will be connected to the (i 1)^th node, (i + 1)^th node and a node j such that i ? j and arr[i] = arr[j]. Now, the answer will be the minimum edges in the path from index 0 to index N – 1 in the constructed graph.
The graph for the array arr[] = {1, 2, 3, 4, 1, 5} is shown in the image below:

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 100005
 
vector<int> gr[N];
 
// Function to add edge
void add_edge(int u, int v)
{
    gr[u].push_back(v);
    gr[v].push_back(u);
}
 
// Function to return the minimum path
// from 0th node to the (n - 1)th node
int dijkstra(int n)
{
    // To check whether an edge is visited or not
    // and to keep distance of vertex from 0th index
    int vis[n] = { 0 }, dist[n];
 
    for (int i = 0; i < n; i++)
        dist[i] = INT_MAX;
 
    // Make 0th index visited and distance is zero
    vis[0] = 1;
    dist[0] = 0;
 
    // Take a queue and push first element
    queue<int> q;
    q.push(0);
 
    // Continue this until all vertices are visited
    while (!q.empty()) {
        int x = q.front();
 
        // Remove the first element
        q.pop();
 
        for (int i = 0; i < gr[x].size(); i++) {
 
            // Check if a vertex is already visited or not
            if (vis[gr[x][i]] == 1)
                continue;
 
            // Make vertex visited
            vis[gr[x][i]] = 1;
 
            // Store the number of moves to reach element
            dist[gr[x][i]] = dist[x] + 1;
 
            // Push the current vertex into the queue
            q.push(gr[x][i]);
        }
    }
 
    // Return the minimum number of
    // moves to reach (n - 1)th index
    return dist[n - 1];
}
 
// Function to return the minimum number of moves
// required to reach the end of the array
int Min_Moves(int a[], int n)
{
 
    // To store the positions of each element
    vector<int> fre[10];
    for (int i = 0; i < n; i++) {
        if (i != n - 1)
            add_edge(i, i + 1);
 
        fre[a[i]].push_back(i);
    }
 
    // Add edge between same elements
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < fre[i].size(); j++) {
            for (int k = j + 1; k < fre[i].size(); k++) {
                if (fre[i][j] + 1 != fre[i][k]
                    and fre[i][j] - 1 != fre[i][k]) {
                    add_edge(fre[i][j], fre[i][k]);
                }
            }
        }
    }
 
    // Return the required minimum number of moves
    return dijkstra(n);
}
 
// Driver code
int main()
{
    int a[] = { 1, 2, 3, 4, 1, 5 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << Min_Moves(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
import java.util.*;
 
class GFG{
     
static ArrayList<
       ArrayList<Integer>> gr = new ArrayList<
                                    ArrayList<Integer>>();
static int N = 100005;
 
// Function to add edge 
static void add_edge(int u, int v) 
{
    for(int i = 0; i < N; i++)
    {
        gr.add(new ArrayList<Integer>());
    }
    gr.get(u).add(v);
    gr.get(v).add(u);
}
 
// Function to return the minimum path 
// from 0th node to the (n - 1)th node 
static int dijkstra(int n)
{
     
    // To check whether an edge is visited
    // or not and to keep distance of 
    // vertex from 0th index 
    int[] vis = new int[n];
    Arrays.fill(vis, 0);
     
    int[] dist = new int[n];
    for(int i = 0; i < n; i++)
    {
        dist[i] = Integer.MAX_VALUE;
    }
     
    // Make 0th index visited and 
    // distance is zero 
    vis[0] = 1; 
    dist[0] = 0;
     
    // Take a queue and push first element 
    Queue<Integer> q = new LinkedList<>();
    q.add(0);
     
    // Continue this until all vertices 
    // are visited 
    while (q.size() > 0)
    {
         
        // Remove the first element 
        int x = q.poll();
        for(int i = 0; i < gr.get(x).size(); i++)
        {
             
            // Check if a vertex is already 
            // visited or not 
            if (vis[gr.get(x).get(i)] == 1)
            {
                continue;
            }
             
            // Make vertex visited
            vis[gr.get(x).get(i)] = 1;
             
            // Store the number of moves to 
            // reach element
            dist[gr.get(x).get(i)] = dist[x] + 1;
             
            // Push the current vertex into 
            // the queue
            q.add(gr.get(x).get(i));
        }
    }
     
    // Return the minimum number of 
    // moves to reach (n - 1)th index
    return dist[n - 1];
}
 
// Function to return the minimum number of moves 
// required to reach the end of the array 
static int Min_Moves(int[] a, int n) 
{
     
    // To store the positions of each element
    ArrayList<
    ArrayList<Integer>> fre = new ArrayList<
                                  ArrayList<Integer>>();
    for(int i = 0; i < 10; i++)
    {
        fre.add(new ArrayList<Integer>());
    }
    for(int i = 0; i < n; i++)
    {
        if (i != n - 1)
        {
            add_edge(i, i + 1);
        }
        fre.get(a[i]).add(i);
    }
     
    // Add edge between same elements 
    for(int i = 0; i < 10; i++)
    {
        for(int j = 0; 
                j < fre.get(i).size(); 
                j++) 
        {
            for(int k = j + 1; 
                    k < fre.get(i).size(); 
                    k++)
            {
                if (fre.get(i).get(j) + 1 != 
                    fre.get(i).get(k) && 
                    fre.get(i).get(j) - 1 != 
                    fre.get(i).get(k))
                {
                    add_edge(fre.get(i).get(j),
                             fre.get(i).get(k));
                }
            }
        }
    }
     
    // Return the required minimum 
    // number of moves 
    return dijkstra(n);
}
 
// Driver code 
public static void main(String[] args) 
{
    int[] a = { 1, 2, 3, 4, 1, 5 };
    int n = a.length;
     
    System.out.println(Min_Moves(a, n));
}
}
 
// This code is contributed by avanitrachhadiya2155

Python3

# Python3 implementation of the approach
from collections import deque
N = 100005
 
gr = [[] for i in range(N)]
 
# Function to add edge
def add_edge(u, v):
    gr[u].append(v)
    gr[v].append(u)
 
# Function to return the minimum path
# from 0th node to the (n - 1)th node
def dijkstra(n):
     
    # To check whether an edge is visited
    # or not and to keep distance of vertex
    # from 0th index
    vis = [0 for i in range(n)]
    dist = [10**9 for i in range(n)]
 
    # Make 0th index visited and 
    # distance is zero
    vis[0] = 1
    dist[0] = 0
 
    # Take a queue and 
    # append first element
    q = deque()
    q.append(0)
 
    # Continue this until  
    # all vertices are visited
    while (len(q) > 0):
        x = q.popleft()
 
        # Remove the first element
        for i in gr[x]:
 
            # Check if a vertex is 
            # already visited or not
            if (vis[i] == 1):
                continue
 
            # Make vertex visited
            vis[i] = 1
 
            # Store the number of moves 
            # to reach element
            dist[i] = dist[x] + 1
 
            # Push the current vertex
            # into the queue
            q.append(i)
 
    # Return the minimum number of
    # moves to reach (n - 1)th index
    return dist[n - 1]
 
# Function to return the minimum number of moves
# required to reach the end of the array
def Min_Moves(a, n):
 
    # To store the positions of each element
    fre = [[] for i in range(10)]
    for i in range(n):
        if (i != n - 1):
            add_edge(i, i + 1)
 
        fre[a[i]].append(i)
 
    # Add edge between same elements
    for i in range(10):
        for j in range(len(fre[i])):
            for k in range(j + 1,len(fre[i])):
                if (fre[i][j] + 1 != fre[i][k] and
                    fre[i][j] - 1 != fre[i][k]):
                    add_edge(fre[i][j], fre[i][k])
 
    # Return the required 
    # minimum number of moves
    return dijkstra(n)
 
# Driver code
a = [1, 2, 3, 4, 1, 5]
n = len(a)
 
print(Min_Moves(a, n))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
    static List<List<int>> gr = new List<List<int>>();
    static int N = 100005;
   
    // Function to add edge 
    static void add_edge(int u, int v)
    {
        for(int i = 0; i < N; i++)
        {
            gr.Add(new List<int>());
        }
        gr[u].Add(v);
        gr[v].Add(u);
    }
   
    // Function to return the minimum path 
    // from 0th node to the (n - 1)th node 
    static int dijkstra(int n)
    {
       
        // To check whether an edge is visited
        // or not and to keep distance of 
        // vertex from 0th index
        int[] vis = new int[n];
        Array.Fill(vis, 0);
        int[] dist = new int[n];
        for(int i = 0; i < n; i++)
        {
            dist[i] = Int32.MaxValue;
        }
       
        // Make 0th index visited and 
        // distance is zero 
        vis[0] = 1; 
        dist[0] = 0;
         
        // Take a queue and push first element 
        Queue<int> q = new Queue<int>();
        q.Enqueue(0);
         
        // Continue this until all vertices 
        // are visited 
        while(q.Count > 0)
        {
           
            // Remove the first element 
            int x = q.Dequeue();
            for(int i = 0; i < gr[x].Count; i++ )
            {
               
                // Check if a vertex is already 
                // visited or not 
                if(vis[gr[x][i]] == 1)
                {
                    continue;
                }
               
                // Make vertex visited
                vis[gr[x][i]] = 1;
               
                // Store the number of moves to 
                // reach element
                dist[gr[x][i]] = dist[x] + 1;
                 
                // Push the current vertex into 
                // the queue
                q.Enqueue(gr[x][i]);
            }
        }
       
        // Return the minimum number of 
        // moves to reach (n - 1)th index
        return dist[n - 1];
    }
   
    // Function to return the minimum number of moves 
    // required to reach the end of the array 
    static int Min_Moves(int[] a, int n) 
    {
       
        // To store the positions of each element
        List<List<int>> fre = new List<List<int>>();
        for(int i = 0; i < 10; i++)
        {
            fre.Add(new List<int>());          
        }
        for(int i = 0; i < n; i++)
        {
            if (i != n - 1)
            {
                add_edge(i, i + 1);
            }
            fre[a[i]].Add(i);
        }
       
        // Add edge between same elements 
        for(int i = 0; i < 10; i++)
        {
            for(int j = 0; j < fre[i].Count; j++)
            {
                for(int k = j + 1; k < fre[i].Count; k++)
                {
                    if(fre[i][j] + 1 != fre[i][k] && 
                       fre[i][j] - 1 != fre[i][k])
                    {
                        add_edge(fre[i][j], fre[i][k]);
                    }
                }
            }
        }
       
        // Return the required minimum 
        // number of moves 
        return dijkstra(n);
    }
   
    // Driver code 
    static public void Main ()
    {
        int[] a = { 1, 2, 3, 4, 1, 5 };
        int n = a.Length;
        Console.WriteLine(Min_Moves(a, n));
    }
}
 
// This code is contributed by rag2127

Javascript

<script>
// Javascript implementation of the approach
 
let gr = [];
let N = 100005;
 
// Function to add edge
function add_edge(u,v)
{
    for(let i = 0; i < N; i++)
    {
        gr.push([]);
    }
    gr[u].push(v);
    gr[v].push(u);
}
 
// Function to return the minimum path
// from 0th node to the (n - 1)th node
function dijkstra(n)
{
    // To check whether an edge is visited
    // or not and to keep distance of
    // vertex from 0th index
    let vis = new Array(n);
    for(let i = 0; i < vis.length; i++)
    {
        vis[i] = 0;
    }
      
    let dist = new Array(n);
    for(let i = 0; i < n; i++)
    {
        dist[i] = Number.MAX_VALUE;
    }
      
    // Make 0th index visited and
    // distance is zero
    vis[0] = 1;
    dist[0] = 0;
      
    // Take a queue and push first element
    let q = [];
    q.push(0);
      
    // Continue this until all vertices
    // are visited
    while (q.length > 0)
    {
          
        // Remove the first element
        let x = q.shift();
        for(let i = 0; i < gr[x].length; i++)
        {
              
            // Check if a vertex is already
            // visited or not
            if (vis[gr[x][i]] == 1)
            {
                continue;
            }
              
            // Make vertex visited
            vis[gr[x][i]] = 1;
              
            // Store the number of moves to
            // reach element
            dist[gr[x][i]] = dist[x] + 1;
              
            // Push the current vertex into
            // the queue
            q.push(gr[x][i]);
        }
    }
      
    // Return the minimum number of
    // moves to reach (n - 1)th index
    return dist[n - 1];
}
 
// Function to return the minimum number of moves
// required to reach the end of the array
function Min_Moves(a,n)
{
    // To store the positions of each element
    let fre = [];
    for(let i = 0; i < 10; i++)
    {
        fre.push([]);
    }
    for(let i = 0; i < n; i++)
    {
        if (i != n - 1)
        {
            add_edge(i, i + 1);
        }
        fre[a[i]].push(i);
    }
      
    // Add edge between same elements
    for(let i = 0; i < 10; i++)
    {
        for(let j = 0;
                j < fre[i].length;
                j++)
        {
            for(let k = j + 1;
                    k < fre[i].length;
                    k++)
            {
                if (fre[i][j] + 1 !=
                    fre[i][k] &&
                    fre[i][j] - 1 !=
                    fre[i][k])
                {
                    add_edge(fre[i][j],
                             fre[i][k]);
                }
            }
        }
    }
      
    // Return the required minimum
    // number of moves
    return dijkstra(n);
}
 
// Driver code
let a = [1, 2, 3, 4, 1, 5 ];
let n = a.length;
document.write(Min_Moves(a, n));
 
// This code is contributed by unknown2108
</script>

Output:

Time complexity: O(n²)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!