Home » Interview coding problems/challenges

First and last occurrence of an element

First and last occurrence of an element: Given a sorted array with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array.
Submitted by Divyansh Jaipuriyar, on August 21, 2020

Problem statement

Given a sorted array with possibly duplicate elements, the task is to find indexes of first and last occurrences of an element x in the given array.

Problem description:

The problem wants you to find the position (index) first occurrence and last occurrence of the element x given in the problem. The main catch here is to use the fact that array is already sorted.

Input

The first line consists of an integer T i.e. number of test cases. The first line of each test case contains two integers n and x. The second line contains n spaced integers.

Output

Print index of the first and last occurrences of the number x with a space in between.

Constraints

1<=T<=1000
1<=n,a[i]<=100005

Examples

Input:
T=1
N=9,x=3
[1,2,3,3,3,3,3,3,33]

Output:
2 7,
since 3 occurs at index 2 and 7.

Input:
T=1
N=8,x=5
[1,2,3,5,5,5,7,8]

Output:
3 5,
since 5 occurs at index 3 and 5.

Solution Approach

(a) Brute Force Approach:

The problem can be solved using the naive algorithm, we will travel from first to the last element of the array, which will take O(n) time for traversal and store the first and last occurrence of the element x.

b) Binary Search Approach:

In this approach we will use the concept of binary search, for finding the first occurrence of the element x we follow:

• If we found the element at index mid, where mid=(l+r)/2, then we will store it in some variable first, and then we will do our further search operation on the left side of the mid-point.
  i.e. r=mid-1.

For finding the last occurrence of the element x we will perform:

• If we found the element at index mid, where mid=(l+r)/2, then we will store it in some variable second, and then we will do our further search operation on the right side of the mid-point.
  i.e. l=mid+1.

Time Complexity for the above approach in the worst case is: O(logn)

Space Complexity for the above approach in the worst case is: O(1)

C++ Implementation (Brute Force Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve(ll arr[], ll n, ll x)
{
    //initialize two variable first
    //and second with -1.
    ll first = -1;
    ll last = -1;

    //alliteratively travel all elements.
    for (ll i = 0; i < n; i++) {
        //if encounter for first time.
        if (arr[i] == x and first == -1)
            first = i;
        //last occurrence.
        if (arr[i] == x and first != -1)
            last = i;
    }

    //if element is the array.
    if (first != -1)
        cout << first << " " << last << "\n";
    else
        cout << -1 << "\n";
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;

    while (t--) {
        cout << "Enter size of array and element x: ";
        ll n, x;
        cin >> n >> x;

        ll arr[n];

        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //call solve function.
        solve(arr, n, x);
    }
 
    return 0;
}

Output

Enter number of test cases: 3
Enter size of array and element x: 9 3
Enter elements: 1 2 3 3 3 3 3 3 3        
2 8
Enter size of array and element x: 5 2
Enter elements: 1 2 3 4 5
1 1
Enter size of array and element x: 3 9
Enter elements: 1 1 1
-1

C++ Implementation (Binary Search Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

void solve(ll arr[], ll n, ll x)
{
    ll l, r;
 
    //initialize left index for
    //binary search with 0.
    l = 0;
 
    //initialize right index for
    //binary search with n-1.
    r = n - 1;
 
    //initialize first and last
    //variable with -1.
    ll first = -1;
    ll last = -1;

    //perform binary search.
    while (l <= r) {
        //mid index=(l+r)/2.
        //avoid maximum overflow condition.
        ll mid = l + (r - l) / 2;

        //if array element is equal
        //to x.
        if (arr[mid] == x) {
            first = mid; //assign first index.
            r = mid - 1; //move in left range.
        }
        //if mid element is greater than
        //element x.
        if (arr[mid] > x)
            r = mid - 1;
        //if mid element is smaller than
        //element x.
        if (arr[mid] < x)
            l = mid + 1;
    }

    //again initialize left and right index.
    l = 0;
    r = n - 1;

    //perform binary search.
    while (l <= r) {
        //mid index.
        ll mid = l + (r - l) / 2;
        if (arr[mid] == x) {
            last = mid; //assign right index.
            l = mid + 1; //move in right range.
        }
        //if mid element is greater.
        if (arr[mid] > x)
            r = mid - 1;
        //if mid element is smaller.
        if (arr[mid] < x)
            l = mid + 1;
    }
    //if first is not -1.
    if (first != -1)
        cout << first << " " << last << "\n";
    else
        cout << -1 << "\n";
}

int main()
{
    ll t;
    cout << "Enter number of test cases: ";
    cin >> t;
 
    while (t--) {
        cout << "Enter size of array and element x: ";
        ll n, x;
        cin >> n >> x;
 
        ll arr[n];
 
        cout << "Enter elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];
 
        //call solve function.
        solve(arr, n, x);
    }
 
    return 0;
}

Output

Enter number of test cases: 2  
Enter size of array and element x: 9 2
Enter elements: 1 2 2 2 2 2 2 2 2         
1 8
Enter size of array and element x: 5 -2
Enter elements: 1 2 3 4 5 
-1