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.
Input
2.2.
Output
2.3.
Explanation
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation in C++
3.3.1.
Output
3.4.
Implementation in Java
3.4.1.
Output
3.5.
Time Complexity
3.6.
Space Complexity
4.
Optimized Approach
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++
4.3.1.
Output
4.4.
Implementation in Java
4.4.1.
Output
4.5.
Time Complexity
4.6.
Space Complexity
5.
Frequently Asked Questions
5.1.
What do you understand by space complexity?
5.2.
What is the Breadth-First Search?
5.3.
What is the time complexity in the best case for finding the Breadth-First Search in a graph?
5.4.
What is recursion? 
5.5.
What is an application of recursion?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if the end of the Array can be Reached from a Given Position

Author Sahil Setia
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

An essential subject for programming interviews is the Array. You'll discover that arrays are used in numerous problems, from complex to easy ones. Since arrays are so standard, you will find them being used in any programming language you select.

Title image

In this blog, we will discuss a problem with checking if the end of the array can be reached from a given position. Before diving directly into the solution, let’s briefly discuss the problem statement.

Problem Statement

We are given ‘N’ positive numbers in an array(0-based indexing) and a starting position, and we are asked to check if the end of the Array can be reached from the given position by performing two operations from the current index. 

The operations are

  1. From the current index ‘curr’, we can go to curr + moves[curr]  
     
  2. From the current index ‘curr’, we can go to curr - moves[curr]  

Input

N = Total number of elements of array = 4

Starting position = 0

Array = [2, 2, 1, 0]

Output

Yes

Explanation

From starting index = 0, jump to index = 2 by taking a jump to the right. As the value at index 0 is arr[0] = 2,i.e., we will take a jump of 2 units to the right and reach an index number equal to 2.

Explanation image 1

From index = 2, jump to index = 3 by taking a jump to the right. As the value at index 2 is arr[2] = 1,i.e., we will take a jump of 1 unit to the right and reach an index number equal to 3 which is our end of the array.

Explanation image 2

Hence, we reached the last index of the array, i.e., we reached the end of the array, so the output will be “Yes”.

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

Brute Force Approach

The brute force approach to check if the end of the array can be reached from a given position will be straightforward if we follow the recursive method. At each index, we will have two choices: to go in the forward direction by arr[curr] or in the backward direction by arr[curr].

Algorithm

  1. Call the recursive function ‘check()’ to check whether the array's end can be reached.
     
  2. Make base cases in the recursion function. Two base cases are to be considered, which are as follows:
     
  3. If the current index ‘curr’ is out of bounds, i.e., curr < 0 or curr > arr. size(), then return false.
     
  4. If the current index ‘curr’ is equal to the last index of the array, then return true. 
     
  5. Call the recursive function ‘check()’ for the current index ‘curr - arr[curr]’ and for the current index ‘curr + arr[curr]’. Take the OR of these two recursive calls as if either of them is true, it simply means the last index of the array was reached.
     
  6. At last, if the recursion function returns true, then display the output as “Yes”; else, show the output as “No”.

Dry Run

Dry Run

Here, a and b demonstrate the values of the corresponding index which we can reach from the current index by taking a jump of arr[curr] units either to the left or right.

As we can see, the Recursion tree above demonstrates the working of the whole recursive approach and why the output is “Yes” as the last index of the array is visited during the recursive call, i.e., the end of the array is reached, and this is the full demonstration of the recursion approach.

Implementation in C++

#include <iostream>
#include <vector>
using namespace std;

// Function for recursion call
bool check(vector <int> &arr, int N, int curr){
    
    /*
        If the index is negative or greater 
        Then the size of the array 
        Then definitely, we can't reach the end.
    */
    if(curr<0 || curr>N){
        return false;
    }
    
    /*
        If we have reached the last index, 
        This means that it is possible to reach the end.
    */
    if(curr==N-1){
        return true;
    }
    
    if(arr[curr]==0){
        return false;
    }
    
    /*
        Using recursion to change position and 
        Checking if we can reach the end of the array.
    */
    return check(arr,N,curr-arr[curr]) || check(arr,N,curr+arr[curr]);
}

// Driver Code for the main function
int main(){
    
    // Total elements in the array
    int N=4;
    
    // Starting position
    int start=0;
    
    // Declaring elements of the array
    vector <int>arr(N);
    arr[0]=2;
    arr[1]=2;
    arr[2]=1;
    arr[3]=0;
    
    bool ans=check(arr,N,start);
    if(ans)
    cout<<"Yes";
    else
    cout<<"No";
}


Output

Output image 1

Implementation in Java

public class MyClass {
    
    // Function for recursion call
    static boolean check(int arr[], int N, int curr){
        
        /*
            If the index is negative or greater 
            Then the size of the array 
            Then definitely, we can't reach the end.
        */
        if(curr<0 || curr>N){
            return false;
        }
        
        /*
            If we have reached the last index, 
            This means that it is possible to reach the end.
        */
        if(curr==N-1){
            return true;
        }
        
        if(arr[curr]==0){
            return false;
        }
        
        /*
            Using recursion to change position and 
            Checking if we can reach the end of the array.
        */
        return check(arr,N,curr-arr[curr]) || check(arr,N,curr+arr[curr]);
    }
    
    // Driver Code for running the main function
    public static void main(String[] args){
        
        // Total elements in the array
        int N=4;
        
        // Starting position
        int start=0;
        
        // Declaring elements of the array
        int [] arr;
        arr=new int[N];
        arr[0]=2;
        arr[1]=2;
        arr[2]=1;
        arr[3]=0;
        
        boolean ans=check(arr,N,start);
        
        if(ans==true){
            
            System.out.println("Yes");
        }
        else{
            
            System.out.println("No");
        }
    }
}


Output

Output image 2

Time Complexity

O(2N) where N = the total number of elements in the array.

Explanation: As in the worst case, we may have to visit the entire array before reaching the last index, and at each index, there are two choices, i.e., going in the forward and backward direction.

Hence, two choices over the entire array yield a time complexity of O(2N).

Space Complexity

O(N) where N = the total number of elements in the array.

Explanation: In the worst case, all elements are traversed once in the recursive call stack, yielding a space complexity of O(N).

Optimized Approach

The optimized approach to this problem includes a graph traversal concept known as Breadth-First Search

In BFS, we are always given a starting node, i.e., in this case, starting position, and each index can have at most two edges originating from it. The first edge corresponds to the forward direction, i.e., curr + arr[curr], and the second edge corresponds to the backward direction, i.e., curr - arr[curr]. Hence, applying the BFS approach here is convenient because it takes much less time than the brute-force solution.

Algorithm

  1. Call the ‘check_bfs()’ function to check if the end of the array is reached or not
     
  2. The queue is initialized in ‘check_bfs’ function to contain the array indexes from which we have to check if the end of the array is reachable or not.
     
  3. Initialize a boolean array ‘visited’ to store the status of already visited nodes.
     
  4. Declare a variable ‘reachable’ to check whether we have reached the last index.
     
  5. Start a while loop with the condition that it goes on till our queue is non-empty.
    1. Extract the front element of the queue and pop the element from the queue.
       
    2. If the current index ‘curr’ is already visited, continue the iteration for the next element. 
       
    3. If the current index ‘curr’ is not visited, then:
      1. If curr is equal to the N - 1, change the value of ‘reachable’ to true as the last index of the array is reached and break the loop here.
         
      2. Else push the corresponding forward and backward indexes possible from this index in the queue.
         
  6. Return the boolean variable ‘reachable’ from the ‘check_bfs’ function.
     
  7.  If ‘reachable’ is true, display the output as “Yes”; otherwise, display the output as “No.”

Dry Run

Let’s look at the visualization of the optimized approach using bfs.

  • Given input array 
Dry run image 1
  • Initially, our queue is empty, but we push the starting position in our queue.
Dry run image 2
  • Now, the front element of the queue is extracted, and we looked for 2 possible solutions: going 2 moves forward or going 2 moves backward. Since moving forward is possible, we will add index = 2 into the queue and move to position 2.
Dry run image 3
  • Now, one new index = 2 is added to the queue, and our queue looks like this:
Dry run image 4
  • Now, the next front element with index = 2 is extracted from the queue, and we mark it in the visited array.
Dry run image 5
  • Now, we looked for 2 possible solutions: going 1 move forward or going 1 move backward. Since moving forward is possible, we will add index = 3 into the queue for the forward possible index and index = 1 into the queue for the backward possible index.
Dry run image 5
  • Now, two new indexes, 3 and 1, are added to the queue, and our queue looks like this:
Dry run image 6
  • Now, the front element is extracted from the queue equal to 3.
Dry run image 7

 

  • As the current index is equal to the array's last position, we have reached the end of the array, and the variable ‘reachable’ is set to true, and we exit from the while loop.
     
  • Finally, ‘reachable,’ which is true, is returned from the function, and “Yes” is displayed as the output.

Implementation in C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
/*
    Bfs function to check if it's
    Possible to reach the last index.
*/
bool check_bfs(vector <int> &arr, int N, int start)
{
 
    // Initialising a queue
    queue<int> q;
 
    /*
        At first, all nodes are unvisited, 
        And we have yet to reach the end.
    */
    vector <bool> visited(N,false);
    bool reachable = false;
 
    // Inserting the first element in the queue
    q.push(start);
 
    // Until the queue becomes empty
    while (!q.empty()) {
 
        // Get the top element and delete it
        int curr_idx = q.front();
        q.pop();
 
        // If you have already visited, ignore that index
        if (visited[curr_idx] == true)
            continue;
 
        visited[curr_idx] = true;
        // When we have reached the end of the array
        if (curr_idx == N - 1) {
            reachable = true;
            break;
        }
 
        /*
            As we can move only temp + arr[temp] or 
            temp - arr[temp], so inserting that in the queue
            and checking that index does not go out of the bound.
        */
        if (curr_idx + arr[curr_idx] < N) {
            q.push(curr_idx + arr[curr_idx]);
        }
 
        if (curr_idx - arr[curr_idx] >= 0) {
            q.push(curr_idx - arr[curr_idx]);
        }
    }
 
    return reachable;
}
 
// Driver Code for the main function
int main(){
    
    // Total elements in the array
    int N=4;
    
    // Starting position
    int start=0;
    
    // Declaring elements of the array
    vector <int>arr(N);
    arr[0]=2;
    arr[1]=2;
    arr[2]=1;
    arr[3]=0;
    
    bool ans=check_bfs(arr,N,start);
    if(ans)
    cout<<"Yes";
    else
    cout<<"No";

}


Output

Output image 3

Implementation in Java

import java.util.LinkedList;

public class MyClass {
    
    /*
        Bfs function to check if it's
        possible to reach the last index.
    */
    static boolean check_bfs(int arr[], int N, int start)
    {
     
        // Initialising a queue for BFS
        LinkedList<Integer> q= new LinkedList<Integer>();
     
        /*
            At first, all nodes are unvisited, and we have not reached the end.
        */
        boolean visited[] = new boolean[N];
        for(int i=0;i<N;i++){
            visited[i]=false;
        }
        boolean reachable = false;
     
        // Inserting first element in the queue
        q.add(start);
     
        // Until the queue becomes empty
        while (q.size()!=0) {
     
            // Get the top element and delete it
            int curr_idx = q.poll();
     
            // If you have already visited ignore that index
            if (visited[curr_idx] == true)
                continue;
            
            visited[curr_idx] = true;
            // When we have reached the end of the array
            if (curr_idx == N - 1) {
                reachable = true;
                break;
            }
     
            /*
                As we can move only temp + arr[temp] or 
                temp - arr[temp], so inserting that in the queue
                and checking that index does not go out of the bound.
            */
            if (curr_idx + arr[curr_idx] < N) {
                q.push(curr_idx + arr[curr_idx]);
            }
     
            if (curr_idx - arr[curr_idx] >= 0) {
                q.push(curr_idx - arr[curr_idx]);
            }
        }
     
        return reachable;
    }
    
    // Driver Code for running the main function
    public static void main(String[] args){
        
        // Total elements in the array
        int N=4;
        
        // Starting position
        int start=0;
        
        // Declaring elements of the array
        int [] arr;
        arr=new int[N];
        arr[0]=2;
        arr[1]=2;
        arr[2]=1;
        arr[3]=0;
        
        boolean ans=check_bfs(arr,N,start);
        
        if(ans==true){
            
            System.out.println("Yes");
        }
        else{
            
            System.out.println("No");
        }
    }
}


Output

Output image 4\

Time Complexity

O(N) where N = total number of elements in the array

Explanation: In the worst case, all the array elements will be traversed only once, which yields a time complexity of O(N).

Space Complexity

O(N) where N = the total number of elements in the array

Explanation: An additional array ‘visited’ of size N is used to keep account of the visited indexes in the array, yielding a space complexity of O(N).

Frequently Asked Questions

What do you understand by space complexity?

The space complexity of a program can be defined as the total space taken in the memory by the algorithm with respect to its input.

What is the Breadth-First Search?

An algorithm called breadth-first search is used to look for nodes in a tree data structure that satisfy a certain property. Before moving on to the nodes which are the next depth level, it begins at the root of the tree and investigates every node there.

What is the time complexity in the best case for finding the Breadth-First Search in a graph?

The best-case time complexity for finding Breadth-First Search in a graph is O(1), i.e. when only a single or no vertex is present in the Graph.

What is recursion? 

Recursion is the method in which a function calls itself its subroutine, which will solve a complex iterative problem by dividing it into sub-tasks.

What is an application of recursion?

Many well-known sorting algorithms (Quick sort, Merge sort, etc.) use recursion.

Conclusion

This article discusses the problem of checking if the end of the array can be reached from a given position. In detail, we have covered two different approaches to solving the problem, and we saw the implementation of the two approaches in C++ and Java. We also discussed the time complexity and Space Complexity of each approach. We would suggest you solve them to gain more confidence in these kinds of problems. These questions are asked during various coding contests as well as placement tests and thus are very important. 

We hope this blog has helped you enhance your knowledge of the array of problems and the Breadth-First Search approach. If you want to enhance more, then check out our blogs.

And many more on our platform Coding Ninjas Studio.

Refer to our Guided Path to upskill yourself in DSACompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio!

But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problemsinterview experiences, and interview bundles for placement preparations.

However, you may consider our paid courses to give your career an edge over others!

Happy Learning, Ninjas!

Previous article
Rotting Oranges Problem
Next article
Minimize Steps Required to Convert Number N to M.
Live masterclass