Find Minimum in Rotated Sorted Array - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const LEFT = 'LEFT', LEFT_COLOR = 'orange';
const RIGHT = 'RIGHT', RIGHT_COLOR = 'blue';
const MIDDLE = 'MIDDLE', MIDDLE_COLOR = 'gray';
const MIN_COLOR = 'green';

function visMainFunction(inputNums) {
    initClassProperties();

    startBatch();
    const nums = VisArray.from(inputNums).options({'renderingStyle': RenderingStyle.BAR_CHART});
    let left = 0;
    let right = nums.length - 1;

    makeVisVariable(left).registerAsIndexPointer(nums, LEFT);
    makeVisVariable(right).registerAsIndexPointer(nums, RIGHT);
    endBatch();

    explanationAndColorPaletteNotifications();

    notification(`
        🔍 The array consists of <b>two sorted parts</b> due to rotation:<br/>
        A first increasing section starting with a number greater than all in the second,<br/>
        and a second increasing section that starts at the <b>minimum element</b>.<br/>
        If there is no rotation, the size of the <b>first half</b> is <b>0</b> (the array is fully increasing).
    `);

    while (left < right) {
        startPartialBatch();
        const mid = Math.floor((left + right) / 2);
        const midVisManager = nums.makeVisManagerForIndex(mid);
        midVisManager.addClass(MIDDLE);

        if (nums[mid] > nums[right]) {
            notification(`
                📌 <b>nums[mid]</b> = <b>${makeColoredSpan(nums[mid], MIDDLE_COLOR)}</b>,  
                <b>nums[right]</b> = <b>${makeColoredSpan(nums[right], RIGHT_COLOR)}</b>.<br/>
                Since <code>nums[mid] &gt; nums[right]</code> and <b>nums[right]</b> is the greatest element in the second half,<br/>
                <b>mid must be in the first half</b> (the larger part).<br/>
                The minimum will always be in the <b>second half</b>, so it must lie to the <b>right of mid</b>.<br/>
                👉 Move search to the right: <code>left = mid + 1</code> → left = ${makeColoredSpan(mid + 1, LEFT_COLOR)}.
            `);
            left = mid + 1;
        } else {
            notification(`
                📌 <b>nums[mid]</b> = <b>${makeColoredSpan(nums[mid], MIDDLE_COLOR)}</b>,  
                <b>nums[right]</b> = <b>${makeColoredSpan(nums[right], RIGHT_COLOR)}</b>.<br/>
                Since <code>nums[mid] ≤ nums[right]</code> and <b>nums[right]</b> belongs to the second half</b>,  
                and every element in the <b>first half</b> is greater than any element in the <b>second half</b>,  
                <b>mid must lie in the second half</b> (the smaller part).<br/>
                In this half, values are increasing and <b>nums[right]</b> is the maximum.<br/>
                The <b>minimum</b> is at the beginning of this half, so it must be either <b>mid itself</b> or somewhere to its left.<br/>
                👉 Move search to the left side of this half: <code>right = mid</code> → right = ${makeColoredSpan(mid, RIGHT_COLOR)}.
            `);
            right = mid;
        }

        midVisManager.removeClass(MIDDLE);
        endBatch();
    }

    startPartialBatch();
    nums.makeVisManagerForIndex(left).setProp('backgroundColor', MIN_COLOR);
    notification(`
        ✅ The <b>minimum number</b> is <b>${makeColoredSpan(nums[left], MIN_COLOR)}</b> at index <b>${left}</b>.<br/>
        At the end of the loop, <b>left and right are equal</b>, both pointing to the index of the <b>${makeColoredSpan("smallest element", MIN_COLOR)}</b> in the array.<br/>
        This element is the start of the second increasing section, and it is the minimum value in the array.
    `);
    endBatch();
    return nums[left]; // left is equal to right actually
}

function explanationAndColorPaletteNotifications() {
    // High-level explanation (from your API)
    explanationNotification();

    // Color palette guide
    notification(`
        🎨 <b>Color Palette Guide</b><br/><br/>
        • ${makeColoredSpan("Orange background", LEFT_COLOR)} → <b>Left index/element</b> (current <code>left</code> pointer)<br/>
        • ${makeColoredSpan("Blue background", RIGHT_COLOR)} → <b>Right index/element</b> (current <code>right</code> pointer)<br/>
        • ${makeColoredSpan("Gray background", MIDDLE_COLOR)} → <b>Mid index/element</b> during each comparison<br/>
        • ${makeColoredSpan("Green background", MIN_COLOR)} → <b>Minimum element</b> (final answer)
    `);
}

function initClassProperties() {
    setClassProperties(LEFT, {
        backgroundColor: LEFT_COLOR
    });

    setClassProperties(RIGHT, {
        backgroundColor: RIGHT_COLOR
    });

    setClassProperties(MIDDLE, {
        backgroundColor: MIDDLE_COLOR
    });
}

Approach

Goal

Given a rotated sorted array of unique integers, find the minimum element. The array is originally sorted in increasing order and then rotated.

Key Idea (Intuition)

The array can be divided into two sorted parts: a first half where all values are greater than those in the second half and is strictly increasing, and a second half that starts with the minimum element and is strictly increasing.
If there is no rotation, the size of the first half is 0 (the array is fully increasing).
By comparing nums[mid] with nums[right], we can determine which half mid belongs to and shrink the search space accordingly.

Binary Search Process

Initialize left = 0 and right = n - 1. While left < right:

If nums[mid] > nums[right], then mid must be in the first half (the larger part), since nums[right] is the greatest element in the second half. The minimum will always be in the second half, so it must be laying in the right side of mid. 👉 Move search to the right: left = mid + 1.
If nums[mid] ≤ nums[right], then mid lies in the second half (the smaller part), because every element in the first half is greater than any element in the second half, and nums[right] belongs to the second half. In this half, values are increasing and nums[right] is the maximum. The minimum is at the beginning of this half, so it must be either mid itself or somewhere to its left. 👉 Move search to the left side of this half: right = mid.

Termination

When the loop ends, left == right, both pointing to the index of the smallest element in the array. This element is the start of the second increasing section and is the minimum value in the entire array.

Time Complexity

The binary search halves the search interval each iteration and does only constant work per step (compute mid, compare with nums[right], and move one pointer). Therefore, the time complexity is O(log n).

Space Complexity

The algorithm only uses a constant number of variables (left, right, mid) and does not allocate any extra data structures. Therefore, the space complexity is O(1).

Input-1

Find Minimum in Rotated Sorted Array - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Goal

Key Idea (Intuition)

Binary Search Process

Termination

Time Complexity

Space Complexity