Longest Zigzag Subsequence

Problem

Given an array of integers, find the length of the longest zigzag subsequence. A sequence is called a zigzag sequence if the differences between successive numbers strictly alternate between positive and negative. In other words, the elements of the subsequence alternate between increasing and decreasing order.

A sequence with fewer than two elements is trivially a zigzag subsequence.

A zigzag sequence alternates as follows:

x₁ < x₂ > x₃ < x₄ > x₅ < ...

That is, each element is alternately greater and less than its neighbors.

Examples

Example 1

Input: [1, 9, 3, 9, 1, 6]
Output: 6
Explanation: The sequence [1, 9, 3, 9, 1, 6] is zigzag because the differences (8, -6, 6, -8, 5) alternate in sign.

Example 2

Input: [1, 6, 7, 4, 5]
Output: 3
Explanation: The longest zigzag subsequence is [1, 6, 4] or [6, 7, 4].

Example 3

Input: [1, 9, 4, 4, 5]
Output: 3
Explanation: The longest zigzag subsequence is [1, 9, 4] or [9, 4, 5].

Example 4

Input: [1, 7, 4, 9, 2, 5]
Output: 6
Explanation: The entire sequence is zigzag.

Solution

Method 1 – Dynamic Programming (Two Arrays)

Intuition

The main idea is to use dynamic programming to keep track of the longest zigzag subsequence ending at each index, considering both possible directions (up and down). For each element, we check all previous elements to see if we can extend a zigzag subsequence by increasing or decreasing.

Approach

1. If the array is empty, return 0. If it has one element, return 1.
2. Create two arrays, up and down, where:
   • up[i] is the length of the longest zigzag subsequence ending at index i with an upward move (A[i] > A[j]).
   • down[i] is the length ending at i with a downward move (A[i] < A[j]).
3. Initialize all values in up and down to 1.
4. For each index i from 1 to n-1:
   • For each index j from 0 to i-1:
     • If A[i] > A[j], set up[i] = max(up[i], down[j] + 1).
     • If A[i] < A[j], set down[i] = max(down[i], up[j] + 1).
5. The answer is the maximum value in both up and down arrays.

Code

C++

class Solution {
public:
    int longestZigzag(vector<int>& arr) {
        int n = arr.size();
        if (n == 0) return 0;
        vector<int> up(n, 1), down(n, 1);
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i] > arr[j]) up[i] = max(up[i], down[j] + 1);
                else if (arr[i] < arr[j]) down[i] = max(down[i], up[j] + 1);
            }
            ans = max(ans, max(up[i], down[i]));
        }
        return ans;
    }
};

Go

func LongestZigzag(arr []int) int {
    n := len(arr)
    if n == 0 { return 0 }
    up := make([]int, n)
    down := make([]int, n)
    for i := range up { up[i], down[i] = 1, 1 }
    ans := 1
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if arr[i] > arr[j] {
                if down[j]+1 > up[i] { up[i] = down[j]+1 }
            } else if arr[i] < arr[j] {
                if up[j]+1 > down[i] { down[i] = up[j]+1 }
            }
        }
        if up[i] > ans { ans = up[i] }
        if down[i] > ans { ans = down[i] }
    }
    return ans
}

Java

class Solution {
    public int longestZigzag(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        int[] up = new int[n], down = new int[n];
        Arrays.fill(up, 1); Arrays.fill(down, 1);
        int ans = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) up[i] = Math.max(up[i], down[j] + 1);
                else if (arr[i] < arr[j]) down[i] = Math.max(down[i], up[j] + 1);
            }
            ans = Math.max(ans, Math.max(up[i], down[i]));
        }
        return ans;
    }
}

Python

class Solution:
    def longest_zigzag(self, arr: list[int]) -> int:
        n = len(arr)
        if n == 0:
            return 0
        up = [1] * n
        down = [1] * n
        ans = 1
        for i in range(1, n):
            for j in range(i):
                if arr[i] > arr[j]:
                    up[i] = max(up[i], down[j] + 1)
                elif arr[i] < arr[j]:
                    down[i] = max(down[i], up[j] + 1)
            ans = max(ans, up[i], down[i])
        return ans

Complexity

• ⏰ Time complexity: O(n^2), as we check all pairs (i, j) with i > j.
• 🧺 Space complexity: O(n), for the up and down arrays.