Solving a Leetcode problem daily — Day 11 | Find Minimum in Rotated Sorted Array | by Subhradeep Saha | May, 2024 | Dev Genius

A detailed guide on how to solve Leetcode’s 153. Find minimum element in rotated sorted array problem using binary search.

blog.devgenius.io

Here is the Leetcode problem —153. Find Minimum in Rotated Sorted Array

Problem Statement

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.

• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array.

You must write an algorithm that runs in O(log n)time.

Constraints:

• n == nums.length

• 1 <= n <= 5000

• -5000 <= nums[i] <= 5000

• All the integers of nums are unique.

• nums is sorted and rotated between 1 and n times.

Examples:

Example 1:
Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:
Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:
Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times.

High-Level Approach

A direct method involves inspecting each element in the array to identify the minimum, but this would incur a time complexity of O(n). However, given that the input array exhibits a sorted-then-rotated characteristic, a more efficient approach could leverage binary search.

How are we getting the min element?

• If somehow we get the index of the max element in the array, then the immediate next element will be the smallest item of the array.

• If the maximum element is at the end of the array, the while loop won’t check the middle element from within. Hence, we return -1 in this case, signifying that the minimum element is at index -1+1 = 0, which is the first element.

Now how to identity the max element?

• The rotation creates two distinct sorted halves, one with elements increasing from the start and another with elements decreasing towards the end.

• The max value will be the one which is greater than its next number. So we divide the search space into half and check if the middle element is the max or not.

if its greater than its next number then we return it as the max element

To further optimize the search space in the next iteration, we can employ a strategy based on the comparison between the middle element and the array’s first element:

=> if the middle element is greater than the first element, it implies that the maximum value cannot exist in the left half of the array. Therefore, we can update the lower index to be m + 1.

=> conversely, if the middle element is less than the first element, it indicates that the maximum item lies in the lower half. Consequently, we can discard the right half and update the upper index to be m.

How are we updating the l, h and why?

• In the while loop with the condition l < h, we’re ensuring that there are at least two items between l and h. Given that the middle index, m moves closer to the value of l when we divide by 2, we can confidently include the condition nums[m] > nums[m+1] without concerns about m+1 going beyond the array boundary. This adjustment streamlines the logic and simplifies the implementation.

• Why do we update l to m+1 and not another value? It’s because when nums[m] > nums[m+1], it indicates that the maximum value is likely between indices l and m including both. We don’t set l to m because we’ve already evaluated m and confirmed that it’s not the maximum value.

• Similarly, when nums[m] < nums[0], we ensure that m remains within the scope for the next iteration. This is because, if nums[m-1] happens to be the maximum value, it will only be identified when compared with its subsequent item which is nums[m].

Code Implementation in C++

class Solution {
public:
    int findPeakIdx(vector<int>& nums) {
        int l = 0, h = nums.size() - 1;
        while(l < h) {
            int m = l + (h-l)/2;
            if(nums[m] > nums[m+1]) {
                return m;
            }

            if(nums[m] > nums[0]) {
                l = m+1;
            }
            else {
                h = m;
            }
        }
        return -1;
    }
    int findMin(vector<int>& nums) {
        int peakIdx = findPeakIdx(nums);
        return nums[peakIdx+1];
    }
};

Detailed Breakdown of the Code:

findPeakIdx():

This function takes a sorted rotated array nums and returns the index of the element at the peak (the point where the decreasing half starts). It uses binary search to achieve this:

• l and h represent the left and right indices of the search space, respectively.

• The loop continues until l < h .

• m is calculated as the middle index.

• If nums[m] is greater than nums[m+1], it signifies the peak is at m (the decreasing half starts after this point).

• Otherwise, we need to determine which half holds the minimum element.

=> If nums[m] is greater than nums[0], the minimum element is likely in the right half (l = m+1).

=> Else, the minimum element is likely in the left half (h = m).

• If the while loop doesn’t return any value from within, it implies that the last element is the maximum value in the array. In this case, we return -1 as the peakIdx.

findMin():

This main function calls findPeakIdx to locate the peak index and then returns the element at the next index (peakIdx+1).

Dry Run with a Test Case

Let’s consider the test case nums = [11, 13, 15, 17]:

findMin calls findPeakIdx passing the input array

InsidefindPeakIdx() :

Iteration 1(l < h):

• loop starts with l = 0 and h = 3.

• m is calculated to be 1

• nums[m] = 13 is not > nums[m+1] = 15

• nums[m] = 13 > nums[0] = 11 so l is updated to be m+1 = 2

Iteration 2(l < h):

• l = 2, h = 3

• m is calculated to be 2

• nums[m] = 15 is not > nums[m+1] = 17

• nums[m] = 15 > nums[0] = 11 so l is updated to be m+1 = 3

Iteration 3(l == h):

• l = 3, h = 3

• since l is not less than h, the while loop terminates and we return -1 from the findPeakIdx() function

InsidefindMin() :

nums[peakIdx + 1] = nums[-1+1] = nums[0] = 11 is returned as the main output.

Time and Space Complexity Analysis

• Time Complexity: The findPeakIdx function employs binary search, halving the search space in each iteration and resulting in a time complexity of O(log n), where n is the array’s size. findMin calls findPeakIdx once and then performs a constant-time operation to retrieve the minimum element, so the overall time complexity remains O(log n).

• Space Complexity: The code uses constant extra space for variables like l, h, and m. This space complexity is independent of the input size and is considered O(1).

Real-World Applications

• Circular Buffers: Circular buffers are used to store data where new elements are written at the end, and old ones are overwritten if the buffer is full. Finding the minimum element in a circular buffer with a sorted (but rotated) access pattern can be solved using this approach.

• Log Analysis: Rotated logs might occur when a log file reaches its maximum size and starts overwriting older entries. To identify the most recent log entry (which might be the minimum based on timestamps), this technique can be employed.

Conclusion

The provided solution leverages binary search to efficiently find the minimum element in a sorted rotated array. This approach achieves a time complexity of O(log n) while utilizing constant extra space. Understanding the concept of rotated sorted arrays and applying binary search principles allows for efficient solutions in various real-world applications where data exhibits similar characteristics.

References

• https://www.reddit.com/r/embedded/comments/1bg65qe/use_of_circular_buffer_in_embedded_systems/

• https://www.digitalocean.com/community/tutorials/how-to-use-journalctl-to-view-and-manipulate-systemd-logs

• Cover Photo by Elena Mozhvilo on Unsplash

• Diagrams are made using Canva

What next?

If you’re intrigued by binary search algorithms, do check out my other posts where I delve into fascinating use cases that are solved using binary search:

• Leetcode — 69. Sqrt(x)

• Leetcode — 278. First Bad Version

• Leetcode — 34. Find first and last position of element in sorted array

Thank you for reading throughout! If you found this post insightful, please show your appreciation by liking this post and sharing it. Don’t forget to follow me for more engaging content like this. Your feedback is valuable, so please feel free to comment or reach out to me with any thoughts or suggestions.