The trick here is to name the state correctly, then let the implementation follow. For 154. Find Minimum in Rotated Sorted Array II, the solution in this repository is mainly a binary search solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: binary search, two pointers, sliding window.
The notes already sitting in the source point us in the right direction:
- Binary search
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are dfs, findMin.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//Binary search
02//Runtime: 12 ms, faster than 71.51% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
03//Memory Usage: 12.5 MB, less than 26.21% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
04class Solution {
05public:
06 int dfs(vector<int>& nums, int pivot, int l, int r){
07 if(l > r) return -1;
08
09 int mid = (l+r) >> 1;
10 // cout << mid << endl;
11
12 /*
13 found the inflection point:
14 the position where right element < left element
15 */
16 if(mid+1 < nums.size() && nums[mid+1] < nums[mid]) return nums[mid+1];
17 if(mid-1 >= 0 && nums[mid] < nums[mid-1]) return nums[mid];
18
19 if(nums[mid] < pivot){
20 return dfs(nums, pivot, l, mid-1);
21 }else if(nums[mid] > pivot){
22 return dfs(nums, pivot, mid+1, r);
23 }else{
24 //nums[mid] == pivot
25 //need to search in both directions
26 int res1 = dfs(nums, pivot, mid+1, r);
27 int res2 = dfs(nums, pivot, l, mid-1);
28 if(res1 == -1 && res2 == -1){
29 return -1;
30 }else if(res1 != -1){
31 // if(res1 != res2 && res2 != -1){
32 // cout << "get 2 different result: " << res1 << " and " << res2 << endl;
33 // }
34 return res1;
35 }else{
36 return res2;
37 }
38 }
39 };
40
41 int findMin(vector<int>& nums) {
42 int n = nums.size();
43
44 if(n == 1) return nums[0];
45 if(n == 2 && nums[0] == nums[1]) return nums[0];
46
47 /*
48 choose nums[0] as pivot,
49 so we don't need to put nums[0] in the search range
50 */
51 int l = 0, r = n-1;
52
53 //array is sorted, not rotated
54 if(nums[l] < nums[r]) return nums[l];
55
56 int res = dfs(nums, nums[0], 0, n-1);
57
58 return (res == -1) ? nums[0] : res;
59 }
60};
61
62//Binary search, find left boundary
63//https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/48808/My-pretty-simple-code-to-solve-it
64//Runtime: 12 ms, faster than 71.51% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
65//Memory Usage: 12.3 MB, less than 74.40% of C++ online submissions for Find Minimum in Rotated Sorted Array II.
66class Solution {
67public:
68 int findMin(vector<int>& nums) {
69 int n = nums.size();
70 /*
71 choose nums[n-1] as pivot,
72 so the search range is [0, n-2]
73 */
74 int l = 0, r = n-1-1;
75 int mid;
76
77 //find left boundary
78 while(l <= r){
79 mid = (l+r) >> 1;
80 // cout << "look at [" << l << ", " << r << "] - " << mid << ", pivot: " << nums[r+1] << endl;
81
82 if(nums[mid] < nums[r+1]){
83 /*
84 nums[mid:r+1] is increasing,
85 but we want to find inflection point,
86 so next we look at the left part: nums[l:mid]
87 (nums[mid] is implicitly considered since it's our next pivot)
88 */
89 r = mid-1;
90 }else if(nums[mid] > nums[r+1]){
91 /*
92 for the range nums[mid:r+1],
93 the head is larger than the tail,
94 the inflection point must be in this range,
95 so next we look at the right part: nums[mid+1:r+1]
96 */
97 l = mid+1;
98 }else{
99 //nums[mid] == pivot
100 /*
101 since we need to find left boundary,
102 it's safe to shrink right boundary
103 */
104
105 //https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/discuss/48808/My-pretty-simple-code-to-solve-it/48840
106 if (r-1 >= 0 && nums[r-1] > nums[r]) {
107 l = r;
108 break;
109 }
110 --r;
111 }
112 }
113 // cout << "look at [" << l << ", " << r << "]" << endl;
114 // cout << "==============" << endl;
115
116 return nums[l];
117 }
118};Cost