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
, 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.**mid=(l+r)/2**

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
, 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.**mid=(l+r)/2**

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions