DEV Community

Cover image for 34. Find First and Last Position of Element in Sorted Array
Harsh Rajpal
Harsh Rajpal

Posted on

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

Problem Statement:

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

Solution:
Algorithm:

  1. Find the target value in the array.
  2. If the target value is found,then find the first and last position of the target value.
  3. If the target value is not found,return [-1,-1].
  4. Return the result.

Code:

public class Solution {
    public int[] searchRange(int[] nums,int target){

        int[] result = new int[2];
        result[0] = -1;
        result[1] = -1;
        int left = 0;
        int right = nums.length - 1;
        int mid = 0;
        while(left <= right){
            mid = (left + right) / 2;
            if(nums[mid] == target){
                result[0] = mid;
                result[1] = mid;
                break;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }
            else{
                right = mid - 1;
            }
        }
        if(result[0] == -1){
            return result;
        }
        int i = mid - 1;
        while(i >= 0 && nums[i] == target){
            result[0] = i;
            i--;
        }
        i = mid + 1;
        while(i < nums.length && nums[i] == target){
            result[1] = i;
            i++;
        }
        return result;
    }

}
Enter fullscreen mode Exit fullscreen mode

Time Complexity:
O(log N)

Space Complexity:
O(1)

Image of Datadog

The Future of AI, LLMs, and Observability on Google Cloud

Datadog sat down with Google’s Director of AI to discuss the current and future states of AI, ML, and LLMs on Google Cloud. Discover 7 key insights for technical leaders, covering everything from upskilling teams to observability best practices

Learn More

Top comments (0)

Hostinger image

Get n8n VPS hosting 3x cheaper than a cloud solution

Get fast, easy, secure n8n VPS hosting from $4.99/mo at Hostinger. Automate any workflow using a pre-installed n8n application and no-code customization.

Start now

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay