algoadvance

Leetcode 81. Search in Rotated Sorted Array II

Problem Statement

Suppose an array sorted in non-decreasing order is rotated at some pivot unknown to you beforehand (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return true, otherwise return false.

This array may contain duplicates.

You must decrease the overall time complexity.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Constraints:

Clarifying Questions

  1. Are there any edge cases that the solution must handle?
    • Yes, cases with duplicates, very small arrays, and target at the pivot or end positions.
  2. What is the expected time complexity for an optimal solution?
    • Expected is O(log n) in average additional potential linear time due to duplicates.

Strategy

  1. Binary Search Adjustment for Rotated Array with Duplicates:
    • Normally, binary search has O(log n) complexity, but the presence of duplicates may degrade it to O(n) in the worst scenario.
  2. Modified Binary Search Steps:
    • Calculate mid.
    • Check if nums[mid] == target, return true.
    • To handle duplicates during binary search, when elements at start, mid, and end are equal, shrink the search range by moving the start and end pointers inward.
    • Identify the sorted half:
      • If nums[start] to nums[mid] is sorted, determine if the target is in this range.
      • If nums[mid] to nums[end] is sorted, determine if the target is in this range.
    • Adjust the pointers based on this strategy to continue the search.
  3. Edge Cases:
    • Single element arrays.
    • Arrays where the target is at the pivot.
    • All elements being duplicates except one.

Code

#include <vector>
using namespace std;

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int start = 0, end = nums.size() - 1;
        
        while (start <= end) {
            int mid = start + (end - start) / 2;
            
            if (nums[mid] == target) {
                return true;
            }
            
            // Handle duplicates by narrowing the range.
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            }
            // Left part is sorted.
            else if (nums[start] <= nums[mid]) {
                // Target is in the sorted left part.
                if (nums[start] <= target && target < nums[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            // Right part is sorted.
            else {
                // Target is in the sorted right part.
                if (nums[mid] < target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        
        return false;
    }
};

Time Complexity

The worst-case time complexity of this approach is O(n) because in the case of many duplicates, we might end up checking every element. However, in the average case, it should perform better, typically closer to O(log n) when there are fewer duplicates.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI