Balanced Triplets Subarray
You are given an array and need to return the longest contiguous subarray whose every length-3 window contains a mix of even and odd numbers.
Another way to say the same rule is this: inside the chosen subarray, you must never have three consecutive values with the same parity. A triple of all even numbers breaks the rule, and a triple of all odd numbers breaks it too. But triples like [odd, even, odd] or [even, odd, even] are fine because they contain both parities.
For example, [1,2,1,2,1] is valid all the way through, so the answer is the full array. But [2,2,2] returns an empty array because the only length-3 window is all even. The input [1,2,3,4,5] is also fully valid, because every length-3 window still contains both an even and an odd value.
So the real task is to keep the longest stretch where parity never repeats three times in a row.
Example Input & Output
Every length-3 window contains both parities, so the whole array is valid.
The only length-3 window is all even, so it breaks the rule immediately.
No triple inside the array is all even or all odd, so the full array works.
Algorithm Flow
Solution Approach
The useful observation here is that we do not actually need to inspect every length-3 window from scratch. A length-3 window fails exactly when its three numbers all have the same parity. That means the subarray stays valid as long as we never allow a run of three consecutive evens or three consecutive odds.
So instead of storing every triple, we can scan once from left to right and track the current parity streak. At each index, compare the parity of the current number with the parity of the previous number. If they match, increase the streak length. If they differ, reset the streak length to 1 because a new parity run has started.
Now comes the key window update. If the streak length becomes 3, then the current subarray can no longer include all three of those same-parity values. To fix that, move the left boundary forward so the window keeps only the last two values of that streak. In practice, if we are at index i and the same-parity streak reaches three, the new valid window should start at i - 1.
As we scan, we track the best window length and remember its start and end indices. When the current valid segment becomes longer than the best one so far, we store it. If two valid segments have the same length, you can keep the earlier one unless the problem says otherwise.
This pattern is really a sliding window over a parity condition rather than over raw values. We do not care about the actual numbers except for whether each one is even or odd. That simplification is what makes the linear solution possible.
This works in O(n) time because each element is processed once. The important idea is that the whole condition can be reduced to a simpler local rule: no three consecutive values may share the same parity.
Best Answers
import java.util.*;
class Solution {
public int[] balanced_triplets_subarray(int[] nums) {
int n = nums.length;
if (n < 3) return new int[0];
boolean[] valid_starts = new boolean[n - 2];
for (int i = 0; i < n - 2; i++) {
int odd_cnt = 0;
for (int j = 0; j < 3; j++) {
if (nums[i+j] % 2 != 0) odd_cnt++;
}
if (odd_cnt == 2) valid_starts[i] = true;
}
int longest_len = 0;
int best_start = -1;
int current_start = -1;
int current_len = 0;
for (int i = 0; i < n - 2; i++) {
if (valid_starts[i]) {
if (current_len == 0) current_start = i;
current_len++;
} else {
if (current_len > 0) {
int real_len = current_len + 2;
if (real_len > longest_len) {
longest_len = real_len;
best_start = current_start;
}
}
current_len = 0;
}
}
if (current_len > 0) {
int real_len = current_len + 2;
if (real_len > longest_len) {
longest_len = real_len;
best_start = current_start;
}
}
if (best_start == -1) return new int[0];
return Arrays.copyOfRange(nums, best_start, best_start + longest_len);
}
}Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this Challenge.