I like to read this solution as a small machine: keep the useful information, throw away the noise. For 4. Median of Two Sorted Arrays, the solution in this repository is mainly a binary search solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. 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
- https://www.youtube.com/watch?v=LPFhl65R7ww&feature=emb_logo
- time: O(log(min(m,n)), space: O(1)
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are findMedianSortedArrays.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- 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:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
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(log(min(m,n)), space: O(1)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//binary search
02//https://www.youtube.com/watch?v=LPFhl65R7ww&feature=emb_logo
03//Runtime: 36 ms, faster than 48.68% of C++ online submissions for Median of Two Sorted Arrays.
04//Memory Usage: 89.2 MB, less than 5.16% of C++ online submissions for Median of Two Sorted Arrays.
05//time: O(log(min(m,n)), space: O(1)
06class Solution {
07public:
08 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
09 int m = nums1.size();
10 int n = nums2.size();
11 //need to ensure that nums1 is shorter than or equal to nums2
12 if(m > n){
13 swap(nums1, nums2);
14 swap(m, n);
15 }
16
17 // cout << nums1.size() << ", " << nums2.size() << ", " << m << ", " << n << endl;
18
19 int xstart = 0;
20 int xend = m;
21 int xmid, ymid;
22
23 while(xstart <= xend){
24 /*
25 used to partition x into 2 parts,
26 xmid is the first index of right part in x,
27 also can be seen as left part's size
28 */
29 xmid = (xstart+xend)/2;
30 /*
31 the first index of right part in y,
32 also can be seen as left part's size
33 */
34 ymid = (m+n+1)/2 - xmid;
35
36 // cout << "[" << xstart << ", " << xend << "], " << xmid << ", " << ymid << endl;
37
38 int maxLeftX = (xmid > 0) ? nums1[xmid-1] : INT_MIN;
39 int minRightX = (xmid < m) ? nums1[xmid] : INT_MAX;
40
41 int maxLeftY = (ymid > 0) ? nums2[ymid-1] : INT_MIN;
42 int minRightY = (ymid < n) ? nums2[ymid] : INT_MAX;
43
44 // cout << maxLeftX << ", " << minRightX << ", " << maxLeftY << ", " << minRightY << endl;
45
46 if((maxLeftX <= minRightY) && (maxLeftY <= minRightX)){
47 if((m+n) % 2 == 1){
48 return max(maxLeftX, maxLeftY);
49 }else{
50 return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0;
51 }
52 }
53
54 if(maxLeftX > minRightY){
55 //x's left part is too large, so move left
56 xend = xmid-1;
57 }else if(maxLeftX < minRightY){
58 //x's left part is too small, move right
59 xstart = xmid+1;
60 }
61 }
62
63 return 0.0;
64 }
65};
66
67//binary search, revise to inclusive boundary on both sides(uglier)
68//Runtime: 40 ms, faster than 43.83% of C++ online submissions for Median of Two Sorted Arrays.
69//Memory Usage: 89.3 MB, less than 5.16% of C++ online submissions for Median of Two Sorted Arrays.
70class Solution {
71public:
72 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
73 int m = nums1.size();
74 int n = nums2.size();
75 //need to ensure that nums1 is shorter than or equal to nums2
76 if(m > n){
77 swap(nums1, nums2);
78 swap(m, n);
79 }
80
81 // cout << nums1.size() << ", " << nums2.size() << ", " << m << ", " << n << endl;
82
83 int xstart = 0;
84 int xend = m-1;
85 int xmid, ymid;
86
87 while(xstart <= xend + 1){
88 /*
89 used to partition x into 2 parts,
90 xmid is the last index of left part in x,
91 xmid+1 is the left part's size
92 */
93 /*
94 need to take the minimum!
95 [100001]
96 [100000]
97 */
98 xmid = min(xstart, xend) + (xend-xstart)/2;
99 /*
100 the last index of left part in y,
101 ymid+1 is the right part's size,
102 so (xmid+1) + (ymid+1) is equal to (m+n+1)/2
103 */
104 ymid = (m+n+1)/2 - (xmid+2);
105
106 // cout << "[" << xstart << ", " << xend << "], " << xmid << ", " << ymid << endl;
107
108 int maxLeftX = (xmid >= 0) ? nums1[xmid] : INT_MIN;
109 int minRightX = (xmid+1 < m) ? nums1[xmid+1] : INT_MAX;
110
111 int maxLeftY = (ymid >= 0) ? nums2[ymid] : INT_MIN;
112 int minRightY = (ymid+1 < n) ? nums2[ymid+1] : INT_MAX;
113
114 // cout << maxLeftX << ", " << minRightX << ", " << maxLeftY << ", " << minRightY << endl;
115
116 if((maxLeftX <= minRightY) && (maxLeftY <= minRightX)){
117 if((m+n) % 2 == 1){
118 return max(maxLeftX, maxLeftY);
119 }else{
120 return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.0;
121 }
122 }
123
124 if(maxLeftX > minRightY){
125 //x's left part is too large, so move left
126 xend = xmid-1;
127 }else if(maxLeftX < minRightY){
128 //x's left part is too small, move right
129 xstart = xmid+1;
130 }
131
132 // cout << xstart << ", " << xend << endl;
133 }
134
135 return 0.0;
136 }
137};
138
139//binary search, official solution
140//Runtime: 36 ms, faster than 48.68% of C++ online submissions for Median of Two Sorted Arrays.
141//Memory Usage: 89.2 MB, less than 5.16% of C++ online submissions for Median of Two Sorted Arrays.
142//time: O(log(min(m,n)), space: O(1)
143class Solution {
144public:
145 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
146 int m = nums1.size();
147 int n = nums2.size();
148 //need to ensure that nums1 is shorter than or equal to nums2
149 if(m > n){
150 swap(nums1, nums2);
151 swap(m, n);
152 }
153
154 int xstart = 0;
155 int xend = m;
156
157 while(xstart <= xend){
158 //xmid ranges from 0 to m
159 int xmid = (xstart+xend)/2;
160 //if m > n, ymid may be negative!
161 int ymid = (m+n+1)/2 - xmid;
162
163 if(xmid < m && ymid > 0 && nums2[ymid-1] > nums1[xmid]){
164 //xmid is too small
165 xstart = xmid+1;
166 }else if(xmid > 0 && ymid < n && nums1[xmid-1] > nums2[ymid]){
167 //xmid is too large
168 xend = xmid-1;
169 }else{
170 int maxLeft = max(xmid > 0 ? nums1[xmid-1] : INT_MIN,
171 ymid > 0 ? nums2[ymid-1] : INT_MIN);
172 if((m+n) % 2 == 1) return maxLeft;
173
174 int minRight = min(xmid < m ? nums1[xmid] : INT_MAX,
175 ymid < n ? nums2[ymid] : INT_MAX);
176
177 return (maxLeft+minRight)/2.0;
178 }
179 }
180
181 return 0.0;
182 }
183};Cost
Complexity
Time
O(log(min(m,n)), space: O(1)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.