daihan's blog

Bounded distinct
By daihan, 8 years ago, In English

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 .

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

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply