{"id":1322,"date":"2024-01-05T13:00:00","date_gmt":"2024-01-05T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=1322"},"modified":"2024-01-09T09:40:24","modified_gmt":"2024-01-09T09:40:24","slug":"find-minimum-in-rotated-sorted-array","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/find-minimum-in-rotated-sorted-array\/","title":{"rendered":"Find Minimum in Rotated Sorted Array (with Solution)"},"content":{"rendered":"\n<p>There are many leetcode problems associated with arrays that are being asked in interviews, one of them is finding the minimum in the rotated sorted array. This article will delve into the various approaches to finding the minimum element in a rotated sorted array, with code implementation.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Find Minimum in the Rotated Sorted Array Problem<\/strong><\/h2>\n\n\n\n<p><strong>In the programming problem to find the minimum in the rotated sorted array, we are given a sorted array that has been rotated between 1 and n times. Our task is to find the minimum element in this rotated sorted array.<\/strong> It is important to note that all elements in the array are unique.<\/p>\n\n\n\n<p>Rotating an array [a[0], a[1], a[2], &#8230;, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], &#8230;, a[n-2]].<\/p>\n\n\n\n<p>Let us understand it with an example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><strong>Input:<\/strong> nums = [3,4,5,1,2]<br><strong>Output:<\/strong> 1<\/p>\n\n\n\n<p>Note that the original array was [1,2,3,4,5] rotated 3 times.<\/p>\n\n\n\n<p>Let&#8217;s discuss the easy solution using linear search. In this approach of finding the minimum element, we will traverse the whole array from start to end comparing each element to find the minimum. Here are the steps involved:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>First of all, we will declare a variable to store the minimum element and initialize it with the first element of the array<\/li>\n\n\n\n<li>Now we will start traversing from 2nd element to the last and compare each element with the minimum element. If a smaller element is found, we will update the minimum element<\/li>\n\n\n\n<li>After traversing the entire array, the minimum element will be stored in the variable<\/li>\n\n\n\n<li>Now we will return the minimum element.<\/li>\n<\/ul>\n\n\n\n<p>The Time Complexity of this approach is O(N), where n is the size of the array. The Space Complexity is O(1) as we haven\u2019t used any extra space.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Using Binary Search to Solve It<\/strong><\/h2>\n\n\n\n<p><strong>The best possible way to find the minimum in a rotated sorted array is by using Binary Search.<\/strong> We know that we can apply binary search in a sorted array and a rotated sorted array. We have two sorted halves and we have to detect in which half minimum element is present.<\/p>\n\n\n\n<p><a href=\"https:\/\/favtutor.com\/blogs\/searching-algorithms\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/blogs\/searching-algorithms\">Binary Search and Linear Search<\/a> are the two most used searching algorithms in any programming language.<\/p>\n\n\n\n<p>Let&#8217;s do it step-by-step:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Firstly we will initialize two variables \u2018low\u2019 and \u2018high\u2019 to the first and last indices of the array and mid is calculated as the middle index using the formula \u2018low + (high-low)\/2\u2019.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"413\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-1024x413.png\" alt=\"initialize two variables \u2018low\u2019 and \u2018high\u2019\" class=\"wp-image-1326\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-1024x413.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-300x121.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-768x310.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-750x303.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1-1140x460.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/1.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>&#8216;ans&#8217; is initialized to INT_MAX to keep track of the minimum element.<\/li>\n\n\n\n<li>Now we will run a while loop as long as \u2018low\u2019 is less than or equal to \u2018high\u2019.<\/li>\n\n\n\n<li>Inside the loop, we will check whether the segment of the array from \u2018low\u2019 to \u2018mid\u2019 is sorted, by checking nums[low]&lt;=nums[mid] (3&lt;=5).<\/li>\n\n\n\n<li>If true we will update \u2018ans\u2019 with the minimum of current \u2018ans\u2019 and \u2018nums[low]\u2019 and adjust the search range by updating \u2018low\u2019 to \u2018mid+1\u2019.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"414\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-1024x414.png\" alt=\"Update ans and range\" class=\"wp-image-1327\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-1024x414.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-300x121.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-768x310.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-750x303.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2-1140x460.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2024\/01\/2.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>If the segment is not sorted, it means the rotation point is in the current segment. It updates ans with the minimum of the current ans and nums[mid] and adjusts the search range by updating \u2018high\u2019 to \u2018mid-1\u2019.<\/li>\n\n\n\n<li>The mid is then recalculated using the formula low + (high &#8211; low) \/ 2.<\/li>\n\n\n\n<li>The loop continues until the low is greater than the high, at which point the search range has converged<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Let&#8217;s implement it in C++:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;climits&gt;\n\nusing namespace std;\n\nint findMin(vector&lt;int&gt;&amp; nums) {\n    int n = nums.size();\n    int low = 0;\n    int high = n - 1;\n    int mid = low + (high - low) \/ 2;\n    int ans = INT_MAX;\n\n    while (low &lt;= high) {\n        if (nums[low] &lt;= nums[mid]) {\n            ans = min(ans, nums[low]);\n            low = mid + 1;\n        } else {\n            ans = min(ans, nums[mid]);\n            high = mid - 1;\n        }\n        mid = low + (high - low) \/ 2;\n    }\n\n    return ans;\n}\n\nint main() {\n    vector&lt;int&gt; rotatedArray = {3,4,5,1,2};\n    int minElement = findMin(rotatedArray);\n\n    cout &lt;&lt; &quot;Minimum Element: &quot; &lt;&lt; minElement &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>We can do the binary search approach in Python as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def find_min(nums):\n    n = len(nums)\n    low = 0\n    high = n - 1\n    ans = float('inf')\n\n    while low &lt;= high:\n        mid = low + (high - low) \/\/ 2\n\n        if nums[low] &lt;= nums[mid]:\n            ans = min(ans, nums[low])\n            low = mid + 1\n        else:\n            ans = min(ans, nums[mid])\n            high = mid - 1\n\n    return ans\n\nrotated_array = [3, 4, 5, 1, 2]\nmin_element = find_min(rotated_array)\nprint(&quot;Minimum Element:&quot;, min_element)<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>Finally, here is the Java program to find minimum in rotated sorted array:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class FindMin {\n\n    public static int findMin(int[] nums) {\n        int n = nums.length;\n        int low = 0;\n        int high = n - 1;\n        int ans = Integer.MAX_VALUE;\n\n        while (low &lt;= high) {\n            int mid = low + (high - low) \/ 2;\n\n            if (nums[low] &lt;= nums[mid]) {\n                ans = Math.min(ans, nums[low]);\n                low = mid + 1;\n            } else {\n                ans = Math.min(ans, nums[mid]);\n                high = mid - 1;\n            }\n        }\n\n        return ans;\n    }\n\n    public static void main(String[] args) {\n        int[] rotatedArray = {3, 4, 5, 1, 2};\n        int minElement = findMin(rotatedArray);\n        System.out.println(&quot;Minimum Element: &quot; + minElement);\n    }\n}<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>Minimum Element: 1<\/code><\/pre>\n\n\n\n<p>The time complexity is O(log N), where N is the size of the input array nums. The binary search algorithm is used to find the minimum element, and in each iteration, the search range is effectively halved. The Space complexity is O(1) as we haven\u2019t used any extra space.<\/p>\n\n\n\n<p>Before ending this tutorial, let&#8217;s compare both the approaches:<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td><strong>Approach&nbsp;<\/strong><\/td><td><strong>Time complexity<\/strong><\/td><td><strong>Space complexity<\/strong><\/td><td><strong>Details&nbsp;<\/strong><\/td><\/tr><tr><td>Linear search<br>Approach<\/td><td>O(N)<\/td><td>O(1)<\/td><td>As we are traversing through the array only once to check the minimum element.<\/td><\/tr><tr><td>Binary search Approach<\/td><td>O(Nlogn)<\/td><td>O(1)<\/td><td>The binary search algorithm is used to find the minimum element, and in each iteration, the search range is effectively halved.<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>In conclusion, the <a href=\"https:\/\/leetcode.com\/problems\/find-minimum-in-rotated-sorted-array\/\" target=\"_blank\" data-type=\"link\" data-id=\"https:\/\/leetcode.com\/problems\/find-minimum-in-rotated-sorted-array\/\" rel=\"noreferrer noopener nofollow\">leetcode problem<\/a> of finding the minimum element in a rotated sorted array has been addressed through both a brute-force linear search and an optimized binary search approach, with their time complexity and space complexity and implementation in C++, Java, and Python.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Understand the leetcode problem of finding the Minimum in a Rotated Sorted Array using Binary Search with implementation.<\/p>\n","protected":false},"author":12,"featured_media":1324,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,15],"class_list":["post-1322","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1322","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=1322"}],"version-history":[{"count":3,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1322\/revisions"}],"predecessor-version":[{"id":1351,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/1322\/revisions\/1351"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/1324"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=1322"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=1322"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=1322"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}