Блог пользователя daihan

Автор daihan, 7 лет назад, По-английски

Can this problem : Bounded distinct be solvable using two pointer ? If yes what is the logic ? I implemented it with two pointer but code become very much complex . My code . Getting WA for this code .

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I think you're somewhat on the right track based on what I could understand from your code. Just try to make it a lot simpler. What are your two pointers? What should be the state at the end of each iteration?

The simplest idea I could think of is to find the largest valid subarray for each starting index. Left pointer would be the starting index and at each iteration we move the right pointer until we find a duplicate (or hit either the end of the array or maximum allowed interval length) and count the number of valid intervals starting from this index. Sample implementation.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wasted most of the time in contest for a small mistake in this problem. The final answer can range upto 1e10, you should use long long for the answer instead of int. :P