Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
Algorithm
3.2.
DRY Run
3.3.
Implementation in C++
3.4.
Implementation in Python
3.5.
Complexity Analysis
4.
Stack Approach
4.1.
Algorithm
4.2.
DRY Run
4.3.
Implementation in C++
4.4.
Implementation in Python
4.5.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
How to calculate the size of the vector?
5.2.
What is index out of bounds?
5.3.
How can we implement an array in python?
5.4.
How to calculate the size of a list in python?
5.5.
What is a recursive function?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if it is possible to reach the index with value K when the start index is given

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

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.

introduction image

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

example input 1

Output

We can reach value k from the given start index.
 

Input

example input 2

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

  1. Initialize the array with a start index and value of ‘k’.
     
  2. Call the reach function to check if it is possible to reach ‘k’.
     
  3. Check the base conditions:
    • if(startx>=(array size)) returns false.
    • if(start<0) return false.
    • If (array[start] == -1) return false
       
  4. If the value at the current index is equal to the value of k, return true.
     
  5. Mark the visited index with -1, and if we revisit the index, return false.
     
  6. Do the recursive calls to reach the function:
    • reach array, start + array[start] ,k).
       
  7. 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.
       
  8.  Return output to the main function.

DRY Run

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

DRY Run example

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.

DRY Run example

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

c++ code 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

python code 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

  1. Initialize a stack to store the indexes.
     
  2. Push the current start index in the stack.
     
  3. Check if the start index is greater than the array size and is a negative integer.
     
  4. If the above conditions are false, compare the values at the start index and value k. Return true if the condition is true.
     
  5. Else, pop out the stack top.
     
  6. Check if the index is visited or not.
     
  7. If not, then store the value of the current start index in a variable.
     
  8. Replace the value at the current index with -1 to mark it as visited,
     
  9. Push the result of (start + array[start]) or (start - array[start]) in the stack.
     
  10. Pop out the current top element from the stack.
     
  11. Now repeat steps 3 to 10 until the stack is empty.
     
  12. At the end of the function, return false.

DRY Run

Input

DRY Run example
DRY Run example

Empty Stack

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

DRY Run example

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.

DRY Run example

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. 

DRY Run example

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.

DRY Run example
DRY Run example

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.

DRY Run example

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.

DRY Run example

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

c++ code 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

python code 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).

Also, check out - Rod Cutting Problem

Frequently Asked Questions

How to calculate the size of the vector?

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.

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Minimize Steps Required to Convert Number N to M.
Next article
Check If Cells Numbered 1 to K In A Grid Can Be Connected After The Removal Of At most One Blocked Cell
Live masterclass