Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Find First and Last Position of Element in Sorted Array

Easy
0/40
Average time to solve is 20m
126 upvotes
Asked in companies
AmazonGoogleTech Mahindra

Problem statement

You are given a non-decreasing array 'arr' consisting of 'n' integers and an integer 'x'. You need to find the first and last position of 'x' in the array.


Note: 
1. The array follows 0-based indexing, so you need to return 0-based indices.
2. If 'x' is not present in the array, return {-1 -1}.
3. If 'x' is only present once in the array, the first and last position of its occurrence will be the same.


Example: 
Input:  arr = [1, 2, 4, 4, 5],  x = 4

Output: 2 3

Explanation: The given array’s 0-based indexing is as follows:
 1      2     4     4     5
 ↓      ↓     ↓     ↓     ↓
 0      1     2     3     4

So, the first occurrence of 4 is at index 2, and the last occurrence of 4 is at index 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains the integer 'n', denoting the size of the sorted array.
The second line contains 'n' space-separated integers denoting the array elements.
The third line contains the value 'x', whose first and last position of occurrence you need to find.
Output Format: 
The only line of output should contain two space-separated integers, where the first and second integer will be the first and the last position of occurrence of 'x', respectively, in the array.
Constraints: 
 1 <= n <= 10^4
-10^9 <= arr[i] <= 10^9
-10^9 <= x <= 10^9
 Time Limit: 1sec


Expected Time Complexity: 
Try to solve the problem in O(log(N)) time complexity.
Sample Input 1:
5
-10 -5 -5 -5 2
-5
Sample Output 1:
1 3
Explanation for Sample Input 1:
The given array’s 0-based indexing is as follows:
-10    -5    -5    -5     2
 ↓      ↓     ↓     ↓     ↓
 0      1     2     3     4

So, the first occurrence of -5 is at index 1, and the last occurrence of -5 is at index 3.
Sample Input 2:
4
1 2 3 4
-1
Sample Output 2:
-1 -1
Explanation for Sample Input 2:
The given array 'arr' is:[1, 2, 3, 4] and 'x' = -1.
In this case 'x' is not present in the array.
Hence, we return {-1,-1}.
Hint

Naively find first and the last occurrence.

Approaches (2)
Naively find first and the last occurrence
  • Create two storage variables ‘IDX1’ and ‘IDX2’ to store the first and last position of occurrence and initialise them to -1.
  • Iterate through the array, if you encounter an array element equal to value ‘X’, and ‘IDX1’ = ‘IDX2’ = -1 previously, then update ‘IDX1’, ‘IDX2’ to the current index.
  • If ‘IDX1’ != -1 and you encounter an array element equal to value ‘X’, then only update ‘IDX2’ as then you had already recorded the first occurrence
  • Finally, return ‘IDX1’ and ‘IDX2’.
Time Complexity

O(N), where ‘N’ is the size of the sorted array.

 

Since here a linear search is being used for traversing and searching through all the ‘N’ elements of the sorted array, therefore, the worst-case time complexity becomes O(N). 

Space Complexity

O(1), as we are using constant extra memory.

Code Solution
(100% EXP penalty)
Find First and Last Position of Element in Sorted Array
All tags
Sort by
Search icon
profile
Jaeson Karter Joseph

Interview problems

Python Code 


def findCiel(arr,x):
    low = 0
    high = len(arr) - 1
    while low<= high:
        mid = (low+high)//2

        if arr[mid] <= x:
            low = mid+1
        else:
            high = mid - 1
    return high


def findFloor(arr,x):
    low = 0
    high = len(arr) - 1
    while low<=high:
        mid = (low + high)//2
        if arr[mid] >= x:
            high = mid - 1
        else:
            low = mid + 1

    return low


def searchRange(arr: [int], x: int) -> [int]:
    # Write your code here.
    first_occ = findFloor(arr,x)
    last_occ = findCiel(arr,x)
    if first_occ -1 == last_occ:
        return [-1,-1]
    
    return [first_occ,last_occ]
9 views
0 replies
0 upvotes
profile
Nithya Munagapati

Interview problems

Easy Java Solution

public class Solution {

    public static int[] searchRange(int []arr, int x) {

        // Write your code here.

        int[] ar=new int[2];

        ar[0]=-1;

        ar[1]=-1;

        for(int i=0;i<arr.length;i++){

            if(arr[i]==x){

                ar[0]=i;

                for(int j=i;j<arr.length;j++){

                    if(arr[i]==arr[j]) ar[1]=j;

                    else break;

                }

                break;

            }

        }

        return ar;

    }

}

7 views
0 replies
0 upvotes
profile
Shantanu Kulkarni

Interview problems

Beginner friendly approach O(n) with explanation 

public class Solution {
    public static int[] searchRange(int []arr, int x) {
        // Write your code here.
        
        int a[] = new int[2];
        //For first position we traverse from 0 to x position.
        for(int i=0; i<arr.length;i++){
            if(arr[i]==x){
                a[0]=i;
                break;
            }else{
                a[0]=-1;
            }
        }

        //For last position we traverse reverse from last element to x position.
        for(int i=arr.length-1; i>=0;i--){
            if(arr[i]==x){
                a[1]=i;
                break;
            }else{
                a[1]=-1;
            }
        }
        return a;
    }
}
36 views
0 replies
0 upvotes
profile
Bhola kumar

Interview problems

Find First and Last Position of Element in Sorted Array

Basic Approach: Binary Search

 Steps:

1> first we find lowerBound 

2> Second we find UpperBound

 

when we call both method in main function we check our lowerbound is equal to array length or not present in array if true then return {-1,-1}

otherwise return {lowerbound,upperbound-1}

 

Time Complexity : O(log n)

Space Complexity : O(1)

 

 public static int[] searchRange(int []arr, int x) {
        int lowerbound=LowerBound(arr, x);
        if(lowerbound==arr.length ||arr[lowerbound]!=x)return new int[]{-1,-1};
        else return new int[]{lowerbound,UpperBound(arr, x)-1};
    }
    public static int LowerBound(int arr[],int x){
        int start=0,end=arr.length-1, ans=arr.length;
        while(start<=end){
            int mid=(start+end)/2;
            if(arr[mid]>=x){
                ans=mid;
                end=mid-1;
            }
            else start=mid+1;
        }
        return ans;
    }
    public static int UpperBound(int arr[],int x){
        int start=0,end=arr.length-1,ans=arr.length;

        while(start<=end){
            int mid=(start+end)/2;
            if(arr[mid]>x){
                ans=mid;
                end=mid-1;
            }
            else start=mid+1;
        }
        return ans;
    }

java

datastructures

algorithms

57 views
0 replies
0 upvotes
profile
Ramu Prajapati

Interview problems

C++||Faster Than 91%||Binary Search

int firstOcc(vector<int> &arr, int n, int key) {

  int s = 0;

  int e = n - 1;

  int mid = s + (e - s) / 2;

  int ans = -1;

  while (s <= e){

      if(arr[mid] == key){

          ans = mid;

          e = mid-1;

      }

      else if(key > arr[mid]){

          s = mid+1;

      }

      else if(key < arr[mid]){

          e = mid-1;

      }

      mid = s + (e - s)/2;

  }

  return ans;

 

} 

 

int lastOcc(vector<int> &arr, int n, int key) {

  int s = 0;

  int e = n - 1;

  int mid = s + (e - s) / 2;

  int ans = -1;

  while (s <= e){

      if(arr[mid] == key){

          ans = mid;

          s = mid+1;

      }

      else if(key > arr[mid]){

          s = mid+1;

      }

      else if(key < arr[mid]){

          e = mid-1;

      }

      mid = s + (e - s)/2;

  }

  return ans;

 

} 

 

 

vector<int> searchRange(vector<int> &arr, int x)

{

    // Write your code here.

    vector<int> p;

    int first = firstOcc(arr, arr.size(), x);

    int second = lastOcc(arr, arr.size(), x);

    p.push_back(first);

    p.push_back(second);

 

    return p;

}

117 views
0 replies
0 upvotes
profile
Somya Singh

Interview problems

Java Solution | Tc-2*logn | sc-O(1) 

import java.util.*;
public class Solution {
    public static int[] searchRange(int []arr, int x) {
        // Write your code here.
        int n = arr.length;
        int[] ans = new int[2];
        ans[0] = firstOccurence(arr, x);
        ans[1] = lastOccurence(arr,x);
        return ans;
    }
    public static int firstOccurence(int[] arr, int x){
        int start = 0, end = arr.length-1;
        int first = -1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(arr[mid] == x){
                first = mid;
                end = mid - 1;
            }
            else if(arr[mid] < x){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }
        return first;
    }
    public static int lastOccurence(int[] arr, int x){
        int start = 0, end = arr.length-1;
        int last = -1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(arr[mid] == x){
                last = mid;
                start = mid + 1;
            }
            else if(arr[mid] < x){
                start = mid + 1;
            }
            else{
                end = mid - 1;
            }
        }
        return last;
    }
}
19 views
0 replies
0 upvotes
profile
Vikesh Kumar

Interview problems

c++ || 0(n) and 0(logn)

  • 0(n)
vector<int> searchRange(vector<int> &arr, int x)
{
	// Write your code here.
	int first =-1,second=-1;
	for(int i=0; i<arr.size(); i++){
		if(arr[i] == x){
			if(first == -1) first =i;
			second=i;
		}
	}
	vector<int>v ={first,second};
	return v;
}
  • 0(logn)
int binarySearch(vector<int>& nums, int target, bool isSearchingLeft) {
        int left = 0;
        int right = nums.size() - 1;
        int idx = -1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                idx = mid;
                if (isSearchingLeft) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        
        return idx;
}
vector<int> searchRange(vector<int> &arr, int x)
{
	// Write your code here.
	vector<int> result = {-1, -1};
    int left = binarySearch(arr, x, true);
    int right = binarySearch(arr, x, false);
    result[0] = left;
    result[1] = right;
    return result;
}
81 views
0 replies
0 upvotes
profile
Govind Dubey

Interview problems

C++||ALL TEST CLEAR|| TIME COMPLEXITY O( log N) || BINARY SEARCH METHOD

// searching first element or the leftmost element

 

  • int firstocc(vector<int>& arr, int x) {    int start = 0;    int end = arr.size() - 1;    int ans = -1;    while (start <= end) {        int mid = start + (end - start) / 2;        if (arr[mid] == x) {            ans = mid;            end = mid - 1;        } else if (x > arr[mid]) {            start = mid + 1;        } else {            end = mid - 1;        }    }    return ans; }

 

// searching last or rightmost element

 

  • int lastocc(vector<int>& arr, int x) {    int start = 0;    int end = arr.size() - 1;    int ans = -1;    while (start <= end) {        int mid = start + (end - start) / 2;        if (arr[mid] == x) {            ans = mid;            start = mid + 1;        } else if (x > arr[mid]) {            start = mid + 1;        } else {            end = mid - 1;        }    }    return ans; }

 

//making function call  and storing the value 

 

 

  • vector<int> searchRange(vector<int>& arr, int x) {    vector<int> p;    int first = firstocc(arr, x);    int second = lastocc(arr, x);    p.push_back(first);    p.push_back(second);    return p; }  
42 views
0 replies
0 upvotes
profile
Khushi Punani

Interview problems

JAVA Solution || Find First and Last Position of Element in Sorted Array 

import java.util.Arrays;
import java.util.Collections;

public class Solution {
    public static int[] searchRange(int []arr, int x) {
        // Write your code here.
        
        int []ans = new int[2];
        for(int i =0; i<arr.length ; i++){
            if(arr[i]==x){
                ans[0]=i;
                break;
            }else{
                ans[0]=-1;
            }
        }
        
        for(int i =arr.length-1; i>0 ; i--){
            if(arr[i]==x){
                ans[1]=i;
                break;
            }else{
                ans[1]=-1;
            }
        }
        return ans;

    }
}
20 views
0 replies
0 upvotes
profile
Sachin

Interview problems

Beginner Friendly Solution 🚀

#include<bits/stdc++.h>

vector<int> searchRange(vector<int> &arr, int x)

{

// Write your code here.

int n=arr.size();

vector<int> ans;

for(int i=0;i<n;i++)

{

if(arr[i]==x)

{

ans.push_back(i);

break;

}

}

for(int i=n-1;i!=-1;i--)

{

if(arr[i]==x)

{

ans.push_back(i);

break;

}

}

if(ans.size()==0)

{

return {-1,-1,};

}

return ans;

 

}

 

111 views
0 replies
0 upvotes
1
2
3
4
Full screen
Console