Longest Alternating Subarray After Removing At Most One Element - Solution & Explanation

Problem Overview: Given an integer array, you want the longest contiguous subarray where adjacent elements alternate in parity (even, odd, even, odd or vice versa). You may remove at most one element anywhere in the array. The task is to compute the maximum possible length of such an alternating subarray after the optional removal.

Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)

Try removing every index i (including the option of removing nothing). For each case, scan the resulting array and compute the longest alternating subarray by checking nums[j] % 2 != nums[j+1] % 2. This directly simulates the problem but requires rebuilding or skipping one element during every scan. The algorithm performs up to n full passes over the array, giving O(n^2) time. Useful only for validating correctness or reasoning about the pattern.

Approach 2: Dynamic Programming Without Removal (O(n) time, O(n) space)

First compute the longest alternating segment ending at each index using a DP array left[i]. If nums[i] has different parity from nums[i-1], extend the previous segment; otherwise restart from length 1. This gives the best alternating subarray when no deletion happens. While it does not yet handle the removal, it builds the structural information needed to connect segments later. This pattern commonly appears in dynamic programming problems involving local transitions.

Approach 3: Prefix-Suffix Decomposition + Enumeration (O(n) time, O(n) space)

Precompute two arrays: left[i] = length of the alternating subarray ending at i, and right[i] = length of the alternating subarray starting at i. Then enumerate each index i as the element to remove. After removal, the two neighbors i-1 and i+1 become adjacent. If their parity differs, you can merge the prefix left[i-1] and suffix right[i+1]. Otherwise the merge is invalid and you take the best side individually. Track the maximum across all removal positions and also the no-removal case. This approach scans the array a constant number of times and uses simple parity checks, giving optimal O(n) time. The technique combines ideas from array preprocessing and enumeration.

Recommended for interviews: Prefix–suffix decomposition with enumeration. Interviewers expect an O(n) solution because the brute force clearly wastes repeated scans. Showing the brute force first demonstrates understanding of the constraint, while deriving prefix and suffix alternating lengths shows strong problem‑solving and DP intuition.