Skip to main content
Talentd

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

HardArrayDynamic ProgrammingEnumeration11 min read
Practice this problem

Problem Statement

You are given an integer array nums.

A subarray nums[l..r] is alternating if one of the following holds:

  • nums[l] < nums[l + 1] > nums[l + 2] < nums[l + 3] > ...
  • nums[l] > nums[l + 1] < nums[l + 2] > nums[l + 3] < ...

In other words, if we compare adjacent elements in the subarray, then the comparisons alternate between strictly greater and strictly smaller.

You can remove at most one element from nums. Then, you select an alternating subarray from nums.

Return an integer denoting the maximum length of the alternating subarray you can select.

A subarray of length 1 is considered alternating.

 

Example 1:

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

Output: 4

Explanation:

  • Choose not to remove elements.
  • Select the entire array [2, 1, 3, 2], which is alternating because 2 > 1 < 3 > 2.

Example 2:

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

Output: 4

Explanation:

  • Choose to remove nums[3] i.e., [3, 2, 1, 2, 3, 2, 1]. The array becomes [3, 2, 1, 3, 2, 1].
  • Select the subarray [3, 2, 1, 3, 2, 1].

Example 3:

Input: nums = [100000,100000]

Output: 1

Explanation:

  • Choose not to remove elements.
  • Select the subarray [100000, 100000].

 

Constraints:

  • 2 <= nums.length <= 105
  • 1 <= nums[i] <= 105

Approach Overview

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.

Solution

We use two arrays l_1 and l_2 to represent the length of the longest alternating subarray ending at position i with the last comparison being "<" and ">", respectively. Similarly, we use r_1 and r_2 to represent the length of the longest alternating subarray starting at position i with the first comparison being "<" and ">", respectively.

We can compute l_1 and l_2 through a single left-to-right traversal, and then compute r_1 and r_2 through a single right-to-left traversal.

Next, we initialize the answer as max(max(l_1), max(l_2)), which represents the length of the longest alternating subarray without removing any elements.

Then, we enumerate the position i of the element to be removed. If after removing position i, positions i-1 and i+1 can still form an alternating relationship, we can add l_1[i-1] and r_1[i+1] (or l_2[i-1] and r_2[i+1]) together to update the answer.

The time complexity is O(n) and the space complexity is O(n).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Removal + ScanO(n^2)O(1)Small arrays or when validating logic during early problem exploration
DP for Alternating Lengths (No Removal)O(n)O(n)Computing baseline alternating segments before considering deletion
Prefix-Suffix Decomposition + EnumerationO(n)O(n)General optimal solution; handles one removal efficiently

Video Solution

Q4. Longest Alternating Subarray After Removing At Most One Element || Leetcode Weekly 487 || 2X 🚀 • Rajan Keshari ( CSE - IIT Dhanbad ) • 1,378 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Longest Alternating Subarray After Removing At Most One Element easy or hard?
The problem is typically classified as Hard because it requires combining dynamic programming, prefix-suffix preprocessing, and careful edge-case handling when merging segments after deletion.
Longest Alternating Subarray After Removing At Most One Element Python/Java solution
Most implementations follow the same structure across languages: build prefix and suffix alternating length arrays, then iterate through possible removal indices. The algorithm works in O(n) time and is easily implemented in Python, Java, C++, Go, TypeScript, or Rust.
How to solve Longest Alternating Subarray After Removing At Most One Element in O(n)?
Precompute two arrays: left[i] for the alternating length ending at i and right[i] for the alternating length starting at i. Then enumerate each index as the removed element and check whether nums[i-1] and nums[i+1] still alternate in parity. If they do, merge left[i-1] and right[i+1]; otherwise take the larger side.
What is the best approach for Longest Alternating Subarray After Removing At Most One Element?
The optimal approach uses prefix-suffix decomposition with enumeration. Compute the longest alternating subarray ending at each index and starting at each index, then try removing every element and merging the two sides if their parity alternates. This runs in O(n) time and O(n) space.
Is Longest Alternating Subarray After Removing At Most One Element asked at Google/Amazon/Meta?
Alternating subarray and single-deletion array problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants that combine dynamic programming with prefix-suffix preprocessing are common in coding rounds.
What data structure is used in Longest Alternating Subarray After Removing At Most One Element?
The main data structures are simple arrays used for dynamic programming. Two auxiliary arrays store prefix and suffix alternating lengths, allowing constant-time checks when enumerating a removed index.
What is the time complexity of Longest Alternating Subarray After Removing At Most One Element?
The optimal solution runs in O(n) time with O(n) space using prefix and suffix alternating length arrays. A naive brute force approach that removes each element and rescans the array takes O(n^2) time.

Ready to solve this problem?

Practice Longest Alternating Subarray After Removing At Most One Element with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays