Find minimum in Rotated Sorted Array

Intuition:

The idea here is to use simple linear search to fnd out the minimum element among the array elements.

Approach:

Begin by initializing mini to INT_MAX, which is the maximum possible value for integers. This ensures that any element in the array will be smaller than mini initially.
Use a for loop to iterate through each element in the array. For each element, update `mini` using the min function. This function compares the current value of mini with the current element and assigns the smaller value back to `mini`. This effectively finds the smallest element encountered so far in the array.
Continue iterating until all elements of the array have been processed. Each iteration ensures that `mini` retains the smallest value found among the elements seen so far. Return this value as the result of the function.

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

class Solution {
public:
    // Function to find minimum element in a vector
    int findMin(vector<int>& arr) {
        int n = arr.size();  
        
         // Initialize mini to maximum integer value
        int mini = INT_MAX;   
        for (int i = 0; i < n; i++) {
            
            /* Update mini with the 
            smaller of mini and arr[i]*/
            mini = min(mini, arr[i]);   
        }
        // Return the minimum element found
        return mini;  
    }
};

int main() {
      
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2, 3}; 
    
    // Create an object of the Solution class
    Solution sol;
    int ans = sol.findMin(arr);   
    
    //Print the result
    cout << "The minimum element is: " << ans << "\n"; 
    return 0;  
}
import java.util.*;

class Solution {
    // Function to find minimum element in an array
    public int findMin(ArrayList<Integer> arr) {
        
        // Initialize mini to maximum integer value
        int mini = Integer.MAX_VALUE;  
        for (int i = 0; i < arr.size(); i++) {
            
            /* Update mini with the
            smaller of mini and arr[i]*/
            mini = Math.min(mini, arr.get(i)); 
        }
        // Return the minimum element found
        return mini; 
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(4, 5, 6, 7, 0, 1, 2, 3));
    
        // Create an object of the Solution class
        Solution sol = new Solution();  
        
        int ans = sol.findMin(arr); 
        
        // Print the result
        System.out.println("The minimum element is: " + ans); 
    }
}
class Solution:
    # Function to find minimum element in a list
    def findMin(self, arr):
        
        # Initialize mini to maximum float value
        mini = float('inf') 
        for num in arr:
            
            """ Update mini with the
            smaller of mini and num"""
            mini = min(mini, num) 
        # Return the minimum element found
        return mini 

if __name__ == "__main__":
    arr = [4, 5, 6, 7, 0, 1, 2, 3]
    
     # Create an object of the Solution class
    sol = Solution()
    
    ans = sol.findMin(arr) 
    
    # Print the result
    print("The minimum element is:", ans) 
class Solution {
    // Function to find minimum element in an array
    findMin(arr) {
        // Initialize mini to maximum infinity value
        let mini = Infinity; 
        for (let num of arr) {
            
            /* Update mini with the 
            smaller of mini and num*/
            mini = Math.min(mini, num); 
        }
        // Return the minimum element found
        return mini; 
    }
}

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

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

let ans = sol.findMin(arr);  

// Print the result
console.log("The minimum element is:", ans); 

Complexity Analysis:

Time Complexity:O(N), where N is size of the array. As the array is being traversed only once using a single loop.

Space Complexity:O(1), As no additional space is used.

Intuition:

As the given array is sorted and then rotated, we can optimize the brute-force solution by applying the binary search algorithm. In any sorted array, the minimum element is located at the very first index. This observation allows us to reduce the search space by half in each iteration. The task is to identify the sorted half of the array, store its minimum element (which is the first element of this half), and then eliminate this half from our search space.

Approach:

First, initialize few variables: low to 0 and high to sizeOfArray - 1, which represent the indices of the array arr that define the current search range, ans to Integer.MAX_VALUE, which ensures that any element in the array will be smaller than ans initially.
Use a while loop to continue searching while low is less than or equal to high. This ensures that the search space is valid and non-empty. Compute the midpoint mid of the current search range using mid = (low + high) / 2 or mid = low + (high-low)/2.
Compare element at (low) with element at (mid). If element at (low) is less than or equal to element at (mid), then the left part from low to mid is sorted:
1. Update ans with the minimum of its current value and element at (low). This step ensures that ans always holds the smallest element encountered in the sorted part of the array.
2. Move the low pointer to mid + 1 to search in the right part of the array, as the minimum element cannot be in the left part (which is already sorted).
If the left part is not sorted (element at (low) is greater than element at (mid)), then the right part from mid to high is sorted:
1. Update ans with the minimum of its current value and element at (mid). This ensures ans contains the smallest element encountered in the sorted part of the array.
2. Move the high pointer to mid - 1 to search in the left part of the array, as the minimum element cannot be in the right part (which is already sorted).
Once the loop completes,` ans` will contain the smallest element found in the rotated sorted array. Return `ans` as the minimum element in the rotated sorted array.

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

class Solution {
public:
    /* Function to find minimum element
    in a rotated sorted array */
    int findMin(vector<int>& arr) {
        
        // Initialize low and high indices
        int low = 0, high = arr.size() - 1; 
        
        // Initialize ans to maximum integer value
        int ans = INT_MAX;  
        while (low <= high) { 
            int mid = (low + high) / 2; 

            // Check if left part is sorted
            if (arr[low] <= arr[mid]) {
                
                /* Update ans with minimum 
                of ans and arr[low] */
                ans = min(ans, arr[low]);  
                
                // Move to the right part
                low = mid + 1;  
            } 
            else {  
                /* Update ans with minimum 
                of ans and arr[mid] */
                ans = min(ans, arr[mid]);  
                
                // Move to the left part
                high = mid - 1;  
            }
        }
        // Return the minimum element found
        return ans; 
    }
         
};

int main() {
    
    vector<int> arr = {4, 5, 6, 7, 0, 1, 2, 3};  
    
    // Create an object of the Solution class
    Solution sol; 
     
    int ans = sol.findMin(arr); 
    
    // Print the result
    cout << "The minimum element is: " << ans << "\n";  
    return 0; 
}
import java.util.*;

class Solution {
    /* Function to find minimum element
    in a rotated sorted array */
    public int findMin(ArrayList<Integer> arr) {
        // Initialize low and high indices
        int low = 0, high = arr.size() - 1;
        
        // Initialize ans to maximum integer value
        int ans = Integer.MAX_VALUE;
        while (low <= high) {
            int mid = (low + high) / 2;
            
            // Check if left part is sorted
            if (arr.get(low) <= arr.get(mid)) {
                /* Update ans with minimum 
                of ans and arr[low] */
                ans = Math.min(ans, arr.get(low));
                
                // Move to the right part
                low = mid + 1;
            } else {
                /* Update ans with minimum 
                   of ans and arr[mid] */
                ans = Math.min(ans, arr.get(mid));
                
                // Move to the left part
                high = mid - 1;
            }
        }
        // Return the minimum element found
        return ans;
    }

    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(4, 5, 6, 7, 0, 1, 2, 3));
    
        //Create an instance of the Solution class
        Solution sol = new Solution();
        
        int ans = sol.findMin(arr);
        
        System.out.println("The minimum element is: " + ans);
    }
}
class Solution:
    """ Function to find minimum element
        in a rotated sorted array """
    def findMin(self, arr):
        # Initialize low and high indices
        low, high = 0, len(arr) - 1
        
        # Initialize ans to maximum integer value
        ans = float('inf')
        while low <= high:
            mid = (low + high) // 2
            
            # Check if left part is sorted
            if arr[low] <= arr[mid]:
                """ Update ans with minimum 
                    of ans and arr[low] """
                ans = min(ans, arr[low])
                
                # Move to the right part
                low = mid + 1
            else:
                """ Update ans with minimum 
                    of ans and arr[mid] """
                ans = min(ans, arr[mid])
                
                # Move to the left part
                high = mid - 1
        
        # Return the minimum element found
        return ans

if __name__ == "__main__":
    arr = [4, 5, 6, 7, 0, 1, 2, 3]
    
    #Create an instance of the Solution class
    sol = Solution()
    
    ans = sol.findMin(arr)
    
    print("The minimum element is:", ans)
class Solution {
    /* Function to find minimum element
       in a rotated sorted array */
    findMin(arr) {
        // Initialize low and high indices
        let low = 0, high = arr.length - 1;
        
        // Initialize ans to maximum integer value
        let ans = Infinity;
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            
            // Check if left part is sorted
            if (arr[low] <= arr[mid]) {
                /* Update ans with minimum 
                   of ans and arr[low] */
                ans = Math.min(ans, arr[low]);
                
                // Move to the right part
                low = mid + 1;
            } else {
                /* Update ans with minimum 
                   of ans and arr[mid] */
                ans = Math.min(ans, arr[mid]);
                
                // Move to the left part
                high = mid - 1;
            }
        }
        // Return the minimum element found
        return ans;
    }
}

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

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

let ans = sol.findMin(arr);

console.log("The minimum element is:", ans);

Complexity Analysis:

Time Complexity:O(log(N)), where N is size of the array. Because binary search is being used.

Space Complexity:O(1) As no additional space is used.

Problem List

Find minimum in Rotated Sorted Array

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Intuition:

Approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code