3830. Longest Alternating Subarray After Removing At Most One Element

HardArrayDynamic ProgrammingEnumeration

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an integer array nums.

A subarray nums[l..r] is called alternating if the comparisons between adjacent elements keep switching between strictly greater and strictly smaller. Formally, one of the following must hold:

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, as you walk through the subarray comparing each pair of neighboring elements, the relationship strictly alternates: a < is always followed by a >, and a > is always followed by a <. Equal adjacent values are never allowed.

Before selecting your subarray, you are allowed to remove at most one element from nums. After this optional removal, you pick an alternating subarray from the resulting array.

Your task is to return an integer representing the maximum length of the alternating subarray you can obtain.

Note that a subarray consisting of a single element is always considered alternating, so the answer is at least 1.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Finding the longest alternating subarray after at most one removal requires DP tracking both upward and downward alternating states at each position.

Open in Flowchart

Intuition

The problem has two parts mixed together: finding alternating subarrays, and allowing one element to be removed. Let's tackle them step by step.

First, ignore the removal. Suppose we are not allowed to delete anything. Then the task reduces to finding the longest alternating subarray directly. A natural idea is dynamic programming: for each position i, we ask "what is the longest alternating subarray that ends exactly at i?"

But there's a subtlety. To extend an alternating subarray by one element, we need to know what the last comparison was. For example, if the subarray ending at i - 1 finished with a < relationship, then to keep alternating we now need a > relationship between nums[i - 1] and nums[i]. So we cannot describe the state with a single number; we need to track the direction of the last comparison.

This leads us to keep two values at each index:

l1[i]: the length of the longest alternating subarray ending at i whose last comparison is < (meaning nums[i - 1] < nums[i]).
l2[i]: the length of the longest alternating subarray ending at i whose last comparison is > (meaning nums[i - 1] > nums[i]).

The transitions are clean. If nums[i - 1] < nums[i], the last step is a <, so this must follow a subarray that ended with >. Hence l1[i] = l2[i - 1] + 1. Symmetrically, if nums[i - 1] > nums[i], then l2[i] = l1[i - 1] + 1. A single left-to-right pass computes everything, and the best of all l1[i] and l2[i] gives the answer without removal.

Now, bring back the removal. The trick for "at most one removal" problems is prefix-suffix decomposition. If we decide to delete the element at index i, the subarray must come from gluing together a piece ending at i - 1 (the prefix part) with a piece starting at i + 1 (the suffix part). So besides the left-side arrays, we also build right-side arrays by scanning from right to left:

r1[i]: longest alternating subarray starting at i whose first comparison is < (nums[i] < nums[i + 1]).
r2[i]: longest alternating subarray starting at i whose first comparison is > (nums[i] > nums[i + 1]).

The key insight for joining the two pieces: when we delete nums[i], the elements nums[i - 1] and nums[i + 1] become adjacent. For the merged subarray to still be alternating, these two must satisfy a strict comparison, and the directions of the two pieces must line up consistently across the new junction.

Consider the case nums[i - 1] < nums[i + 1]. After joining, the junction is a < relationship. The left piece must end ready for a <, which means its last existing comparison was a >, so we use l2[i - 1]. The right piece must start after a <, so its first comparison should be >, which is exactly r2[i + 1]. These align perfectly, and the combined length is l2[i - 1] + r2[i + 1]. The mirror case nums[i - 1] > nums[i + 1] gives l1[i - 1] + r1[i + 1].

So the overall plan becomes: compute the best answer without removal first, then enumerate every index i as the one to delete and check whether its neighbors can be glued into a longer alternating subarray, updating the answer accordingly. Each of the four arrays is filled in a single linear pass, making the whole approach efficient.

Pattern Learn more about Dynamic Programming patterns.

Solution Approach

Solution 1: Prefix-Suffix Decomposition + Enumeration

We use four arrays, each of length n, all initialized to 1 (since a single element is always alternating):

l1[i]: length of the longest alternating subarray ending at i whose last comparison is < (i.e., nums[i - 1] < nums[i]).
l2[i]: length of the longest alternating subarray ending at i whose last comparison is > (i.e., nums[i - 1] > nums[i]).
r1[i]: length of the longest alternating subarray starting at i whose first comparison is < (i.e., nums[i] < nums[i + 1]).
r2[i]: length of the longest alternating subarray starting at i whose first comparison is > (i.e., nums[i] > nums[i + 1]).

Step 1: Compute l1 and l2 with a left-to-right pass.

For each i from 1 to n - 1, we look at the relationship between nums[i - 1] and nums[i]:

If nums[i - 1] < nums[i], the last comparison is <, which must follow a piece that ended with >, so l1[i] = l2[i - 1] + 1.
If nums[i - 1] > nums[i], the last comparison is >, which must follow a piece that ended with <, so l2[i] = l1[i - 1] + 1.

During this same pass, we update the answer with ans = max(ans, l1[i], l2[i]). This already captures the best alternating subarray without removing any element.

Step 2: Compute r1 and r2 with a right-to-left pass.

For each i from n - 2 down to 0, we look at the relationship between nums[i] and nums[i + 1]:

If nums[i + 1] > nums[i], the first comparison is <, which must precede a piece that started with >, so r1[i] = r2[i + 1] + 1.
If nums[i + 1] < nums[i], the first comparison is >, which must precede a piece that started with <, so r2[i] = r1[i + 1] + 1.

Step 3: Enumerate the deleted element.

For each i from 1 to n - 2, we consider deleting nums[i], which makes nums[i - 1] and nums[i + 1] adjacent. The junction must be a strict comparison, and the two pieces must align in direction:

If nums[i - 1] < nums[i + 1], the junction is a <. The left piece must end ready for a < (last comparison >), giving l2[i - 1]; the right piece must start with >, giving r2[i + 1]. Update ans = max(ans, l2[i - 1] + r2[i + 1]).
If nums[i - 1] > nums[i + 1], the junction is a >. We use l1[i - 1] and r1[i + 1], updating ans = max(ans, l1[i - 1] + r1[i + 1]).

Note that l2[i - 1] + r2[i + 1] correctly counts both joined pieces while the deleted element contributes nothing, so no extra +1 is needed.

Complexity. Each array is filled in a single linear scan, and the enumeration is also linear, so the time complexity is O(n). The four auxiliary arrays use O(n) extra space.

Example Walkthrough

Let's trace the algorithm on a small example:

nums = [4, 5, 3, 2, 6]
indices: 0  1  2  3  4

We want the maximum length alternating subarray after optionally removing at most one element. All four arrays start filled with 1.

Step 1: Left-to-right pass (compute l1 and l2, track ans).

We compare each nums[i-1] with nums[i]:

i = 1: nums[0]=4 < nums[1]=5 → last comparison is <, so l1[1] = l2[0] + 1 = 1 + 1 = 2. Now ans = 2.
i = 2: nums[1]=5 > nums[2]=3 → last comparison is >, so l2[2] = l1[1] + 1 = 2 + 1 = 3. Now ans = 3.
i = 3: nums[2]=3 > nums[3]=2 → last comparison is >, so l2[3] = l1[2] + 1 = 1 + 1 = 2. (l1[2] was still 1 because no < ended at index 2.) ans stays 3.
i = 4: nums[3]=2 < nums[4]=6 → last comparison is <, so l1[4] = l2[3] + 1 = 2 + 1 = 3. ans stays 3.

Resulting arrays:

index:  0  1  2  3  4
l1:     1  2  1  1  3
l2:     1  1  3  2  1

So the best without removal is 3, corresponding to subarray [5, 3, 2]... wait, 5 > 3 > 2 is not alternating. Let's verify: l2[2]=3 came from [4,5,3] where 4<5>3 — that is alternating. Good, length 3.

Step 2: Right-to-left pass (compute r1 and r2).

We compare each nums[i] with nums[i+1]:

i = 3: nums[4]=6 > nums[3]=2 → first comparison is <, so r1[3] = r2[4] + 1 = 1 + 1 = 2.
i = 2: nums[3]=2 < nums[2]=3 → first comparison is >, so r2[2] = r1[3] + 1 = 2 + 1 = 3.
i = 1: nums[2]=3 < nums[1]=5 → first comparison is >, so r2[1] = r1[2] + 1 = 1 + 1 = 2.
i = 0: nums[1]=5 > nums[0]=4 → first comparison is <, so r1[0] = r2[1] + 1 = 2 + 1 = 3.

Resulting arrays:

index:  0  1  2  3  4
r1:     3  1  1  2  1
r2:     1  2  3  1  1

Step 3: Enumerate the deleted element (i from 1 to 3).

When we delete nums[i], neighbors nums[i-1] and nums[i+1] become adjacent:

Delete i = 1 (nums[1]=5): neighbors nums[0]=4 and nums[2]=3. Since 4 > 3, junction is >. Use l1[0] + r1[2] = 1 + 1 = 2. ans stays 3.
Delete i = 2 (nums[2]=3): neighbors nums[1]=5 and nums[3]=2. Since 5 > 2, junction is >. Use l1[1] + r1[3] = 2 + 2 = 4. ans = 4!
Delete i = 3 (nums[3]=2): neighbors nums[2]=3 and nums[4]=6. Since 3 < 6, junction is <. Use l2[2] + r2[4] = 3 + 1 = 4. ans stays 4.

Verification of the winning case. Deleting nums[2]=3 yields [4, 5, 2, 6]. The subarray [4, 5, 2, 6] checks as 4 < 5 > 2 < 6 — a perfectly alternating sequence of length 4. The left piece [4, 5] (from l1[1]=2, ending with <) glues to the right piece [2, 6] (from r1[3]=2, starting with <)...

Actually, let's recheck the join direction: junction 5 > 2 is >, the left piece must end ready for a > and the right piece must start with <. l1[1]=2 means [4,5] ends with < (4<5), then 5>2 adds the >, then 2<6 continues — consistent. The merged length is l1[1] + r1[3] = 4.

Final answer: 4.

This example shows both halves working together: Step 1 alone would only find length 3, but the prefix-suffix decomposition in Step 3 discovers a length-4 subarray that only exists after a single deletion.

Solution Implementation

1from typing import List
2
3
4class Solution:
5    def longestAlternating(self, nums: List[int]) -> int:
6        n = len(nums)
7
8        # up_left[i]: length of the longest alternating subarray ending at index i,
9        #             where the last step goes UP (nums[i-1] < nums[i]).
10        # down_left[i]: length of the longest alternating subarray ending at index i,
11        #               where the last step goes DOWN (nums[i-1] > nums[i]).
12        up_left = [1] * n
13        down_left = [1] * n
14
15        # up_right[i]: length of the longest alternating subarray starting at index i,
16        #              where the first step goes UP (nums[i] < nums[i+1]).
17        # down_right[i]: length of the longest alternating subarray starting at index i,
18        #                where the first step goes DOWN (nums[i] > nums[i+1]).
19        up_right = [1] * n
20        down_right = [1] * n
21
22        ans = 0
23
24        # Forward pass: build alternating runs ending at each index.
25        for i in range(1, n):
26            if nums[i - 1] < nums[i]:
27                # Current step is UP, so it must follow a DOWN step.
28                up_left[i] = down_left[i - 1] + 1
29            elif nums[i - 1] > nums[i]:
30                # Current step is DOWN, so it must follow an UP step.
31                down_left[i] = up_left[i - 1] + 1
32            ans = max(ans, up_left[i], down_left[i])
33
34        # Backward pass: build alternating runs starting at each index.
35        for i in range(n - 2, -1, -1):
36            if nums[i + 1] > nums[i]:
37                # First step is UP, so the next step must be DOWN.
38                up_right[i] = down_right[i + 1] + 1
39            elif nums[i + 1] < nums[i]:
40                # First step is DOWN, so the next step must be UP.
41                down_right[i] = up_right[i + 1] + 1
42
43        # Combine passes: try skipping element i and bridging neighbors i-1 and i+1.
44        for i in range(1, n - 1):
45            if nums[i - 1] < nums[i + 1]:
46                # Bridge with an UP step between i-1 and i+1:
47                # left side must end with DOWN, right side must start with DOWN.
48                ans = max(ans, down_left[i - 1] + down_right[i + 1])
49            elif nums[i - 1] > nums[i + 1]:
50                # Bridge with a DOWN step between i-1 and i+1:
51                # left side must end with UP, right side must start with UP.
52                ans = max(ans, up_left[i - 1] + up_right[i + 1])
53
54        return ans
55

1class Solution {
2    public int longestAlternating(int[] nums) {
3        int n = nums.length;
4
5        // upFromLeft[i]  : length of the longest alternating subarray ending at i,
6        //                  where the last step goes UP   (nums[i-1] < nums[i])
7        // downFromLeft[i]: length of the longest alternating subarray ending at i,
8        //                  where the last step goes DOWN (nums[i-1] > nums[i])
9        int[] upFromLeft = new int[n];
10        int[] downFromLeft = new int[n];
11
12        // upFromRight[i]  : length of the longest alternating subarray starting at i,
13        //                   where the first step goes UP   (nums[i] < nums[i+1])
14        // downFromRight[i]: length of the longest alternating subarray starting at i,
15        //                   where the first step goes DOWN (nums[i] > nums[i+1])
16        int[] upFromRight = new int[n];
17        int[] downFromRight = new int[n];
18
19        // Every single element forms an alternating subarray of length 1 by itself.
20        for (int i = 0; i < n; i++) {
21            upFromLeft[i] = 1;
22            downFromLeft[i] = 1;
23            upFromRight[i] = 1;
24            downFromRight[i] = 1;
25        }
26
27        int ans = 0;
28
29        // Left-to-right pass: build the longest alternating run ending at each index.
30        for (int i = 1; i < n; i++) {
31            if (nums[i - 1] < nums[i]) {
32                // Current step is UP, so it must follow a DOWN step.
33                upFromLeft[i] = downFromLeft[i - 1] + 1;
34            } else if (nums[i - 1] > nums[i]) {
35                // Current step is DOWN, so it must follow an UP step.
36                downFromLeft[i] = upFromLeft[i - 1] + 1;
37            }
38            ans = Math.max(ans, upFromLeft[i]);
39            ans = Math.max(ans, downFromLeft[i]);
40        }
41
42        // Right-to-left pass: build the longest alternating run starting at each index.
43        for (int i = n - 2; i >= 0; i--) {
44            if (nums[i + 1] > nums[i]) {
45                // First step is UP, so the next step must be DOWN.
46                upFromRight[i] = downFromRight[i + 1] + 1;
47            } else if (nums[i + 1] < nums[i]) {
48                // First step is DOWN, so the next step must be UP.
49                downFromRight[i] = upFromRight[i + 1] + 1;
50            }
51        }
52
53        // Combine the two passes by "skipping" the element at index i.
54        // This connects the run ending at i-1 with the run starting at i+1,
55        // treating nums[i-1] and nums[i+1] as adjacent elements.
56        for (int i = 1; i < n - 1; i++) {
57            if (nums[i - 1] < nums[i + 1]) {
58                // nums[i-1] -> nums[i+1] is an UP step, so the left part must end
59                // with a DOWN step and the right part must start with a DOWN step.
60                ans = Math.max(ans, downFromLeft[i - 1] + downFromRight[i + 1]);
61            } else if (nums[i - 1] > nums[i + 1]) {
62                // nums[i-1] -> nums[i+1] is a DOWN step, so the left part must end
63                // with an UP step and the right part must start with an UP step.
64                ans = Math.max(ans, upFromLeft[i - 1] + upFromRight[i + 1]);
65            }
66        }
67
68        return ans;
69    }
70}
71

1class Solution {
2public:
3    int longestAlternating(vector<int>& nums) {
4        int n = nums.size();
5
6        // upFromLeft[i]:   length of the longest alternating subarray ending at i,
7        //                  where the last step goes UP   (nums[i-1] < nums[i])
8        // downFromLeft[i]: length of the longest alternating subarray ending at i,
9        //                  where the last step goes DOWN (nums[i-1] > nums[i])
10        vector<int> upFromLeft(n, 1), downFromLeft(n, 1);
11
12        // upFromRight[i]:   length of the longest alternating subarray starting at i,
13        //                   where the first step (to the right) goes UP   (nums[i] < nums[i+1])
14        // downFromRight[i]: length of the longest alternating subarray starting at i,
15        //                   where the first step (to the right) goes DOWN (nums[i] > nums[i+1])
16        vector<int> upFromRight(n, 1), downFromRight(n, 1);
17
18        int ans = 0;
19
20        // Forward pass: build the alternating run lengths ending at each index.
21        for (int i = 1; i < n; i++) {
22            if (nums[i - 1] < nums[i]) {
23                // Current step is UP, so it extends a run whose previous step was DOWN.
24                upFromLeft[i] = downFromLeft[i - 1] + 1;
25            } else if (nums[i - 1] > nums[i]) {
26                // Current step is DOWN, so it extends a run whose previous step was UP.
27                downFromLeft[i] = upFromLeft[i - 1] + 1;
28            }
29            // Track the best run found so far.
30            ans = max(ans, upFromLeft[i]);
31            ans = max(ans, downFromLeft[i]);
32        }
33
34        // Backward pass: build the alternating run lengths starting at each index.
35        for (int i = n - 2; i >= 0; i--) {
36            if (nums[i + 1] > nums[i]) {
37                // Step to the right is UP, extending a run whose next step was DOWN.
38                upFromRight[i] = downFromRight[i + 1] + 1;
39            } else if (nums[i + 1] < nums[i]) {
40                // Step to the right is DOWN, extending a run whose next step was UP.
41                downFromRight[i] = upFromRight[i + 1] + 1;
42            }
43        }
44
45        // Combine pass: consider removing/skipping index i and joining the
46        // left run (ending at i-1) with the right run (starting at i+1),
47        // making sure the directions stay alternating across the gap.
48        for (int i = 1; i < n - 1; i++) {
49            if (nums[i - 1] < nums[i + 1]) {
50                // The left segment must end going DOWN and the right segment
51                // must start going UP, keeping the alternation consistent.
52                ans = max(ans, downFromLeft[i - 1] + upFromRight[i + 1]);
53            } else if (nums[i - 1] > nums[i + 1]) {
54                // Symmetric case: left ends going UP, right starts going DOWN.
55                ans = max(ans, upFromLeft[i - 1] + downFromRight[i + 1]);
56            }
57        }
58
59        return ans;
60    }
61};
62

1/**
2 * Computes the length of the longest contiguous alternating (zig-zag) subarray.
3 *
4 * Strategy:
5 *  - Two forward DP arrays track the longest alternating run that ENDS at index i,
6 *    distinguished by whether the final comparison step was ascending or descending.
7 *  - Two backward DP arrays track the longest alternating run that STARTS at index i,
8 *    distinguished by whether the first comparison step is ascending or descending.
9 *  - A final pass stitches a left-ending run with a right-starting run across index i
10 *    to capture alternations that bridge a single pivot position.
11 *
12 * @param nums - The input array of numbers.
13 * @returns The length of the longest alternating subarray.
14 */
15function longestAlternating(nums: number[]): number {
16    const length = nums.length;
17
18    // Forward DP: alternating run ending at i whose last step was ascending.
19    const endUp = new Array<number>(length).fill(1);
20    // Forward DP: alternating run ending at i whose last step was descending.
21    const endDown = new Array<number>(length).fill(1);
22    // Backward DP: alternating run starting at i whose first step is ascending.
23    const startUp = new Array<number>(length).fill(1);
24    // Backward DP: alternating run starting at i whose first step is descending.
25    const startDown = new Array<number>(length).fill(1);
26
27    let answer = 0;
28
29    // Build the forward DP arrays by scanning left to right.
30    for (let i = 1; i < length; i++) {
31        if (nums[i - 1] < nums[i]) {
32            // Ascending step: extend a run that previously ended with a descending step.
33            endUp[i] = endDown[i - 1] + 1;
34        } else if (nums[i - 1] > nums[i]) {
35            // Descending step: extend a run that previously ended with an ascending step.
36            endDown[i] = endUp[i - 1] + 1;
37        }
38
39        answer = Math.max(answer, endUp[i]);
40        answer = Math.max(answer, endDown[i]);
41    }
42
43    // Build the backward DP arrays by scanning right to left.
44    for (let i = length - 2; i >= 0; i--) {
45        if (nums[i + 1] > nums[i]) {
46            // First step going right is ascending: extend a run starting with a descending step.
47            startUp[i] = startDown[i + 1] + 1;
48        } else if (nums[i + 1] < nums[i]) {
49            // First step going right is descending: extend a run starting with an ascending step.
50            startDown[i] = startUp[i + 1] + 1;
51        }
52    }
53
54    // Stitch a left-ending run with a right-starting run across the pivot index i.
55    for (let i = 1; i < length - 1; i++) {
56        if (nums[i - 1] < nums[i + 1]) {
57            // Left run ends descending, right run starts descending -> consistent alternation.
58            answer = Math.max(answer, endDown[i - 1] + startDown[i + 1]);
59        } else if (nums[i - 1] > nums[i + 1]) {
60            // Left run ends ascending, right run starts ascending -> consistent alternation.
61            answer = Math.max(answer, endUp[i - 1] + startUp[i + 1]);
62        }
63    }
64
65    return answer;
66}
67

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three separate loops, each iterating over the array once:

The first loop runs from i = 1 to n - 1, performing constant-time comparisons and updates to l1 and l2. This takes O(n) time.
The second loop runs from i = n - 2 down to 0, performing constant-time comparisons and updates to r1 and r2. This also takes O(n) time.
The third loop runs from i = 1 to n - 2, performing constant-time comparisons and max operations. This takes O(n) time.

Since the loops are sequential (not nested), the total time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm allocates four auxiliary arrays l1, l2, r1, and r2, each of size n. The total extra space used is 4n, which simplifies to O(n). The remaining variables (ans, i, n) use constant space, so the overall space complexity is O(n).

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to Initialize `ans` to Cover the Single-Element Case

The problem guarantees that a subarray consisting of a single element is always alternating, so the answer must be at least 1. In the code, ans starts at 0, and the forward-pass loop for i in range(1, n) only runs when n >= 2. If nums has exactly one element, the loop body never executes, and the function returns 0 instead of 1.

Why it happens. The single-element base case is implicitly handled by the * 1 initialization of the four arrays, but ans itself is never seeded with those values when no comparison loop runs.

Solution. Initialize ans = 1 directly, guaranteeing the floor value regardless of n:

n = len(nums)
if n == 0:
    return 0
ans = 1  # a single element is always alternating

This removes the dependence on the loop ever executing and makes the minimum-answer contract explicit.

Pitfall 2: Adding an Erroneous `+1` at the Bridge Junction

When deleting nums[i] and joining nums[i-1] with nums[i+1], it is tempting to write something like down_left[i - 1] + down_right[i + 1] + 1, reasoning that the new junction "adds" a comparison.

Why it's wrong. down_left[i - 1] already counts nums[i-1] as an endpoint (it counts elements, not comparisons), and down_right[i + 1] already counts nums[i+1]. The junction is a comparison between two elements both already counted; the deleted element contributes nothing. Adding +1 would double-count or invent a phantom element, overstating the length by one.

Solution. Keep the bridge sum clean: ans = max(ans, down_left[i - 1] + down_right[i + 1]). Reason in terms of element counts: left piece elements + right piece elements, with the bridged comparison being free.

Pitfall 3: Mismatching Junction Direction with Piece Endings

A subtle logic error is pairing the wrong l/r arrays at the junction. If the junction nums[i-1] < nums[i+1] is an UP step, one might instinctively combine up_left[i-1] (a piece that ended going up) with the right side.

Why it's wrong. Alternation requires that consecutive comparisons strictly switch. If the junction is < (UP), the comparison immediately before it (the left piece's last step) must be > (DOWN), and the comparison immediately after it (the right piece's first step) must also be > (DOWN). So an UP junction pairs with down_left[i-1] and down_right[i+1] — the opposite-direction arrays.

Solution. Always remember the junction sits between the two pieces and must alternate with both their adjacent steps:

if nums[i - 1] < nums[i + 1]:      # junction is UP
    ans = max(ans, down_left[i - 1] + down_right[i + 1])
elif nums[i - 1] > nums[i + 1]:    # junction is DOWN
    ans = max(ans, up_left[i - 1] + up_right[i + 1])

Mnemonic: an < junction must be flanked by > on both sides, hence the down_* arrays.

Pitfall 4: Using `else` Instead of `elif` for Comparisons

Writing if nums[i-1] < nums[i]: ... else: down_left[i] = up_left[i-1] + 1 silently treats the equal case (nums[i-1] == nums[i]) as a valid DOWN step.

Why it's wrong. Equal adjacent values are explicitly forbidden in an alternating subarray. An else branch lumps == together with >, producing an invalid run and an inflated answer.

Solution. Use explicit elif (as the code already does) so that the equality case falls through to neither branch, leaving the arrays at their reset value of 1:

if nums[i - 1] < nums[i]:
    up_left[i] = down_left[i - 1] + 1
elif nums[i - 1] > nums[i]:        # NOT else
    down_left[i] = up_left[i - 1] + 1
# equal case: both stay 1, correctly breaking the run

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering