algoadvance

Leetcode 81. Search in Rotated Sorted Array II

Problem Statement:

You are given an integer array nums sorted in ascending order (with distinct values) that has been rotated at an unknown pivot index. You are also given an integer target. Suppose the array initially looked like this: [0,1,2,4,5,6,7] and it was rotated at an unknown pivot index [4,5,6,7,0,1,2].

Write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Clarifying Questions:

1. Can the array contain duplicates? (Note: Typically, Leetcode problem 81 allows duplicates to be present in the array)
   • Yes.
2. What is the expected time complexity for this problem?
   • Ideally, O(log n), but due to the presence of duplicates, in some cases, the time complexity could degrade to O(n).

Strategy:

1. Algorithm Choice: Binary Search.
2. Handling Duplicates: Because duplicates are present, the standard rotated binary search (which relies on distinct values to determine if pivot is in left or right half) needs modification.
3. Steps:
   • Initialize two pointers left and right at the start and end of the array.
   • While left <= right, calculate mid.
   • Check if nums[mid] is the target.
   • If not, compare elements to determine which half is sorted.
   • If nums[left] is equal to nums[mid], move the left pointer right by one (left++) to skip the duplicate.
   • If nums[mid] is equal to nums[right], move the right pointer left by one (right--) to skip the duplicate.
   • Based on sorted half, decide whether to move left or right to narrow the search.

Code:

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        int left = 0, right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // the only change is here: handling duplicates
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                ++left;
                --right;
            } else if (nums[left] <= nums[mid]) { // left part is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // right part is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }

        return -1; // target not found
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;
        System.out.println(sol.search(nums, target)); // Output: 4
    }
}

Time Complexity:

• Best Case: O(log n) when the duplicates are minimal or do not affect the decision on the pivot and sorted halves.
• Worst Case: O(n) if duplicates cause multiple shifts of either left or right, effectively searching the array linearly.

Space Complexity:

• O(1) since we are using a constant amount of extra space.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?