In this post, we are going to solve the 34. Find First and Last Position of Element in Sorted Array problem of Leetcode. This problem 34. Find First and Last Position of Element in Sorted Array is a Leetcode medium level problem. Let’s see the code, 34. Find First and Last Position of Element in Sorted Array – Leetcode Solution.

Problem

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1 :

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2 :

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3 :

Input: nums = [], target = 0
Output: [-1,-1]

Constraints

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Now, let’s see the code of 34. Find First and Last Position of Element in Sorted Array – Leetcode Solution.

Find First and Last Position of Element in Sorted Array – Leetcode Solution

34. Find First and Last Position of Element in Sorted Array – Solution in Java

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        int f = findFirstOccurance(nums,nums.length,target);
        int l = findLastOccurance(nums,nums.length,target);
        ans[0] = f;
        ans[1] = l;
        return ans;
    }
    
    int findFirstOccurance(int[] arr, int n, int x){
        int ans = -1;
        int s = 0;
        int end = n-1;
        while(s <= end){
            int mid = s - (s - end)/2;
            if(arr[mid] == x){ 
                ans = mid;
                end = mid-1;
                continue;
            }else if(x > arr[mid]){
                s = mid + 1;
            }
            else if(x < arr[mid])end = mid-1;
        }
        return ans;
    } 
    
    int findLastOccurance(int[] arr, int n, int x){
        int ans = -1;
        int s = 0;
        int end = n-1;
        while(s <= end){
            int mid = s - (s - end)/2;
            if(arr[mid] == x){ 
                ans = mid;
                s = mid + 1;
                continue;
            }else if(x < arr[mid]){
                end = mid-1;
            }
           else if(x > arr[mid]) s = mid + 1;
        }
        return ans;
    } 
}

34. Find First and Last Position of Element in Sorted Array – Solution in C++

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int s = 0;
        int f_ocr=-1,l_ocr=-1;
        int l = nums.size()-1;
        //first occurence --->
        while(s<=l){
            int mid = s + (l-s)/2;
            if(target==nums[mid])
            {
                f_ocr = mid;
                l = mid-1;
            }
            else if(target>nums[mid]){
                s = mid+1;
            }
            else l = mid-1;
        }
        s=0;l=nums.size()-1;
        //last occurance --->
        while(s<=l){
            int mid = s + (l-s)/2;
            if(target==nums[mid])
            {
                l_ocr = mid;
                s = mid+1;
            }
            else if(target<nums[mid]){
                l = mid-1;
            }
            else s = mid+1;
        }
       if(f_ocr==-1)return {-1,-1};
        else return {f_ocr,l_ocr};
    }
};

34. Find First and Last Position of Element in Sorted Array – Solution in Python

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        def search(x):
            lo, hi = 0, len(nums)           
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] < x:
                    lo = mid+1
                else:
                    hi = mid                    
            return lo
        
        lo = search(target)
        hi = search(target+1)-1
        
        if lo <= hi:
            return [lo, hi]
                
        return [-1, -1]

Note: This problem 34. Find First and Last Position of Element in Sorted Array is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.