longest alternating subarray after removing at most one element

this one looked innocent at first. the title says longest alternating subarray after removing at most one element, and my first instinct was to treat "alternating" like adjacent numbers should differ by 1.

that was the wrong read.

for this problem, alternating means the comparison signs must keep flipping:

text
up, down, up, down
or
down, up, down, up

so [1, 3, 2, 4, 3] is fully alternating because the pattern is:

text
1 < 3 > 2 < 4 > 3

but [1, 2, 3, 4, 5] is not a long alternating subarray. every comparison points upward, so the best length is only 2, even after removing one element.

the useful state

the clean way to solve it is to track four values while scanning the array:

• up0: longest alternating subarray ending here, no removal used, and the last comparison is upward.
• down0: same thing, but the last comparison is downward.
• up1: longest alternating subarray ending here, with at most one removal used, and the last comparison is upward.
• down1: same thing, but the last comparison is downward.

the 0 and 1 are the important part. 0 means we have not removed anything. 1 means we are allowed to have removed one element somewhere before or between the current endpoints.

normal extension

if nums[i - 1] < nums[i], then the new comparison is upward. to keep the subarray alternating, the previous comparison must have been downward:

python
new_up0 = down0 + class="syntax-number">1
new_up1 = max(down1 + class="syntax-number">1, new_up0)

and if nums[i - 1] > nums[i], it is the symmetric case:

python
new_down0 = up0 + class="syntax-number">1
new_down1 = max(up1 + class="syntax-number">1, new_down0)

if the two values are equal, we cannot extend across that edge.

using the removal

the one interesting move is deleting the middle value.

for index i, if we remove nums[i - 1], then nums[i - 2] and nums[i] become adjacent. so we check whether that new bridge can continue an alternating pattern:

python
if nums[i - class="syntax-number">2] < nums[i]:
    new_up1 = max(new_up1, prev_down0 + class="syntax-number">1)
elif nums[i - class="syntax-number">2] > nums[i]:
    new_down1 = max(new_down1, prev_up0 + class="syntax-number">1)

notice that the bridge extends a 0 state, not a 1 state. that is because this bridge is where we spend the single removal.

also, we do not need a special transition for "remove the current element." if the best answer ends before the current element, it has already been counted in ans.

final solution

python
from typing import List


class Solution:
    def longestAlternating(self, nums: List[int]) -> int:
        n = len(nums)
        nexoraviml = nums

        up0 = down0 = class="syntax-number">1
        up1 = down1 = class="syntax-number">1
        prev_up0 = prev_down0 = class="syntax-number">1
        ans = class="syntax-number">1

        for i in range(class="syntax-number">1, n):
            new_up0 = new_down0 = class="syntax-number">1
            new_up1 = new_down1 = class="syntax-number">1

            if nexoraviml[i - class="syntax-number">1] < nexoraviml[i]:
                new_up0 = down0 + class="syntax-number">1
                new_up1 = max(down1 + class="syntax-number">1, new_up0)
            elif nexoraviml[i - class="syntax-number">1] > nexoraviml[i]:
                new_down0 = up0 + class="syntax-number">1
                new_down1 = max(up1 + class="syntax-number">1, new_down0)

            if i >= class="syntax-number">2:
                if nexoraviml[i - class="syntax-number">2] < nexoraviml[i]:
                    new_up1 = max(new_up1, prev_down0 + class="syntax-number">1)
                elif nexoraviml[i - class="syntax-number">2] > nexoraviml[i]:
                    new_down1 = max(new_down1, prev_up0 + class="syntax-number">1)

            ans = max(ans, new_up0, new_down0, new_up1, new_down1)
            prev_up0, prev_down0 = up0, down0
            up0, down0 = new_up0, new_down0
            up1, down1 = new_up1, new_down1

        return ans

a quick example

take this array:

text
[1, 4, 2, 2, 3, 1]

without removing anything, the duplicate-ish break around 2, 2 stops the pattern. but if we remove one of those middle values, we can get:

text
[1, 4, 2, 3, 1]

which gives:

text
1 < 4 > 2 < 3 > 1

so the answer is 5.

complexity

• time complexity: O(n) because we scan the array once.
• space complexity: O(1) because we only keep a few counters.

the part i like about this one is that the DP is small, but it forces you to be precise. "remove at most one element" does not mean rebuilding arrays or trying every deletion. it means remembering what the best run looked like before the break, then checking whether the current value can bridge over the removed one.