Do you think IIT Guwahati certified course can help you in your career?
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.
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
From the current index ‘curr’, we can go to curr + moves[curr]
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.
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.
Hence, we reached the last index of the array, i.e., we reached the end of the array, so the output will be “Yes”.
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
Call the recursive function ‘check()’ to check whether the array's end can be reached.
Make base cases in the recursion function. Two base cases are to be considered, which are as follows:
If the current index ‘curr’ is out of bounds, i.e., curr < 0 or curr > arr. size(), then return false.
If the current index ‘curr’ is equal to the last index of the array, then return true.
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.
At last, if the recursion function returns true, then display the output as “Yes”; else, show the output as “No”.
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";
}
You can also try this code with Online C++ Compiler
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");
}
}
}
You can also try this code with Online Java Compiler
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
Call the ‘check_bfs()’ function to check if the end of the array is reached or not
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.
Initialize a boolean array ‘visited’ to store the status of already visited nodes.
Declare a variable ‘reachable’ to check whether we have reached the last index.
Start a while loop with the condition that it goes on till our queue is non-empty.
Extract the front element of the queue and pop the element from the queue.
If the current index ‘curr’ is already visited, continue the iteration for the next element.
If the current index ‘curr’ is not visited, then:
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.
Else push the corresponding forward and backward indexes possible from this index in the queue.
Return the boolean variable ‘reachable’ from the ‘check_bfs’ function.
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
Initially, our queue is empty, but we push the starting position in our queue.
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.
Now, one new index = 2 is added to the queue, and our queue looks like this:
Now, the next front element with index = 2 is extracted from the queue, and we mark it in the visited array.
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.
Now, two new indexes, 3 and 1, are added to the queue, and our queue looks like this:
Now, the front element is extracted from the queue equal to 3.
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";
}
You can also try this code with Online C++ Compiler
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");
}
}
}
You can also try this code with Online Java Compiler
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.
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 problems, interview experiences, and interview bundles for placement preparations.
However, you may consider our paid courses to give your career an edge over others!
24+ registered 
