pranshukas's blog

By pranshukas, history, 6 weeks ago, In English

I need help with this Problem Traffic Lights. CSES Problem Set under Sorting and Searching. I thought of an approach that

  1. create a set add elements at every step,

  2. Traverse the set and take the difference and take the maximum out of it.

  3. display maximum at every step.

But I think this is a very naive approach and Time Complexity would be O(n^2) and n can be up to 10^5, so most of my Test Cases are giving TLE.

I am not able to think of another approach. Can Anyone give me a hint, how should I approach it.

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
Hint
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, I didn't get it. Did you meant should I store the left and right index where I'm getting maximum and update it in every step.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Ok I understood you were trying to say just simply maintain a set of positions and map of lenghts and whenever new element is added it will be added between it lower_bound and lower_bound-1. So in map length of new segments to be updated and the old one to be deleted.

    Thanks, for Help.. it got Submitted !!