Find first and last index

 In an array find the first and last index of a key.

Example 1:

Input: 
N = 6, k = 2
Arr[] = {1, 3, 2 17, 2, 1}
Output: 2 4

Explanation: 2 appears first time at 2nd index and last time at 4th index 

return -1 if not present.

method 1:

Initializes the array b with -1 values for both indices. loop through the array from left to right to find the first occurrence of the key and store its index in b[0]. 

Then loop through the array from right to left to find the last occurrence of the key and store its index in b[1]. If the key is not present in array a, the function returns [-1, -1].

Java implementation:

class codemummy
{ 
    
    static int[] findIndex(int a[], int n, int key) 
    { 
        int b[] = new int[]{-1,-1};
        for(int i=0;i<n;i++){
            if(a[i]==key){
                b[0]=i;
                break;
            }
        }
        
        for(int i=n-1;i>=0;i--){
            if(a[i]==key){
                b[1]=i;
                break;
            }
        }
 
        return b;
    }
}

 Time Complexity: O(n)
Auxiliary Space: O(1).

c++ implementation:

#include <iostream>
#include <vector>

using namespace std;

vector<int> findIndex(int a[], int n, int key) {
    vector<int> b = {-1, -1};
    for(int i=0; i<n; i++){
        if(a[i] == key){
            b[0] = i;
            break;
        }
    }
    
    for(int i=n-1; i>=0; i--){
        if(a[i] == key){
            b[1] = i;
            break;
        }
    }
    
    return b;
}

 Time Complexity: O(n)
Auxiliary Space: O(1).

python implementation:

def findIndex(a, n, key):
    b = [-1, -1]
    for i in range(n):
        if a[i] == key:
            b[0] = i
            break
    
    for i in range(n-1, -1, -1):
        if a[i] == key:
            b[1] = i
            break
    
    return b

 Time Complexity: O(n)
Auxiliary Space: O(1).

method 2:

Initializes the array b with -1 values for both indices. then loop through the array a from index 0 to n-1. If the current element matches the search key and found flag is false, it means it is the first occurrence of the key. So, save the current index as the starting index in b[0] and set the found flag to true. If the current element matches the search key and found flag is true, it means it is the last occurrence of the key. So, it saves the current index as the ending index in b[1]. Finally, it returns the result array b.

Java implementation:

class codemummy
{ 
    static int[] findIndex(int a[], int n, int key) 
    { 
        int b[] = new int[]{-1,-1};
        
        boolean found=false;
        for(int i=0;i<n;i++){
            if(a[i]==key){
                if(!found){
                    b[0]=i;
                    found=true;
                }
                b[1]=i;
            }
        }
 
        return b;
    }
}

 Time Complexity: O(n)
Auxiliary Space: O(1).

c++ implementation:

vector<int> findIndex(int a[], int n, int key) {
    vector<int> b = {-1, -1};
    bool found = false;
    for (int i = 0; i < n; i++) {
        if (a[i] == key) {
            if (!found) {
                b[0] = i;
                found = true;
            }
            b[1] = i;
        }
    }
    return b;
}

 Time Complexity: O(n)
Auxiliary Space: O(1).

python implementation:

def findIndex(a, n, key):
    b = [-1, -1]
    found = False
    for i in range(n):
        if a[i] == key:
            if not found:
                b[0] = i
                found = True
            b[1] = i
    return b

 Time Complexity: O(n)
Auxiliary Space: O(1).