Search in Rotated Sorted Array II - Practice Coding Problems

Search in Rotated Sorted Array II - Problem

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.

You must decrease the overall operation steps as much as possible.

Input & Output

Example 1 — Target Found

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

› Output: true

💡 Note: Target 0 exists in the rotated sorted array at indices 3 and 4

Example 2 — Target Not Found

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

› Output: false

💡 Note: Target 3 does not exist anywhere in the rotated sorted array

Example 3 — Single Element

$ Input: nums = [1], target = 1

› Output: true

💡 Note: Single element array contains the target

Constraints

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
nums is guaranteed to be rotated at some pivot
-10⁴ ≤ target ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Rotated sorted array [2,5,6,0,0,1,2] and target 0

Process

Use binary search with duplicate handling

Output

Return true if target found, false otherwise

Key Takeaway

🎯 Key Insight: Even with rotation and duplicates, at least one half remains sorted - focus binary search on the appropriate half

Asked in

M Microsoft 15 A Amazon 12 G Google 10 F Facebook 8

The key insight is that even in a rotated sorted array with duplicates, at least one half is always properly sorted. The modified binary search approach handles duplicates by shrinking boundaries when we can't determine the sorted half. Best approach achieves O(log n) average time complexity. Time: O(log n) average, O(n) worst case, Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Linear Search	O(n)	O(1)	Check each element one by one until target is found
Modified Binary Search	O(log n)	O(1)	Use binary search with special handling for duplicates and rotation

Linear Search — Algorithm Steps

Step 1: Start from the first element
Step 2: Compare each element with target
Step 3: Return true if found, continue if not
Step 4: Return false if end is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin from first element

Compare

Check if current element equals target

Result

Return true when found or false at end

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == target) {
            return true;
        }
    }
    return false;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ') {
            nums[numsSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    int target;
    scanf("%d", &target);
    printf(solution(nums, numsSize, target) ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single loop through all n elements in worst case

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

125.0K Views

Medium Frequency

~25 min Avg. Time

3.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Linear Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler