vlade087's blog

two pointers
By vlade087, 11 years ago, In English

Hello anybody can say me what mean when the problem have a tag two pointers. What mean this approach?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Look here

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

One of the recent problems involving two pointers is problem I:Pirate Chest from ICPC world finals 2013

This problem reduces to one-dimensional case: in integer array, for each element you want to find element that is lower than current on the left and right sides.

For every element you keep left and right positions for the element which is less than this element. (initially set to itselft). Iterate over descendant sorted array and update your info about pointers.

The problem's time limit pretty large. But involving some other NlogN approaches (such as fenwick tree) gives TL. By pointers you achieve lower constant.

→ Reply