Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: 9 Jan, 2021

First and Last Position of an Element In Sorted Array

Easy
Asked in companies
AmazonMicrosoftAdobe

Problem statement

You have been given a sorted array/list 'arr' consisting of ‘n’ elements. You are also given an integer ‘k’.


Now, your task is to find the first and last occurrence of ‘k’ in 'arr'.


Note :
1. If ‘k’ is not present in the array, then the first and the last occurrence will be -1. 
2. 'arr' may contain duplicate elements.


Example:
Input: 'arr' = [0,1,1,5] , 'k' = 1

Output: 1 2

Explanation:
If 'arr' = [0, 1, 1, 5] and 'k' = 1, then the first and last occurrence of 1 will be 1(0 - indexed) and 2.


Input Format
The first line of each test case contains two single-space separated integers ‘n’ and ‘k’, respectively.

The second line of each test case contains ‘n’ single space-separated integers denoting the elements of the array/list 'arr'.


Output Format :
Return two single-space separated integers denoting the first and the last occurrence of ‘k’ in 'arr', respectively.


Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.

Approaches

01 Approach

Naively traverse the array and find the first and last occurrence of ‘K’ in ARR.