Alternating Sequence Length — Problem Statement & Solution Guide

ArraysMediumIdentifying patterns in arrays

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Arrays and solve the Alternating Sequence Length problem optimally.

TopicArrays

PatternIdentifying patterns in arrays

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array nums, select a subsequence (the relative order of the original array must be kept, but the elements need not be contiguous) such that the sign of each adjacent difference alternates strictly. Formally, for the chosen elements a1,a2,…,ak (k≥2) either a1<a2>a3<… or a1>a2<a3>…. The objective is to maximise k, the length of such a subsequence. If every element in nums is identical, the answer is 1 because a single element trivially satisfies the condition.

DSA Pattern Breakdown

"Alternating Sequence Length"

medium

WHY DOES IT MATTER?

Wiggle‑type patterns appear in signal processing, stock price analysis, and any domain where trends flip; mastering this pattern sharpens ability to reason about local monotonicity constraints in linear time.

OPTIMIZATION CHALLENGE

Realizing that only the best ‘up’ and ‘down’ lengths so far are needed eliminates the quadratic DP table, collapsing the state to two integers and achieving O(n) time and O(1) space.

REAL-WORLD CONNECTION

Think of a load balancer that alternates routing requests between two servers to avoid overload; each decision depends only on the previous direction, mirroring the up/down state machine of the algorithm.

During the interview, write the O(n) solution first, explain why you can discard older states, and only then mention the O(n^2) DP as a conceptual stepping stone.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem is a classic variant of the Wiggle Subsequence. For each position we maintain two DP states: up[i] – length of longest alternating subsequence ending at i with a positive last difference, and down[i] – length with a negative last difference. The recurrence is simple: when nums[i]>nums[j] we can extend a down‑ending sequence, so up[i]=max(up[i],down[j]+1); when nums[i]<nums[j] we extend an up‑ending sequence, so down[i]=max(down[i],up[j]+1). A naïve O(n^2) DP scans all j<i, which fails for n up to 10^5. Observing that only the best up and down seen so far matter yields an O(n) greedy solution: iterate once, update up and down based on the sign of the current difference, ignoring equal values. This reduces both time and space dramatically while preserving optimality because any longer alternating subsequence must respect the local sign changes captured by these two counters.

Interview Questions on This Problem

Q1How would you modify the algorithm if the subsequence must start with a rise (a1<a2) rather than allowing either direction?

Initialize up=1, down=0 and only update up when a positive difference is seen; ignore updates that would start with a fall. The final answer is up, ensuring the first step is an increase.

Q2Can you compute the number of distinct longest alternating subsequences, not just the length?

Yes – augment the DP with count arrays cntUp and cntDown that track how many ways to achieve each length, updating counts only when a longer length is found or adding counts when equal length is achieved, taking care to mod large primes.

Q3What changes are needed if equal adjacent elements are allowed to break the alternation but should be skipped rather than terminating the subsequence?

Treat equal differences as neutral: simply continue without updating up or down, effectively skipping those elements, which the O(n) greedy already does by ignoring nums[i]==nums[i-1].

Examples

Example 1

Input

[3,8,6,10,2,7]

Output

Explanation: The whole array already alternates: 3<8>6<10>2<7, so the maximum length is 6.

Example 2

Input

[4,9,11,13,15]

Output

Explanation: All numbers are increasing, therefore any alternating subsequence can contain at most two distinct values, e.g., 4<9. No longer pattern exists, so the answer is 2.

Example 3

Input

[0,0,0]

Output

Explanation: All elements are equal; no two different values exist, so the longest alternating subsequence consists of a single element.

Constraints

1 <= nums.length <= 100000
-1000000000 <= nums[i] <= 1000000000
The algorithm should run in O(n) time and O(1) additional space

Optimal Approach & Strategy

Maintain two variables up and down while scanning; update them according to the sign of each adjacent difference, yielding a linear‑time solution.

Brute Force Approach

Enumerate every subsequence, check if its adjacent differences alternate, and keep the longest length – exponential time.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function alternatingSequenceLength(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    
    // up[i] = length of longest alternating subsequence ending at i where last diff is positive
    // down[i] = length of longest alternating subsequence ending at i where last diff is negative
    const up = new Array(n).fill(1);
    const down = new Array(n).fill(1);
    
    let maxLen = 1;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                up[i] = Math.max(up[i], down[j] + 1);
            } else if (nums[i] < nums[j]) {
                down[i] = Math.max(down[i], up[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, up[i], down[i]);
    }
    
    return maxLen;
}

const nums = [3, 8, 6, 10, 2, 7];
console.log(alternatingSequenceLength(nums));

#include <iostream>
#include <vector>
using namespace std;

int alternatingSequenceLength(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return n;
    
    // up[i] = length of longest alternating subsequence ending at i where last diff is positive (nums[i] > prev)
    // down[i] = length of longest alternating subsequence ending at i where last diff is negative (nums[i] < prev)
    vector<int> up(n, 1), down(n, 1);
    
    int maxLen = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                up[i] = max(up[i], down[j] + 1);
            } else if (nums[i] < nums[j]) {
                down[i] = max(down[i], up[j] + 1);
            }
        }
        maxLen = max(maxLen, max(up[i], down[i]));
    }
    
    return maxLen;
}

int main() {
    vector<int> nums = {3, 8, 6, 10, 2, 7};
    cout << alternatingSequenceLength(nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int alternatingSequenceLength(int[] nums) {
        int n = nums.length;
        if (n <= 1) return n;
        
        // up[i] = length of longest alternating subsequence ending at i where last diff is positive
        // down[i] = length of longest alternating subsequence ending at i where last diff is negative
        int[] up = new int[n];
        int[] down = new int[n];
        Arrays.fill(up, 1);
        Arrays.fill(down, 1);
        
        int maxLen = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    up[i] = Math.max(up[i], down[j] + 1);
                } else if (nums[i] < nums[j]) {
                    down[i] = Math.max(down[i], up[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, Math.max(up[i], down[i]));
        }
        
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {3, 8, 6, 10, 2, 7};
        System.out.println(alternatingSequenceLength(nums));
    }
}

from typing import List

def alternating_sequence_length(nums: List[int]) -> int:
    n = len(nums)
    if n <= 1:
        return n
    
    # up[i] = length of longest alternating subsequence ending at i where last diff is positive
    # down[i] = length of longest alternating subsequence ending at i where last diff is negative
    up = [1] * n
    down = [1] * n
    
    max_len = 1
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                up[i] = max(up[i], down[j] + 1)
            elif nums[i] < nums[j]:
                down[i] = max(down[i], up[j] + 1)
        max_len = max(max_len, up[i], down[i])
    
    return max_len

if __name__ == "__main__":
    nums = [3, 8, 6, 10, 2, 7]
    print(alternating_sequence_length(nums))

function alternatingSequenceLength(nums) {
    const n = nums.length;
    if (n <= 1) return n;
    
    // up[i] = length of longest alternating subsequence ending at i where last diff is positive
    // down[i] = length of longest alternating subsequence ending at i where last diff is negative
    const up = new Array(n).fill(1);
    const down = new Array(n).fill(1);
    
    let maxLen = 1;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                up[i] = Math.max(up[i], down[j] + 1);
            } else if (nums[i] < nums[j]) {
                down[i] = Math.max(down[i], up[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, up[i], down[i]);
    }
    
    return maxLen;
}

const nums = [3, 8, 6, 10, 2, 7];
console.log(alternatingSequenceLength(nums));

Asked in Top Tech Interviews

Salesforce

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.