🚀Day 18/180 Occurence(indices) of a given element (Key) and print them.(Use Recursive function)

Occurence(indices) of a given element (Key) and print them.(Use Recursive function)

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

//For the given integer array of size N. You have to find all the occurrences(indices )
/// of  a given element(Key) and print them. Use a Recursive function to solve this 
/// Problem ...
public class Main {
    public static void arrayIndex(int []arr,int key,int idx){
        //Now setting up the base condition ...
        if(idx==arr.length){
            return;
        }
        if(arr[idx]==key){
        System.out.print(idx+" ");
        }
        arrayIndex(arr,key,idx+1);
        //System.out.println(idx);
    }
    public static void main(String args[]){
        //int []arr = new int [9]; //But here we are dynamically creating a array ...
        //After me dynamically creating an array of a given size we can assign it a value ...
        int arr[]={3,2,4,5,6,2,7,2,2};
        int key=2;
        arrayIndex(arr,key,0);
    }
}
/*
 * PS C:\Users\HP\OneDrive\Coding\Java\Practice01> javac Main.java 
PS C:\Users\HP\OneDrive\Coding\Java\Practice01> java Main
1 5 7 8 
 */

Let's perform a dry run of the code with the given input array {3, 2, 4, 5, 6, 2, 7, 2, 2} and the key 2.

Dry Run

Initial state:

• arr = {3, 2, 4, 5, 6, 2, 7, 2, 2}

• key = 2

• idx = 0

Execution Steps

1. First call: arrayIndex(arr, 2, 0)

   • idx = 0

   • arr[idx] = 3

   • 3 != 2, so no output

   • Recursive call: arrayIndex(arr, 2, 1)

2. Second call: arrayIndex(arr, 2, 1)

   • idx = 1

   • arr[idx] = 2

   • 2 == 2, so print 1

   • Recursive call: arrayIndex(arr, 2, 2)

3. Third call: arrayIndex(arr, 2, 2)

   • idx = 2

   • arr[idx] = 4

   • 4 != 2, so no output

   • Recursive call: arrayIndex(arr, 2, 3)

4. Fourth call: arrayIndex(arr, 2, 3)

   • idx = 3

   • arr[idx] = 5

   • 5 != 2, so no output

   • Recursive call: arrayIndex(arr, 2, 4)

5. Fifth call: arrayIndex(arr, 2, 4)

   • idx = 4

   • arr[idx] = 6

   • 6 != 2, so no output

   • Recursive call: arrayIndex(arr, 2, 5)

6. Sixth call: arrayIndex(arr, 2, 5)

   • idx = 5

   • arr[idx] = 2

   • 2 == 2, so print 5

   • Recursive call: arrayIndex(arr, 2, 6)

7. Seventh call: arrayIndex(arr, 2, 6)

   • idx = 6

   • arr[idx] = 7

   • 7 != 2, so no output

   • Recursive call: arrayIndex(arr, 2, 7)

8. Eighth call: arrayIndex(arr, 2, 7)

   • idx = 7

   • arr[idx] = 2

   • 2 == 2, so print 7

   • Recursive call: arrayIndex(arr, 2, 8)

9. Ninth call: arrayIndex(arr, 2, 8)

   • idx = 8

   • arr[idx] = 2

   • 2 == 2, so print 8

   • Recursive call: arrayIndex(arr, 2, 9)

10. Tenth call: arrayIndex(arr, 2, 9)

    • idx = 9

    • Base condition: idx == arr.length (9 == 9), so return without doing anything.

Final Output

The printed output will be the indices where the key 2 is found:

1 5 7 8

Execution Trace

Here is a summary of the execution trace:

Call: arrayIndex(arr, 2, 0) -> No match, next call
Call: arrayIndex(arr, 2, 1) -> Match, print 1, next call
Call: arrayIndex(arr, 2, 2) -> No match, next call
Call: arrayIndex(arr, 2, 3) -> No match, next call
Call: arrayIndex(arr, 2, 4) -> No match, next call
Call: arrayIndex(arr, 2, 5) -> Match, print 5, next call
Call: arrayIndex(arr, 2, 6) -> No match, next call
Call: arrayIndex(arr, 2, 7) -> Match, print 7, next call
Call: arrayIndex(arr, 2, 8) -> Match, print 8, next call
Call: arrayIndex(arr, 2, 9) -> Base condition met, return

This dry run demonstrates how the function works step-by-step to find all the occurrences of the key in the array.

Time Complexity

The time complexity of the given recursive function can be analyzed by looking at how many times the function arrayIndex is called.

• For each element in the array, the function is called once.

• The function performs a constant amount of work (checking a condition and possibly printing an index) during each call.

If the length of the array is N, the function will be called N times, once for each index from 0 to N-1.

Therefore, the time complexity is: [ O(N) ]

Space Complexity

The space complexity of the given code can be analyzed by considering the space used by the function call stack during recursion.

• In the worst case, the function arrayIndex will make N recursive calls before it terminates. Each of these calls will occupy some space on the call stack.

• The amount of space required for each call is constant (O(1)), as it does not depend on the input size but on the fixed overhead of maintaining function call information.

Thus, the space complexity is: [ O(N) ]

Summary

• Time Complexity: ( O(N) )

  • The function is called once for each element in the array.

• Space Complexity: ( O(N) )

  • The maximum depth of the recursion stack will be equal to the number of elements in the array in the worst case.