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.

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.

Description Hints 4 Solution Video 16:48

3830. Longest Alternating Subarray After Removing At Most One Element

Q: 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.

Q: 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.

Hard30.9% acceptance

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 <= 10⁵
1 <= nums[i] <= 10⁵

Topics

Hints open one at a time

Hint 1

Define left[i][d] as the maximum length of an alternating subarray ending at index i, where d = 0 means the last comparison is < and d = 1 means the last comparison is >. Define right[i][d] similarly for subarrays starting at i.

Hint 2

Fill left from left to right and right from right to left; if adjacent values are equal, the alternating chain must restart since == is invalid.

Hint 3

Try removing each index r: if nums[r - 1] < nums[r + 1], the two sides can connect with pattern < >, giving length left[r - 1][0] + right[r + 1][1]; if nums[r - 1] > nums[r + 1], connect with pattern > <, giving left[r - 1][1] + right[r + 1][0].

Hint 4

Also consider not removing any element by taking the maximum value over all left[i][d].

16:48

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def longestAlternating(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,1,3,2]

Input

[3,2,1,2,3,2,1]

Input

[100000,100000]

Your code is saved on this device.Solution