CSES Traffic Lights (time complexity of 2nd solution)

I am not able to understand how second solution has O(n) time complexity,
Is it a typo?

for (int i = light_num - 1; i > 0; i--) {
		auto high_it = street_pos.upper_bound(lights[i]);
		int high = *high_it;
		int low = *(--high_it);
		max_gap = std::max(max_gap, high - low);
		gaps[i - 1] = max_gap;

In the given code we can see that upper_bound operation on set is O(log n) and this operation is done light_num of times, which is equivalent to O(nlog n).

Yep, looks like a typo. Though it is possible to solve this in O(N) after sorting the input with the doubly linked list mentioned in the solution to Cow Frisbee.

crap sorry lol i’ll fix sometime