Find Minimum in Rotated Sorted Array | Brute Force | Optimized ( O(log N) ) | C++ | Python
Intuition\n\nThis seems like an easy problem if we want to brute force it. But given it is a rotated "sorted" array, we can think about optimizing the solution.
# Intuition\n\nThis seems like an easy problem if we want to brute force it. But given it is a rotated "sorted" array, we can think about optimizing the solution. Algorithms with ```log N``` approach comes to mind and Binary search seems like a good candidate given the nature of the problem wherein we have to incrementally prune some sample space to get closer to our result.\n\nThe array in question looks something like below.\n\n![SmartSelect_20230211_152712_Samsung Notes.jpg](https://assets.leetcode.com/users/images/20894a32-4a98-4c03-bdd7-41b3830fdd5a_1676109667.668417.jpeg)\n\n\n\nIt is clear that we can apply some form of pruning on the array space to narrow down the result. Then it becomes a classic binary search problem with minor changes in logic for boundary and mid pointers.\n\n----------------\n\n# Approach 1 - Brute Force (Accepted)\n\nThe simplest approach that comes to mind after reading the problem is brute forcing through the array space and returning the minimum element among all candidates.\n\n## Complexity\n- Time complexity:\n```O(n)``` as we are traversing all the elements to arrive at the result.\n\n- Space complexity:\n```O(1)``` as we are not using any extra container / array etc. to store intermediate results to arrive at the solution.\n\n## Code\n```cpp []\nclass Solution {\npublic:\n    int findMin(vector<int>& nums) {\n        int min_ele = INT_MAX; // Assign min as INT_MAX\n        for(int i = 0; i < nums.size(); ++i) {\n            if(nums[i] < min_ele) {\n                min_ele = nums[i]; // Check if cur element less than min and update\n            }\n        }\n        return min_ele;\n    }\n};\n```\n```python []\nclass Solution:\n    def findMin(self, nums: List[int]) -> int:\n        # Keeping it simple, no fancy lamda\'s here for now\n        min = 1e9\n        for num in nums:\n            if num < min:\n                min = num\n\n        return min\n```\n\n--------------\n\n# Approach 2 - Optimized ( Binary Search )\n\nAs mentioned above, we are given in the problem statement that the array is a rotated form of its sorted version, so binary search comes to mind. We can prune the search space according to the condition in hand and proceed further. Compare the mid element with the last element and if its larger, prune the left side as minimum will lie on right side. Similarly, follow this for left side conversions.\n\n\n## Code\n```cpp []\nclass Solution {\npublic:\n    int findMin(vector<int>& nums) {\n        // Assign l and r as array boundaries for initial search space\n        int l = 0,r = nums.size() - 1;\n        // Binary search loop\n        while(l < r) {\n            int m = (l + r) / 2; // Or use l + (r - l) / 2 for overflows\n            if(nums[m] > nums[r]) l = m + 1;  // Prune the left space as min lie in right\n            else r = m; // Prune the right space, m can be min also\n        }\n        return nums[l]; // Return the min i.e. l index\n    }\n};\n```\n```python []\nclass Solution:\n    def findMin(self, nums: List[int]) -> int:\n        # Keeping it simple, no fancy lamda\'s here for now\n        # Assign l and r as array boundaries for initial search space\n        l, r = 0, len(nums) - 1\n\n        # Binary search loop\n        while l < r:\n\n            m = (l + r) // 2  # Or use l + (r - l) / 2 for overflows\n            if nums[m] > nums[r]: l = m + 1  # Prune the left space as min lie in right\n            else: r = m  # Prune the right space, m can be min also\n        \n        return nums[l]  # Return the min i.e. l index\n```\n\n## Algorithm\n\nWe will look at the algorithm using an example array ```[4, 5, 6, 7, 0, 1, 2]```.\n\n1. *Iteration 1*: ```m = (l + r) / 2``` which gives ```m = 3```. Now clearly ```nums[m] > nums[r]```, hence we can prune the left portion as minimum can\'t lie in this range. So, ```l = m + 1``` and ```r``` will remain unchanged.\n\n![SmartSelect_20230211_152407_Samsung Notes.jpg](https://assets.leetcode.com/users/images/303fba0d-0dea-4d94-ae19-968cf08d7c16_1676109720.698023.jpeg)\n\n\n\n2. *Iteration 2*: ```m = (l + r) / 2``` which gives ```m = 5```. Now, code will go into the else condition as ```nums[m] < nums[r]```. This means result should lie in left portion ( It can be mid as well ). Hence, ```r = m``` and ```l``` remains unchanged.\n\n![SmartSelect_20230211_152355_Samsung Notes.jpg](https://assets.leetcode.com/users/images/c1283262-ea27-4516-995e-dabfea92aaad_1676109733.7054012.jpeg)\n\n\n\n\n3. *Iteration 3*: ```m = (l + r) / 2``` which gives ```m = 4```. Now, code will go into the else condition as ```nums[m] < nums[r]```. This means result should lie in left portion ( It can be mid as well ). Hence, ```r = m = 4``` and ```l = 4``` as well (unchanged).\n\n![SmartSelect_20230211_152334_Samsung Notes.jpg](https://assets.leetcode.com/users/images/5ef33a0e-5d5b-4d64-8690-56b71501fb65_1676109749.5078168.jpeg)\n\n\n4. Iteration 4: Here, ```l(4)``` not less than ```r(4)```, hence the loop will break and we will return ```nums[l]``` i.e. 0 as our result.\n\n\nWe can quickly look at some corner case as well ( e.g. ```[5, 4]```. This will return after setting ```l``` to index ```1``` as ```arr[m] > arr[r]```). You can dry run on some other cases to have a better understanding / visualisation.\n\n\n\n\n## Complexity\n- Time complexity:\n```O(log N)``` similar to Binary Search algorithm\n\n- Space complexity:\n```O(1)``` similar to Binary Search as we are not using any extra space.\n
['Python', 'C++']