Skip to main content
Talentd

Longest Alternating Subarray - Solution & Explanation

EasyArrayEnumeration9 min read
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums. A subarray s of length m is called alternating if:

  • m is greater than 1.
  • s1 = s0 + 1.
  • The 0-indexed subarray s looks like [s0, s1, s0, s1,...,s(m-1) % 2]. In other words, s1 - s0 = 1, s2 - s1 = -1, s3 - s2 = 1, s4 - s3 = -1, and so on up to s[m - 1] - s[m - 2] = (-1)m.

Return the maximum length of all alternating subarrays present in nums or -1 if no such subarray exists.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [2,3,4,3,4]

Output: 4

Explanation:

The alternating subarrays are [2, 3], [3,4], [3,4,3], and [3,4,3,4]. The longest of these is [3,4,3,4], which is of length 4.

Example 2:

Input: nums = [4,5,6]

Output: 2

Explanation:

[4,5] and [5,6] are the only two alternating subarrays. They are both of length 2.

 

Constraints:

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 104

Approach Overview

Problem Overview: Given an integer array, find the longest contiguous subarray where the difference between consecutive elements alternates between +1 and -1, and the first difference must be +1. If no such subarray of length ≥ 2 exists, return -1.

Approach 1: Sliding Window (O(n) time, O(1) space)

This approach scans the array once while maintaining a window that follows the required difference pattern. Start a window whenever you see a pair where nums[i+1] - nums[i] == 1. Then extend the window while the differences alternate between +1 and -1. Each step compares the current difference with the expected one and flips the expectation for the next element. Because every element is processed at most once, the algorithm runs in linear time with constant extra memory. This method is common when working with contiguous patterns in an array and fits naturally with a sliding window strategy.

Approach 2: Dynamic Programming (O(n) time, O(n) space)

The dynamic programming version tracks the length of a valid alternating subarray ending at each index. Define dp[i] as the length of the longest valid alternating sequence ending at position i. If nums[i] - nums[i-1] matches the expected alternating difference relative to the previous step, extend the previous length; otherwise reset when a new +1 difference appears. This approach explicitly stores intermediate states, making the transition logic easier to reason about. It’s useful when practicing pattern-based dynamic programming, though it uses extra memory compared with the sliding window solution.

Recommended for interviews: The sliding window solution is typically what interviewers expect. It demonstrates strong understanding of contiguous pattern detection and linear-time scanning. Mentioning a brute-force enumeration first shows that you understand the problem space, but implementing the O(n) sliding window approach proves you can optimize effectively.

Approach 1: Sliding Window Approach

This approach involves using a sliding window to keep track of the current alternating subarray. The window expands as the alternating pattern is maintained and resets when the pattern breaks.

This Python implementation finds the longest alternating subarray by maintaining a variable for the maximum length found. It iterates over the array with two pointers, expanding the window if the current subarray maintains the alternating pattern and resetting it otherwise.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the input array. Space Complexity: O(1) because the sliding window technique doesn't use extra space related to input size.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach uses dynamic programming to compute the longest alternating subarray ending at each element and keeps track of the maximum found.

This Java implementation utilizes dynamic programming by maintaining a dp array where each index contains the length of the longest alternating subarray ending at that index. The main condition checks for alternation, incrementing length when sustained or starting a new sequence otherwise.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n) due to a single pass through the input. Space Complexity: O(n) for storing the dp array.

Try this approach in the editor →

Approach 3: Enumeration

We can enumerate the left endpoint i of the subarray, and for each i, we need to find the longest subarray that satisfies the condition. We can start traversing to the right from i, and each time we encounter adjacent elements whose difference does not satisfy the alternating condition, we find a subarray that satisfies the condition. We can use a variable k to record whether the difference of the current element should be 1 or -1. If the difference of the current element should be -k, then we take the opposite of k. When we find a subarray nums[i..j] that satisfies the condition, we update the answer to max(ans, j - i + 1).

The time complexity is O(n^2), where n is the length of the array. We need to enumerate the left endpoint i of the subarray, and for each i, we need O(n) time to find the longest subarray that satisfies the condition. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

Time Complexity: O(n) where n is the length of the input array. Space Complexity: O(1) because the sliding window technique doesn't use extra space related to input size.

Dynamic Programming Approach

Time Complexity: O(n) due to a single pass through the input. Space Complexity: O(n) for storing the dp array.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n²)O(1)Useful for understanding the alternating condition by checking every possible subarray.
Sliding WindowO(n)O(1)Best general solution for contiguous pattern detection in arrays with minimal memory.
Dynamic ProgrammingO(n)O(n)Good for learning state transitions and when tracking sequence lengths explicitly.

Video Solution

Leetcode BiWeekly contest 108 - Easy - Longest Alternating Subarray • Prakhar Agrawal • 1,239 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Longest Alternating Subarray easy or hard?
Longest Alternating Subarray is categorized as an Easy problem on LeetCode. The main challenge is recognizing the alternating +1 and -1 difference pattern and applying a linear scan technique such as sliding window or simple dynamic programming.
Longest Alternating Subarray Python/Java solution
Python and JavaScript implementations typically use a sliding window to track valid segments in O(n) time and O(1) space. Java and C# versions can also implement a dynamic programming approach that stores the length of the valid alternating sequence ending at each index.
How to solve Longest Alternating Subarray in O(n)?
Use a sliding window that starts whenever the difference between two adjacent elements equals +1. Continue extending the window while the differences alternate between +1 and -1. If the pattern breaks, reset the window and check again from the next index. This single pass guarantees O(n) time complexity.
What is the best approach for Longest Alternating Subarray?
The sliding window approach is the most efficient and commonly expected solution. It scans the array once while maintaining a valid window where differences alternate between +1 and -1 starting with +1. This achieves O(n) time complexity and O(1) space complexity, making it optimal for large inputs.
Is Longest Alternating Subarray asked at Google/Amazon/Meta?
Alternating pattern and subarray problems frequently appear in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, similar questions test array traversal, sliding window techniques, and pattern recognition in contiguous sequences.
What data structure is used in Longest Alternating Subarray?
The primary data structure is a simple array traversal with two pointers or a sliding window. No complex structures such as heaps or hash maps are required. The algorithm mainly relies on computing differences between adjacent elements.
What is the time complexity of Longest Alternating Subarray?
The optimal solution runs in O(n) time because the array is scanned once while verifying alternating differences. Each element is processed a constant number of times. Space complexity is O(1) for the sliding window approach and O(n) if a dynamic programming array is used.

Ready to solve this problem?

Practice Longest Alternating Subarray with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Turbulent Subarray