Problem Statement
Given an array of numbers, we need to find the first and last occurrence of a specific number using recursion.
Example Inputs
- Array: [9, 6, 100, 67, 6, 19]
- Target Number: 6
Output: 1, 4 (the first occurrence is at index 1, and the last occurrence is at index 4)
Approach - Use Recursion
Approach
Recursion is a method where the function calls itself. In this case, the idea is to traverse the array recursively to find both the first and last occurrences of the target number. The first occurrence is found as we encounter the number for the first time while moving through the array, and the last occurrence is found by continuing the search until we reach the last index and encounter the target again.
Steps
- Start from the first index of the array.
- Keep track of the first occurrence of the target.
- Continue recursively until the end of the array to find the last occurrence.
- If the target is not found, return
-1 for both occurrences.
Time & Space Complexity
- Time Complexity: O(n), where n is the number of elements in the array. We have to traverse the array once to find both occurrences.
- Space Complexity: O(n) due to the recursive call stack, where each recursive call takes up space.
Code Snippet
Dry Run
Let’s dry run the code with the array [9, 6, 100, 67, 6, 19] and the target number 6.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 0, -1, -1): Index 0 (value = 9) → not the target, move to index 1.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 1, -1, -1): Index 1 (value = 6) → first occurrence, update first to 1, move to index 2.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 2, 1, -1): Index 2 (value = 100) → not the target, move to index 3.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 3, 1, -1): Index 3 (value = 67) → not the target, move to index 4.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 4, 1, -1): Index 4 (value = 6) → last occurrence, update last to 4, move to index 5.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 5, 1, 4): Index 5 (value = 19) → not the target, move to index 6.
- findOccurrences([9, 6, 100, 67, 6, 19], 6, 6, 1, 4): Reached the end of the array, return [1, 4].
Output:
- First occurrence: 1
- Last occurrence: 4
Complexity Analysis
Time and Space Complexity
- Time Complexity: O(n) because we need to iterate over all elements in the array.
- Space Complexity: O(n) due to the recursion stack.
Conclusion
This solution demonstrates the use of recursion to solve the problem of finding the first and last occurrences of a number in an array. While recursion provides an elegant approach, it may not be the most efficient for large arrays due to the overhead of recursive calls and the use of the call stack. Nonetheless, this approach is clear and helps in understanding how recursion can be applied to solve problems involving arrays.