This blog will discuss a challenging problem you might have to solve during your coding interviews. You can also learn this problem to understand traversing more clearly.

The problem we will discuss is known as Jump Game III on various coding platforms. Let’s understand the problem statement now without any delay.

Problem Statement

We will give an array or vector of ‘N’ elements with index values i and 'k'. Our task is to find out whether we can reach an index whose value is 'k' from the start index value. You can follow two paths to reach that particular index at value 'k', or there are two ways to iterate through the array to reach the value 'k'.

If you are on a current index i, you can either go (i + array[i]) or (i - array[i]). For example, if you are at index 2 with a value of 3, you can go to 2+3=5, or you can go 2-3=-1 which is impossible because you have to remain in the bound of the array index.

If you can reach that particular index with value k, then we will return true as output; else, false.

Example

Input

Output

We can reach value k from the given start index.

Input

Output

We cannot reach value k from the given start index.

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

Approach

Now that we have understood the problem statement, let's talk about the solution to the problem. We will use a recursive approach to solve this problem because, from the problem statement, we can observe that we need to traverse the array with two cases, i.e., (i + array[i]) or (i - array[i]) again and again.

We must add a few conditions during the Recursion to give us the output.

First, we need to ensure the start index is smaller than the size of the array because we cannot traverse out of the bound of the array.

Second, we need to ensure that the start index is not smaller than 0, which also arrays out of bounds.

At last, we will ensure we refrain from revisiting the same index during the recursion. We will return false for that particular recursion if any conditions are true.

During the recursion, along with these three conditions, we will look for our desired value, and if we find that value, we will return true.

Algorithm

Initialize the array with a start index and value of ‘k’.

Call the reach function to check if it is possible to reach ‘k’.

Check the base conditions:

if(startx>=(array size)) returns false.

if(start<0) return false.

If (array[start] == -1) return false

If the value at the current index is equal to the value of k, return true.

Mark the visited index with -1, and if we revisit the index, return false.

Do the recursive calls to reach the function:

reach array, start + array[start] ,k).

After getting the result from the above call again, do a call to function.

reach array, start - array[start] ,k).

Perform the recursion until both are not false.

Return output to the main function.

DRY Run

We have taken an array = [2, 0, 1].

First Recursive Call

current _index = start + array[start] where start = 1 and array[start] = 1.

current_index = 2 + 1 = 3.

start = current_index.

Now start is greater than the size of the given array, this violates our condition start < arraySize. We will return false in this call.

Second Recursive Call

current_index = start - array[start] where start = 1 and array[start] = 1.

current_index = 2 - 1 = 1.

Start = current_index.

Our new start will be 1. We will check whether the value in array[1] is equal to k or not.

We can observe that the value at start =1 equals the input value k, which is zero. We can reach the value k from the given start index.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
// Function to check the reach
bool reach(vector<int>& arr, int start, int k) {
// Comparing the start index with size of array and O index.
// Also checking the visted index.
if ( start >= arr.size() || start < 0 || arr[start] < 0 ) return false;
// If current value is k returning true
if ( arr[start] == k ) return true;
int x = arr[start];
// Marking the visted element.
arr[start] = -1;
// Recursive calls until we get true in both or false in one call.
return reach(arr, start+x, k) || reach(arr, start-x, k);
}
int main(){
vector<int>arr{2,0,1};
// Given start and end
int start = 2;
int K = 0;
// Function Call
bool flag = reach(arr,start,K);
if (flag)
cout << "We can reach value k from the given start index.";
else
cout << "We cannot reach value k from the given start index.";
return 0;
}

Output

Implementation in Python

# Function to check the reach.
def reach(array,start,k):
# Checking if the start index is out of bounds of array size.
# Also, if the current index is already visited, return false.
if(start>=len(array) or start<0 or array[start] < 0):
return False
# Return true k is equal to the value at the current index.
if(array[start]== k):
return True
x = array[start]
# Marking the visited index as -1.
array[start] = -1
# Performing recursion from the right and left side of the start index.
return reach(array,start+x,k) or reach(array,start-x,k)
if __name__ == "__main__":
array = [2,0,1]
start = 2
k = 0
result = reach(array,start,k)
if(result):
print("We can reach value k from the given start index.")
else:
print("We cannot reach value k from the given start index.")

Output

Complexity Analysis

The time complexity for this approach will be O(N), where ‘N’ is the number of elements, and we will traverse the ‘N’ times recursively in the worst case.

The space complexity will be O(N), where ‘N’ is the number of elements in the array, so the total space complexity will be O(N).

Stack Approach

In this approach, we will use stack to add the cases (i + array[i]) or (i - array[i]). We will compare the values at indexes inserted in the stack individually. We will also check the conditions.

The index is smaller than the array size.

Non-negative element.

If the top element index in the stack satisfies the two conditions, then we will compare the value of that index with value k. If the value at the current index equals value k, we will return true. Else we will pop out the element from the stack.

Then we will check if the current index is visited or not. If not visited, then we will add the cases of (i + array[i]) or (i - array[i]) in the stack and mark the current index as visited so we do not again apply the operations on that index. We will perform the operations until the stack is empty

Algorithm

Initialize a stack to store the indexes.

Push the current start index in the stack.

Check if the start index is greater than the array size and is a negative integer.

If the above conditions are false, compare the values at the start index and value k. Return true if the condition is true.

Else, pop out the stack top.

Check if the index is visited or not.

If not, then store the value of the current start index in a variable.

Replace the value at the current index with -1 to mark it as visited,

Push the result of (start + array[start]) or (start - array[start]) in the stack.

Pop out the current top element from the stack.

Now repeat steps 3 to 10 until the stack is empty.

At the end of the function, return false.

DRY Run

Input

Empty Stack

First, we will enter the start index in the stack, which we will take as input from the user.

Now we will check the conditions for the top element in the stack. Here, the stack top is 2, which will be our start index,

Start should be smaller than the array size, which is 3.

Start should be a positive integer

The current start index satisfies both conditions, and we will further execute the statements.

Now we will check if the value at index 2 equals the ‘k’ value. At index 2, the value is 1, and k = 0 is not equal. If the values are not equal, we will remove the top element.

Empty Stack

Further, we will add the cases of (start + array[start]) or (start - array[start]). First, we will add the result of (start - array[start]), which is 1, then (start + array[start]), which is 4.

We will also maintain an array to check if we are not revisiting the same index. If we are not revisiting, then we will execute the above logic.

Again we will apply the base conditions.

Start should be smaller than the array size, which is 3.

Start should be a positive integer

Here, the current start index, which is 4, does not satisfy the first condition so we will remove the top from the stack.

The new start index is 1; now, check base conditions again.

Start should be smaller than the array size, which is 3.

Start should be a positive integer

Start = 1 satisfies the conditions.

Compare the value at index =1 and value ‘k’. Value at index = 1 is 0, and ‘k’ = 0. Both are equal and will return true.

We can conclude that we can reach the value ‘k’ from the given start index.

Implementation in C++

#include<bits/stdc++.h>
using namespace std;
// Function to check the reach
bool reach(vector < int > & arr, int start, int k) {
// Intializing the stack.
stack < int > dfs;
// Inserting the start index in stack.
dfs.push(start);
// Iterating over the array to compare with k until the stack is empty.
while (!dfs.empty()) {
int temp = dfs.top();
// Checking the array boundings
if (temp < arr.size() && temp >= 0) {
// Returning true if the value is found.
if (arr[temp] == 0) {
return true;
}
dfs.pop();
// Checking if the value is visited or not.
if (arr[temp] != -1) {
int x = arr[temp];
arr[temp] = -1;
dfs.push(temp - x);
dfs.push(temp + x);
}
} else {
dfs.pop();
}
}
return false;
}
int main() {
vector<int>arr{2,0,1};
// Given start and end
int start = 2;
int K = 0;
// Function Call
bool flag = reach(arr, start, K);
if (flag)
cout << "We can reach value k from the given start index.";
else
cout << "We cannot reach value k from the given start index.";
return 0;
}

Output

Implementation in Python

# Function to check the reach.
def reach(arr,start,k):
# Intializing stack.
dfs = []
# Pushin Start index.
dfs.append(start)
# Iterating over the array to compare with k until the stack is empty.
while(len(dfs)!=0):
temp = dfs[-1]
# Checking the array boundings
if(temp < len(arr) and temp >=0):
# Returning true if value is found.
if(arr[temp]==0):
return True
dfs.pop()
# Checking if value is visited or not.
if(arr[temp]!=-1):
x = arr[temp]
arr[temp] = -1
dfs.append(temp+x)
dfs.append(temp-x)
else:
dfs.pop()
return False
if __name__ == "__main__":
array = [2,0,1]
start = 2
k = 0
result = reach(array,start,k)
if(result):
print("We can reach value k from the given start index.")
else:
print("We cannot reach value k from the given start index.")

Output

Complexity Analysis

The time complexity for this approach will be O(N), where ‘N’ is the number of elements.

The space complexity will be O(N), where ‘N’ is the number of elements inserted into the stack, so the total space complexity will be O(N).

To calculate the size of the vector, you can use the size() function. vector.size() will be the size of the vector.

What is index out of bounds?

When we try to access an index that is not in the bound or we can say that is greater or negative in size compared to the size of array is called an index out of bounds.

How can we implement an array in python?

We can use a list data structure in python to implement an array in python.

How to calculate the size of a list in python?

We can use python's len() method to calculate the list size.

What is a recursive function?

The function that calls itself repeatedly until a base condition is true in that function is called a recursive function.

Conclusion

In this blog, we have discussed how to check whether we can reach value K with start index ‘i’ in a given array. We have also implemented the problem in C++ and Python.

To learn more programming problems check out the following links.