A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 849. Maximize Distance to Closest Person, the solution in this repository is mainly a two pointers 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: two pointers, sliding window.
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 dist, maxDistToClosest, left.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- 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), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//Runtime: 16 ms, faster than 93.26% of C++ online submissions for Maximize Distance to Closest Person.
02//Memory Usage: 10.3 MB, less than 72.29% of C++ online submissions for Maximize Distance to Closest Person.
03
04class Solution {
05public:
06 int dist(int d){
07 //input: the distance btw two seated seats
08 //output: if one person seat btw them, what's the distance of him to the closest person?
09 return d/2;
10 }
11 int maxDistToClosest(vector<int>& seats) {
12 int N = seats.size();
13 vector<int> seated;
14 int ans = 1;
15
16 for(int i = 0; i < N; i++){
17 if(seats[i] == 1) seated.push_back(i);
18 }
19
20 //only one seat seated
21 if(seated.size() == 1) return max(N-1-seated[0], seated[0]);
22
23 //multiple seats seated
24 //boundary condition: seats at first position
25 ans = seated[0];
26 for(int i = 1; i < seated.size(); i++){
27 // cout << seated[i] << " " << seated[i-1] << " " << dist(seated[i] - seated[i-1]) << endl;
28 ans = max(ans, dist(seated[i] - seated[i-1]));
29 }
30 //boundary condition: seats at last position
31 ans = max(ans, N-1-seated[seated.size()-1]);
32
33 return ans;
34 }
35};
36
37/**
38Approach #1: Next Array [Accepted]
39first calculate the distance to left/right person
40**/
41
42/**
43time: O(N), space: O(N)
44**/
45
46//Runtime: 16 ms, faster than 93.26% of C++ online submissions for Maximize Distance to Closest Person.
47//Memory Usage: 10.7 MB, less than 19.28% of C++ online submissions for Maximize Distance to Closest Person.
48
49/**
50class Solution {
51public:
52 int maxDistToClosest(vector<int>& seats) {
53 int N = seats.size();
54 //the distance of a seat to its left/right person
55 //note that we initialize the two vectors with value N
56
57 //for [1,0,0,0]:
58 //right is [0,6,5,4]
59 //left is [0,1,2,3]
60 //and we use min(left, right), so when we look at the area behind the last 1, right is invalid
61
62 //for [0,0,0,1]
63 //left is [4,5,6,0]
64 //right is [3,2,1,0]
65 //similarily, left is invalid when looking at the area behore the first 1
66
67 vector<int> left(N, N), right(N, N);
68
69 for(int i = 0; i < N; i++){
70 if(seats[i] == 1) left[i] = 0;
71 else if(i > 0) left[i] = left[i-1] + 1;
72 }
73
74 for (int i = N-1; i >= 0; --i) {
75 if (seats[i] == 1) right[i] = 0;
76 else if(i < N-1) right[i] = right[i+1] + 1;
77 }
78
79// for(int i = 0; i < N; i++){
80// cout << left[i] << " ";
81// }
82// cout << endl;
83
84// for(int i = 0; i < N; i++){
85// cout << right[i] << " ";
86// }
87// cout << endl;
88
89 int ans = 0;
90 for(int i = 0; i < N; i++){
91 if(seats[i] == 0)
92 ans = max(ans, min(left[i], right[i]));
93 }
94 return ans;
95 }
96};
97**/
98
99/**
100Approach #2: Two Pointer [Accepted]
101**/
102
103/**
104time: O(N), space: O(1)
105**/
106
107//Runtime: 12 ms, faster than 98.25% of C++ online submissions for Maximize Distance to Closest Person.
108//Memory Usage: 9.9 MB, less than 100.00% of C++ online submissions for Maximize Distance to Closest Person.
109
110/**
111class Solution {
112public:
113 int maxDistToClosest(vector<int>& seats) {
114 int N = seats.size();
115 int prev = -1; //first time is -1, go right
116 int future = 0; //go right
117 int ans = 0; //not 1?
118 int left, right;
119
120 for(int i = 0; i < N; i++){
121 if(seats[i] == 1){
122 prev = i;
123 }else{
124 while((future < N && seats[future] == 0) || future < i){
125 future++;
126 }
127 //prev == -1: not person at left
128 left = (prev == -1) ? N : (i-prev);
129 //future == N: no person at right
130 right = (future == N) ? N : (future -i);
131 ans = max(ans, min(left, right));
132 }
133 }
134
135 return ans;
136 }
137};
138**/
139
140/**
141Approach #3: Group by Zero [Accepted]
142count empty seats and ans on the fly
143**/
144
145/**
146time: O(N), space: O(1)
147**/
148
149//Runtime: 12 ms, faster than 98.25% of C++ online submissions for Maximize Distance to Closest Person.
150//Memory Usage: 9.9 MB, less than 100.00% of C++ online submissions for Maximize Distance to Closest Person.
151
152/**
153class Solution {
154public:
155 int maxDistToClosest(vector<int>& seats) {
156 int N = seats.size();
157 int K = 0;
158 int ans = 0;
159
160 for(int i = 0; i < N; i++){
161 if(seats[i] == 0){
162 K++;
163 }else{
164 ans = max(ans, (K+1)/2);
165 K = 0;
166 }
167 }
168
169 for(int i = 0; i < N; i++){
170 if(seats[i] == 1){
171 ans = max(ans, i);
172 break;
173 }
174 }
175
176 for(int i = N-1; i >= 0; i--){
177 if(seats[i] == 1){
178 ans = max(ans, (N-1-i));
179 // ans = max(ans, seats.size()-1-i);
180 break;
181 }
182 }
183
184 return ans;
185 }
186};
187**/Cost
Complexity
Time
O(N), space: O(N)
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.