CSES Traffic Lights (time complexity of 2nd solution)

Problems and Contests
#1

solution2
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--) {
		street_pos.erase(lights[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).

#2

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.

#3

crap sorry lol i’ll fix sometime