Clean C++ Solution 6ms accepted Beats 99.31%


  • 0
    C

    Explaination: First I made a helper function using binary search to help me find the first place where I can see the element. It may be in the middle of the range since it's (first+end)/2.

    Once I have that I can find the start and the end of the range. (Yes, it may be the beginning and end of the array, so just depends on the test cases) but overall I think it works, and is accepted. I will try posting some test cases where this may time out but I'm not sure how the time complexity is implemented or checked here, so not sure if that can be done.

    It beats about 99.31% of all submissions and passes in 6 ms.

    Here's the code:

    int findFirst(vector<int>& nums, int target, int start, int end) {
            if(start > end) return -1;
            if(start == end) return -1;
            
            int mid = (start+end)/2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target){
                start = mid+1;
            } else {
                end = mid;
            }
            return findFirst(nums, target, start, end);
    }
        
    vector<int> searchRange(vector<int>& nums, int target) {
            int first = findFirst(nums, target, 0, nums.size()); //Time: O(logn)
            int start = first, end = first;
            //cout << first << endl;
            while(first > 0 && start > 0 && nums.size() >= 2 && nums[start-1] == target) {
                start--;
            }
            while(first < nums.size()-1 && end < nums.size()-1 && nums[end+1] == target){
                end++;
            }
            vector<int> res{start,end};
            return res;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.