First and Last Occurrences of X

Problem

Given a sorted array having N elements, find the indices of the first and last occurrences of an element X in the given array.

Note: If the number X is not found in the array, return '-1' as an array.

Examples:

Example 1:

Input:
N = 4 , X = 3
arr[] = { 1, 3, 3, 4 }
Output:
1 2
Explanation:
For the above array, first occurence of X = 3 is at index = 1 and last occurence is at index = 2.

Example 2:

Input:
N = 4, X = 5
arr[] = { 1, 2, 3, 4 }
Output:
-1
Explanation: 
As 5 is not present in the array, so the answer is -1.

Your task:

ou don't need to read input or print anything. Complete the function firstAndLast() that takes the array arr, its size N and the value X as input parameters and returns a list of integers containing the indices of first and last occurence of X.

• Expected Time Complexity: $O(log(N))$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^5$
• $0 <= arr[i], X <= 10^9$

Solution

Python

def firstAndLast(self, arr, n, x): 
    first = -1
    last = -1
    for i in range(n):
        if x != arr[i]:
            continue
        if first == -1:
            first = i
        last = i
    if first != -1:
        return [first, last]
    else:
        return [-1]

Java

public ArrayList<Integer> firstAndLast(int arr[], int n, int x){
    ArrayList<Integer> result = new ArrayList<>();
    int first = -1;
    int last = -1;
    for (int i = 0; i < n; i++) {
        if (x != arr[i]) {
            continue;
        }
        if (first == -1) {
            first = i;
        }
        last = i;
    }
    if (first != -1) {
        result.add(first);
        result.add(last);
    } 
    else {
        result.add(-1);
    }
    return result;
}

C++

vector<int> firstAndLast(vector<int> &arr, int n, int x) {
    vector<int> result;
    int first = -1;
    int last = -1;
    for (int i = 0; i < n; i++) {
        if (x != arr[i]) {
            continue;
        }
        if (first == -1) {
            first = i;
        }
        last = i;
    }
    if (first != -1) {
        result.push_back(first);
        result.push_back(last);
    } 
    else {
        result.push_back(-1);
    }
    return result;
}

C

int* firstAndLast(int *arr, int n, int x, int *resultSize) {
    int *result = (int *)malloc(2 * sizeof(int));
    if (result == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE);
    }
    int first = -1;
    int last = -1;
    for (int i = 0; i < n; i++) {
        if (x != arr[i]) {
            continue;
        }
        if (first == -1) {
            first = i;
        }
        last = i;
    }
    if (first != -1) {
        result[0] = first;
        result[1] = last;
        *resultSize = 2;
    } 
    else {
        result[0] = -1;
        *resultSize = 1;
    }
    return result;
}

• Time Complexity: $O(log(N))$
• Auxiliary Space: $O(1)$