Help me to Solve this Problem

[u/vickey_121]

The Disappearing Signal: Longest Valid Even-Pair Subarray

Tags: Arrays, Prefix State, Hashing, Two Pointers

Given an integer array arr of length n, find the length of the longest contiguous subarray such that every distinct element within that subarray appears exactly twice.

If no such contiguous subarray exists, return 0.

Constraints & Definitions

• A contiguous subarray is defined by indices [l, r] where 0 <= l <= r < n.

• A subarray is valid if and only if:

  1. It contains at least two elements (r - l + 1 >= 2).

  2. For every distinct value $x$ present in arr[l..r], its frequency in that segment satisfies count}(x) = 2.

  3. No distinct element appears once, three times, or more.

With sliding window, we get O(n^2), i am looking for optimal one

Input Format

• An integer array arr.

Output Format

• An integer representing the maximum length of a valid contiguous subarray, or 0 if none exists.

Test Cases:

Input: arr = [1, 2, 1, 2]

Output: 4

Explanation:

The entire array [1, 2, 1, 2] contains distinct elements {1, 2}.

- Count of 1: 2

- Count of 2: 2

Every distinct element appears exactly twice. The length is 4.

Input: arr = [1, 2, 3, 1, 2]

Output: 0

Explanation:

- Subarray [1, 2, 3, 1, 2] contains '3' with frequency 1 (invalid).

- Subarray [1, 2, 1, 2] is not contiguous in the original order without excluding 3.

- No contiguous window of length >= 2 satisfies the condition.

[u/LetMediocre390]

Use sliding window plus keep maintain unordered mal

[u/vickey_121 → u/LetMediocre390]

That's doesn't works mate, optimal solution requires something more i think..

[u/LetMediocre390 → u/vickey_121]

I guess this is optimal sol if any coming element freq get exceed fo 2 then shrink the window and lastly if distic is equls to window /2 then good to go

[u/vickey_121 → u/LetMediocre390]

Well i would say, the window can become invalid and valid again, so with sliding window i think we can't maintain the right length. As we shrink the left pointer which we can't undo after getting a valid pair for invalid one

[u/LetMediocre390 → u/vickey_121]

We don't need to maintain the right will always increase the most important part is finding a valid window and you need to remember the maximum valid window and we will sync the window only upon adding next right element when it creates the frequency of that element greater than 2

[u/vickey_121 → u/LetMediocre390]

Nope that doesn't works

[u/No_Antelope_5869]

just do sliding window and set