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

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].

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;
}

You can also try this code with Online C++ Compiler

Run 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.")

You can also try this code with Online Python Compiler

Run 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

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;
}

You can also try this code with Online C++ Compiler

Run 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.")

You can also try this code with Online Python Compiler

Run 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.

• Vertex Cover Problem
• Channel Assignment Problem
• Matrix probability problem
• The Stable Marriage Problem
   

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!