Leetcode 81 Solution

Leetcode Question Link

https://leetcode.com/problems/search-in-rotated-sorted-array-ii

Thinking Process

Very similar question to problem 33. Very interesting question. Highly suggest that you read this and problem 33 before working on this one.

There are three key observations which drives the solution.

Observation 1

We cannot use the answer for problem 33.

I’ll use an example to explain. If we have an array [5, 5, 6, 1, 2, 5], and our target is 3, then the condition function will map this array to [1, 1, 1, 1, 1, 1], and the index of the first 1 in this array does not match the first index of the first element that is greater than or equal to 3.

Observation 2

We can use answer for problem 33 if the first element of the given array is not the same as the last one.

For example, if the given array is [5, 5, 6, 1, 2, 4], no matter what the target is, the condition function will map this array into a 0-1 array where the index of the first 1 matches the index of the first element that is greater than or equal to target in the given array. Why?

• If target is within the range of the right part, the left part is going to be mapped to 0 anyway. So this is just like finding first element greater than or equal to target in a sorted array.
• If target is within the range of the left part, the right part is going to be mapped to 1 anyway. This is still just like finding first element greater than or equal to target in a sorted array.

Observation 3

We can’t solve this problem in O(N) where N is the size of the array.

Think about an array which is full of 0 except for one element. That can be an rotated sorted array from this question. If you don’t look at all of the elements, you just don’t know if there is a 1 hiding in it.

The Final Algorithm

Based on the above three observations, we can design an algorithm like this:

• Let’s just first walk the array from the beginning until the element is not the same as the last one in the given array.
• Apply solution to problem 33.

Worst case time complexity is still O(N), but in most cases, it should be O(lg N).

Time & Space Complexity

Assuming N is the size of the array:

• Time complexity: O(N)
• Space complexity: O(1)

Solution

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return false

        l = 0
        r = len(nums) - 1

        while l < r and nums[l] == nums[r]:
            l += 1

        while l < r:
            m = (l + r) // 2
            if target > nums[-1] and (nums[m] >= target or nums[m] <= nums[-1]) or target <= nums[-1] and (target <= nums[m] <= nums[-1]):
                r = m
            else:
                l = m + 1

        return nums[l] == target