A street has n parking spots numbered 0 to n - 1 in a row. Drivers ask the attendant for a spot near a particular number (their favourite shop's door), and the attendant gives them the free spot closest to it.
Implement class Street:
Street(n): allnspots start free (1 <= n <= 200,000).park(want) -> int: occupy and return the free spotsthat minimisesabs(s - want). If two free spots are equally close, pick the lower number. If the street is full, return-1and change nothing.wantis always in0..n-1.leave(spot): the car inspotdrives off, so it's free again. The tests only call this for a spot that is currently occupied.
st = Street(5)
st.park(2) # 2
st.park(2) # 1 (1 and 3 are both one away: lower wins)
st.park(2) # 3
st.park(0) # 0
st.park(1) # 4 (the only spot left)
st.park(3) # -1 (full)
st.leave(1)
st.park(4) # 1
Walking left and right from want until you hit a free spot is O(n) per call when a long stretch is occupied; the tests park 100,000 cars in a row at the same end of a 100,000-spot street. Aim for O(log n) comparisons per call.
Show hint
keep the free spots in a sorted list. With i = bisect_left(free, want), the only candidates are free[i] (the smallest free spot >= want) and free[i - 1] (the largest < want); take the closer, preferring free[i - 1] on a tie, then free.pop(...) it. leave is bisect.insort(free, spot).