Pankaj Tanwar
Published on

Find First and Last Position of Element in Sorted Array.

––– views

Problem of the day - Find First and Last Position of Element in Sorted Array

Tag - Medium

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]

Honestly, this problem is worth the medium tag.

So, basically, from a sorted array, we need to find the starting and end index of given target element. (Constraints - O(log n) runtime.)

Ahm, how can I miss that. binary search is my best friend incase of sorted array result.

So, my thought was to find the starting and ending index of the target element in given array.

I must say,it was the worst decision. I struggled with it for around 1 hour. For each submission, leet code seemed unhappy as rejected the submission due to all test cases not passing.

I am not gonna lie, I took help of the discussion tab and modified my solution a bit.

Code Solution

class Solution {
public:
	// find the lowest index
    int searchTheLowest(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size();


        int mid;


        while(low < high) {
            mid = (low + high)/2;
            if(nums[mid] >= target) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }


    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size() == 0) return {-1,-1};


        int start = searchTheLowest(nums, target);
        int end = searchTheLowest(nums, target+1) - 1; // search for next big


        if(start >= 0 && end >= 0 && start < nums.size() && end < nums.size() && nums[start] == target && nums[end] == target && start <= end) {
            return {start, end};
        }
        return {-1,-1};
    }
};

Yeah ok ok, I can see what you have been feeling.

Anyways, It got solved in O(log n) time complexity.

If you feel, I am missing on something, feel free to reach out to me

I welcome your suggestions to improve it further!

Thanks for being part of my daily-code-workout journey. As always, if you have any thoughts about anything shared above, don't hesitate to reach out.

You might like previous editions of my coding diary

Tweet this article