C++ solution using sets


  • 0
    S

    The approach of this solution is to make a set of indices of 'nums' array at which we find our target value. After we have made a list of all the indices which contain target value, we can obtain the range by extracting the min and max index.

    The algorithm uses binary search algorithm to search for the target values and hence is O(logn).

    class Solution {
    public:
        void binarySearch(vector<int> &nums, int n, set<int> &indices, int start, int end){
            if(start > end){
                return;
            }
            
            if(nums[end] < n){
                return;
            }
            if(nums[start] > n){
                return;
            }
            
            int mid = (start + end) / 2;
            if(nums[mid] == n){
                indices.insert(mid);
            }
            
            binarySearch(nums, n, indices, mid + 1, end);
            binarySearch(nums, n, indices, start, mid - 1);
        }
        vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> answer(2, -1);
            if(nums.size() <= 0){
                return answer;
            }
            
            set<int> indices;
            binarySearch(nums, target, indices, 0, nums.size() - 1);
            
            if(indices.size() >= 1){
                answer[0] = *(indices.begin());
                answer[1] = *(indices.rbegin());
            }
    
            return answer;
        }
    };
    

Log in to reply
 

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