Search in rotated sorted array-II

Intuition

The simplest way to solve this problem is by using a linear search to check each element of the array one by one.

Approach

Traverse the array from start to end & compare each element with the target value.
If an element matches the target, return True. If no match is found by the end of the array, return False.

Dry Run: Please refer to the video for the dry-run.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to search for the target element in a rotated sorted array
    bool searchInARotatedSortedArrayII(vector<int>& arr, int target) {
        int n = arr.size(); 
        
        // Traverse the array to find the target element
        for (int i = 0; i < n; i++) {
            // If the current element matches the target, return true
            if (arr[i] == target) return true;
        }
        // If the target is not found, return false
        return false;
    }
};

int main() {
    vector<int> arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6}; 
    int target = 3; 

    // Create an instance of the Solution class
    Solution sol;

    // Function call to search for the target element
    bool result = sol.searchInARotatedSortedArrayII(arr, target);

    if (!result)
        cout << "Target is not present.\n";
    else
        cout << "Target is present in the array.\n";

    return 0;
}
import java.util.*;

class Solution {
    // Function to search for the target element in a rotated sorted array
    public boolean searchInARotatedSortedArrayII(int[] arr, int target) {
        int n = arr.length; 
        
        // Traverse the array to find the target element
        for (int i = 0; i < n; i++) {
            // If the current element matches the target, return true
            if (arr[i] == target) return true;
        }
        // If the target is not found, return false
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6}; 
        int target = 3; 

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Function call to search for the target element
        boolean result = sol.searchInARotatedSortedArrayII(arr, target);

        if (!result)
            System.out.println("Target is not present.");
        else
            System.out.println("Target is present in the array.");
    }
}
class Solution:
    # Function to search for the target element in a rotated sorted array
    def searchInARotatedSortedArrayII(self, arr, target):
        n = len(arr) 
        
        # Traverse the array to find the target element
        for i in range(n):
            # If the current element matches the target, return true
            if arr[i] == target:
                return True
        # If the target is not found, return false
        return False

if __name__ == "__main__":
    arr = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6] 
    target = 3 

    # Create an instance of the Solution class
    sol = Solution()

    # Function call to search for the target element
    result = sol.searchInARotatedSortedArrayII(arr, target)

    if not result:
        print("Target is not present.")
    else:
        print("Target is present in the array.")
class Solution {
    // Function to search for the target element in a rotated sorted array
    searchInARotatedSortedArrayII(arr, target) {
        let n = arr.length; 
        
        // Traverse the array to find the target element
        for (let i = 0; i < n; i++) {
            // If the current element matches the target, return true
            if (arr[i] === target) return true;
        }
        // If the target is not found, return false
        return false;
    }
}

let arr = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6];
let target = 3;

// Create an instance of the Solution class
let sol = new Solution();

// Function call to search for the target element
let result = sol.searchInARotatedSortedArrayII(arr, target);

if (!result)
    console.log("Target is not present.");
else
    console.log("Target is present in the array.");

Complexity Analysis:

Time Complexity:O(N), for iterating through N elements, where N is the size of the given array.

Space Complexity:O(1), not using any extra space to solve this problem.

Intuition

For looking for a target in a rotated sorted array that has duplicates, use binary search for most optimal results. The tricky part is handling duplicates, especially when they are at both ends of the array. Start by finding the sorted half of the array and checking if the target is there. If duplicates make it hard to find the sorted half, just skip them by moving our pointers. This way, keep narrowing down the search space efficiently.

Approach

Initialize two pointers: low at the start and high at the end of the array.
Inside a loop, calculate the midpoint (mid). If arr[mid] is the target, return True.
Check if arr[low], arr[mid], and arr[high] are equal. If so, increment low and decrement high to skip duplicates.
Identify the sorted half: If arr[low] <= arr[mid], the left half is sorted. Otherwise, the right half is sorted.
Adjust the pointers based on the target's location: If the left half is sorted and the target is within this range, adjust high to mid - 1. Otherwise, adjust low to mid + 1. If the right half is sorted and the target is within this range, adjust low to mid + 1. Otherwise, adjust high to mid - 1.
Continue this process until low exceeds high. If no target is found, return False.

Dry Run:

Please refer to the video for complete dry-run.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /*  Function to search for the target element 
        in a rotated sorted array with duplicates   */
    bool searchInARotatedSortedArrayII(vector<int>& arr, int target) {
        int n = arr.size();
        int low = 0, high = n - 1;
        
        // Applying binary search algorithm 
        while (low <= high) {
            int mid = (low + high) / 2;

            // Check if mid points to the target
            if (arr[mid] == target) return true;

            // Handle duplicates: if arr[low], arr[mid], and arr[high] are equal
            if (arr[low] == arr[mid] && arr[mid] == arr[high]) {
                low = low + 1;
                high = high - 1;
                continue;
            }

            // Check if the left part is sorted
            if (arr[low] <= arr[mid]) {
                /*  Eliminate the right part if target
                    exists in the left sorted part */
                if (arr[low] <= target && target <= arr[mid]) {
                    high = mid - 1;
                } 
                // Otherwise eliminate the left part
                else {
                    low = mid + 1;
                }
            } else {
                /*  If the right part is sorted and
                    target exists in the right sorted
                    part, eliminate the left part   */
                if (arr[mid] <= target && target <= arr[high]) {
                    low = mid + 1;
                } 
                // Otherwise eliminate the right part
                else {
                    high = mid - 1;
                }
            }
        }
        // If target is not found
        return false;
    }
};

int main() {
    vector<int> arr = {7, 8, 1, 2, 3, 3, 3, 4, 5, 6};
    int target = 3; 

    // Create an instance of the Solution class
    Solution sol;

    // Function call to search for the target element
    bool result = sol.searchInARotatedSortedArrayII(arr, target);

    if (!result)
        cout << "Target is not present.\n";
    else
        cout << "Target is present in the array.\n";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to search for the target element 
    in a rotated sorted array with duplicates */
    public boolean searchInARotatedSortedArrayII(ArrayList<Integer> arr, int target) {
        int n = arr.size();
        int low = 0, high = n - 1;
        
        // Applying binary search algorithm 
        while (low <= high) {
            int mid = (low + high) / 2;

            // Check if mid points to the target
            if (arr.get(mid) == target) return true;

            // Handle duplicates: if arr[low], arr[mid], and arr[high] are equal
            if (arr.get(low).equals(arr.get(mid)) && arr.get(mid).equals(arr.get(high))) {
                low = low + 1;
                high = high - 1;
                continue;
            }

            // Check if the left part is sorted
            if (arr.get(low) <= arr.get(mid)) {
                /*  Eliminate the right part if target
                    exists in the left sorted part */
                if (arr.get(low) <= target && target <= arr.get(mid)) {
                    high = mid - 1;
                } 
                // Otherwise eliminate the left part
                else {
                    low = mid + 1;
                }
            } else {
                /*  If the right part is sorted and
                    target exists in the right sorted
                    part, eliminate the left part   */
                if (arr.get(mid) <= target && target <= arr.get(high)) {
                    low = mid + 1;
                } 
                // Otherwise eliminate the right part
                else {
                    high = mid - 1;
                }
            }
        }
        // If target is not found
        return false;
    }
}

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>();
        arr.add(7); arr.add(8); arr.add(1); arr.add(2); arr.add(3);
        arr.add(3); arr.add(3); arr.add(4); arr.add(5); arr.add(6);

        int target = 3; 

        // Create an instance of the Solution class
        Solution sol = new Solution();

        // Function call to search for the target element
        boolean result = sol.searchInARotatedSortedArrayII(arr, target);

        if (!result)
            System.out.println("Target is not present.");
        else
            System.out.println("Target is present in the array.");
    }
}
class Solution:
    # Function to search for the target element
    # in a rotated sorted array with duplicates
    def searchInARotatedSortedArrayII(self, arr, target):
        n = len(arr)
        low, high = 0, n - 1
        
        # Applying binary search algorithm 
        while low <= high:
            mid = (low + high) // 2

            # Check if mid points to the target
            if arr[mid] == target:
                return True

            # Handle duplicates: if arr[low], arr[mid], and arr[high] are equal
            if arr[low] == arr[mid] == arr[high]:
                low += 1
                high -= 1
                continue

            # Check if the left part is sorted
            if arr[low] <= arr[mid]:
                # Eliminate the right part if target exists in the left sorted part
                if arr[low] <= target <= arr[mid]:
                    high = mid - 1
                # Otherwise eliminate the left part
                else:
                    low = mid + 1
            else:
                # If the right part is sorted and target exists in the right sorted part, eliminate the left part
                if arr[mid] <= target <= arr[high]:
                    low = mid + 1
                # Otherwise eliminate the right part
                else:
                    high = mid - 1
        
        # If target is not found
        return False

if __name__ == "__main__":
    arr = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6]
    target = 3 

    # Create an instance of the Solution class
    sol = Solution()

    # Function call to search for the target element
    result = sol.searchInARotatedSortedArrayII(arr, target)

    if not result:
        print("Target is not present.")
    else:
        print("Target is present in the array.")
class Solution {
    /* Function to search for the target element 
       in a rotated sorted array with duplicates */
    searchInARotatedSortedArrayII(arr, target) {
        let n = arr.length;
        let low = 0, high = n - 1;
        
        // Applying binary search algorithm 
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);

            // Check if mid points to the target
            if (arr[mid] === target) return true;

            /* Handle duplicates: if arr[low], arr[mid], 
               and arr[high] are equal */
            if (arr[low] === arr[mid] && arr[mid] === arr[high]) {
                low = low + 1;
                high = high - 1;
                continue;
            }

            // Check if the left part is sorted
            if (arr[low] <= arr[mid]) {
                /* Eliminate the right part if target
                   exists in the left sorted part */
                if (arr[low] <= target && target <= arr[mid]) {
                    high = mid - 1;
                } 
                // Otherwise eliminate the left part
                else {
                    low = mid + 1;
                }
            } else {
                /* If the right part is sorted and
                   target exists in the right sorted
                   part, eliminate the left part */
                if (arr[mid] <= target && target <= arr[high]) {
                    low = mid + 1;
                } 
                // Otherwise eliminate the right part
                else {
                    high = mid - 1;
                }
            }
        }
        // If target is not found
        return false;
    }
}

let arr = [7, 8, 1, 2, 3, 3, 3, 4, 5, 6];
let target = 3; 

// Create an instance of the Solution class
let sol = new Solution();

// Function call to search for the target element
let result = sol.searchInARotatedSortedArrayII(arr, target);

if (!result)
    console.log("Target is not present.");
else
    console.log("Target is present in the array.");

Complexity Analysis:

Time Complexity:O(logN) for the best and average cases. As in the best and average scenarios, the binary search algorithm is primarily used and hence the time complexity is O(logN).
However, in the worst-case scenario, it'll be O(N/2) where all array elements are the same but not the target (e.g., given array = {3, 3, 3, 3, 3, 3, 3}), we continue to reduce the search space by adjusting the low and high pointers until they intersect, which will end up taking O(N/2) time complexity.

Space Complexity:O(1), as we are not using any extra space to solve this problem.

Problem List

Search in rotated sorted array-II

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Complexity Analysis:

Intuition

Approach

Dry Run:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code