Leetcode 81. Search in Rotated Sorted Array II

Problem Explanation

In this problem, you are given a "rotated" array. This means, an array is initially sorted in ascending order, then some elements from its beginning are taken out and appended at the end which rotates the array. This rotation could occur at any unknown pivot in the array. You are also given a target number, and you have to determine if the target number is present in the array or not. If it is, you return 'True', and if it isn't, you return 'False'.

This might sound a little bit complex, but it isn't. Consider an array: 2,5,6,0,0,1,2. This is the result of rotating the array: 0,0,1,2,2,5,6. As you can see, the elements have just shifted.

The question is designed as a follow-up problem to Search in a Rotated Sorted Array. Here, the difference is that the array may contain duplicate elements.

A key point to consider is that the presence of duplicates can indeed affect the run-time complexity. With duplicates, in the worst case, we might need to examine each element of the array once, therefore having a run-time complexity of O(n).

Example

Consider this rotated array: [2,5,6,0,0,1,2] and our target is 0. As we traverse through the array, we see that 0 is present. Hence, we return True. But if our target is 3, traversing gets us nowhere since 3 is not present in the array. So, we return False.

Solution Approach

Start at the two ends of the array, i.e., at positions l=0 and r=n-1. While l <= r, keep getting the middle element. If the middle element matches the target value, return True.

If the left, middle, and right element all have the same value, we can't really decide which half to go to, so we increment left and decrement right.

If the left half is sorted (i.e., the leftmost element is smaller than or equal to the middle element), we check whether the target lies in this range. If yes, the target must lie on the left half, thus updating right to m - 1. Otherwise, it must lie on the right half, thus updating left to m + 1.

If the right half is sorted (i.e., the middle element is smaller than the rightmost element), we check whether the target lies in this range. If so, update left to m + 1. Otherwise, update right to m - 1.

If we come out of the loop, that means the target value is not present in the array. Return False.

Here are the solutions in various languages. Remember to replace 'Solution' with the class name used in your code.

Python Solution

1
2python
3class Solution:
4    def search(self, nums: List[int], target: int) -> bool:
5        l, r = 0, len(nums) - 1
6        while l <= r:
7            m = (l + r) // 2
8            if nums[m] == target:
9                return True
10            while l < m and nums[l] == nums[m]:  # tricky part
11                l += 1
12            if nums[l] <= nums[m]:
13                if nums[l] <= target < nums[m]:
14                    r = m - 1
15                else:
16                    l = m + 1
17            else:
18                if nums[m] < target <= nums[r]:
19                    l = m + 1
20                else:
21                    r = m - 1
22        return False

Java Solution

1
2java
3
4public class Solution {
5    public boolean search(int[] nums, int target) {
6        int l = 0, r = nums.length - 1;
7        while (l <= r) {
8            int m = (l + r) / 2;
9            if (nums[m] == target) return true;
10            if (nums[l] == nums[m] && nums[r] == nums[m]) { l++; r--; }
11            else if (nums[l] <= nums[m]) {
12                if (target >= nums[l] && target < nums[m]) r = m - 1;
13                else l = m + 1;
14            } else {
15                if (target > nums[m] && target <= nums[r]) l = m + 1;
16                else r = m - 1;
17            }
18        }
19        return false;
20    }
21}
22

JavaScript Solution

1
2JavaScript
3var search = function(nums, target) {
4    let low = 0, high = nums.length - 1;
5    
6    while (low <= high) {
7        let mid = Math.floor((low + high) / 2);
8        
9        if (nums[mid] === target) return true;
10        
11        while (nums[low] === nums[mid] && low !== mid) low++;
12        
13        if (nums[low] <= nums[mid]) {
14            if (nums[low] <= target && target < nums[mid]) high = mid - 1;
15            else low = mid + 1;
16        } else {
17            if (nums[mid] < target && target <= nums[high]) low = mid + 1;
18            else high = mid - 1;
19        }
20    }
21    
22    return false;
23};
24

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool search(vector<int>& nums, int target) {
6        int l = 0;
7        int r = nums.size() - 1;
8
9        while (l <= r) {
10            int m = (l + r) / 2;
11            if (nums[m] == target)
12                return true;
13            if (nums[l] == nums[m] && nums[m] == nums[r]) {
14                ++l;
15                --r;
16            } else if (nums[l] <= nums[m]) {
17                if (nums[l] <= target && target < nums[m])
18                    r = m - 1;
19                else
20                    l = m + 1;
21            } else {
22                if (nums[m] < target && target <= nums[r])
23                    l = m + 1;
24                else
25                    r = m - 1;
26            }
27        }
28
29        return false;
30    }
31};

C# Solution

1
2Csharp
3
4public class Solution {
5    public bool Search(int[] nums, int target) {
6        int l = 0, r = nums.Length - 1;
7        while (l <= r)
8        {
9            int mid = l + (r-1)/2;
10            if (nums[mid] == target) return true;
11   
12            // the only difference from the first one, trickly handle nums[start] == nums[mid]
13            if (nums[l] == nums[mid] && nums[r] == nums[mid]) {++l; --r;}
14   
15            else if (nums[l] <= nums[mid])
16            {
17                if (nums[l] <= target && target < nums[mid]) r = mid - 1;
18                else l = mid + 1;
19            }
20            else
21            {
22                if (nums[mid] < target && target <= nums[r]) l = mid + 1;
23                else r = mid - 1;
24            }
25        }
26        return false;
27    }
28}
29

Swift Solution

1
2swift
3class Solution {
4    func search(_ nums: [Int], _ target: Int) -> Bool {
5        var left = 0
6        var right = nums.count - 1
7
8        while left <= right {
9            let mid = (left + right) / 2
10            if nums[mid] == target {
11                return true
12            }
13            
14            if nums[left] == nums[mid] && nums[mid] == nums[right] {
15                left += 1
16                right -= 1
17            } else if nums[left] <= nums[mid] {
18                if target >= nums[left] && target < nums[mid] {
19                    right = mid - 1
20                } else {
21                    left = mid + 1
22                }
23            } else {
24                if target > nums[mid] && target <= nums[right] {
25                    left = mid + 1
26                } else {
27                    right = mid - 1
28                }
29            }
30        }
31        
32        return false
33    }
34}

First, we create a class Solution with a function search that takes in the array nums and the target integer value.

In the method, we declare two pointers left and right, representing the left and right ends of the array. While left is less than or equal to right, we get the middle element of the array. If this element matches the target, we return True.

Next, we handle the tricky case where left, middle, and right elements are all the same. In this case, we can't determine which half to explore, so we increment left and decrement right.

Then, we check if the left half is sorted (i.e., the leftmost element is less than or equal to the middle one). If the target lies within this range, we know it's in the left half, so we update right to mid - 1. If not, it must be in the right half, so we update left to mid + 1.

If the right half is sorted (i.e., the middle element is less than the rightmost one), we check if the target is in this range. If so, we update left to mid + 1, otherwise, we update right to mid - 1.

Finally, if the target was not found in this process, we return False. This completes the method and allows us to determine if the target is present in the array or not.

This solution is efficient with a time complexity of O(log n) in the best case scenario when there are no duplicates and O(n) in the worst case when duplicates are present.