1. Last Occurrence of Element

Problem Statement

Find the last occurrence index of an element in an array/vector.

Pattern Used

Linear Recursion / Array Traversal

Approach (High-level)

• Method 1 (Left to Right): Traverse from left to right using recursion, check answer from recursive call first; if found return it, otherwise check current element
• Method 2 (Right to Left): Traverse from right to left using recursion, return immediately when element is found
• Method 3 (STL): Use find() with reverse iterators (rbegin and rend), convert reverse iterator to normal index

Time & Space Complexity

• Time: O(n) for all methods
• Space: O(n) due to recursion call stack for methods 1 and 2, O(1) for method 3

#include <iostream> 
#include <vector>
#include <algorithm>
using namespace std; 

int m3LastOcc(vector<string>&arr,string elem) {
    auto it = find(arr.rbegin(), arr.rend(), elem);
    if (it!=arr.rend()) {
        // Convert reverse iterator to normal index
        return arr.rend()-it-1;
    }
    
    return -1;
}

int m2LastOcc(vector<string> arr,int size,string elem,int i){
  if(i<0){
  return -1;
 }
 
  if(arr[i]==elem) {
   return i;
 }
 return m2LastOcc(arr, size, elem, i-1);
}

int m1LastOcc(vector<string> &arr,int size,string elem,int i){
 if(i>=size){
  return -1;
 }
 int ans=m1LastOcc(arr,size,elem,i+1);

 if(ans!=-1) return ans;

 if(arr[i]==elem) return i;
 
 return -1;
}

int main() {
  vector<string> arr={"a","b","b","b","a","e","f","d","b","a"};
  // int size=arr.size();
  // int index=0;  // for m1
  // int index=arr.size(); //for m2
  string elem="b";
  // int result = m1LastOcc(arr,size,elem,index);
  // int result = m2LastOcc(arr,size,elem,index);
  int result=m3LastOcc(arr,elem);
  cout<<result;
  
    return 0; 
}

2. Reverse String Using Recursion

Problem Statement

Reverse a string using recursive approach.

Pattern Used

Two Pointer / String Manipulation

Approach (High-level)