online advertising

Thursday, March 17, 2016

LeetCode OJ - Search for a Range

Problem: 

Please find the problem here.

Analysis:

Starting from this post, I will try to add an analysis section to the solution. This gives the solution a little more context, in particular, how did I come up with the solution.

The trivial approach for this solution is to linear search for the first occurrence of target and the last occurrence of target, this will be $ O(n) $.

Can we do better? After all the array is sorted. Let's search for the target value using binary search. We can do that in $ O(\log n) $ time. After doing so, we can scan from the middle to find the beginning and the end of the sequence of the target value, that can give us the search range.

But wait, this approach is actually no better than $ O(n) $ because in the worst case, the whole array is the same number and in the latter scan stage we will just scan the whole array again.

Solution:

The problem with the approach above has to do with duplicates and scan. But we know exactly what we are searching for, the beginning and end of the sequence of target values. So instead of searching for a value, searching for a gap that meet the condition of being beginning and end. Conceptually, the elements in the 'array' that we are searching are the gaps. Now those gaps are still ordered, and therefore we can still do binary search, and since we are finding the result we wanted right away, the performance is guaranteed to be  $ O(\log n) $.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/search-for-a-range/

#include "LEET_SEARCH_FOR_A_RANGE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SEARCH_FOR_A_RANGE
{
    class Solution
    {
    public:
        vector<int> searchRange(vector<int>& nums, int target)
        {
            int size = nums.size();

            // A binary search on the gaps in the array, an index of 0 means the gap between [-1] = -infinity and [0]
            int begin = 0;
            int end = size + 1;

            int range_start = -1;
            int range_end = -1;
            while (begin < end)
            {
                int mid = (begin + end) / 2;
                bool prevLessThanTarget = (mid == 0) ? true : nums[mid - 1] < target;
                bool nextHitTargetOrAbove = (mid == size) ? true : nums[mid] >= target;

                if (prevLessThanTarget && nextHitTargetOrAbove)
                {
                    range_start = mid;
                    break;
                }
                else if (!prevLessThanTarget)
                {
                    end = mid;
                }
                else 
                {
                    begin = mid;
                }
            }
            if (nums[range_start] == target)
            {
                begin = 0;
                end = size + 1;
                while (begin < end)
                {
                    int mid = (begin + end) / 2;
                    bool prevHitTargetOrBelow = (mid == 0) ? true : nums[mid - 1] <= target;
                    bool nextLargerThanTarget = (mid == size) ? true : nums[mid] > target;

                    if (prevHitTargetOrBelow && nextLargerThanTarget)
                    {                       
                        range_end = mid - 1;
                        break;
                    }
                    else if (!nextLargerThanTarget)
                    {
                        begin = mid;
                    }
                    else
                    {
                        end = mid;
                    }
                }
            }
            else
            {
                range_start = -1;
            }


            vector<int> result;
            result.push_back(range_start);
            result.push_back(range_end);
            return result;
        }
    };
};

using namespace _LEET_SEARCH_FOR_A_RANGE;

int LEET_SEARCH_FOR_A_RANGE()
{
    int case1_array[] = { 5, 7, 7, 8, 8, 10 };
    vector<int> case1(case1_array, case1_array + _countof(case1_array));
    Solution s;
    vector<int> result = s.searchRange(case1, 8);
    cout << result[0] << ", " << result[1] << endl;
    return 0;
}

No comments :

Post a Comment