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.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 <= 1001 <= nums[i] <= 104Problem 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.
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.
Python
JavaScript
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.
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.
Time Complexity: O(n) due to a single pass through the input. Space Complexity: O(n) for storing the dp array.
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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 | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n²) | O(1) | Useful for understanding the alternating condition by checking every possible subarray. |
| Sliding Window | O(n) | O(1) | Best general solution for contiguous pattern detection in arrays with minimal memory. |
| Dynamic Programming | O(n) | O(n) | Good for learning state transitions and when tracking sequence lengths explicitly. |
Longest Alternating Subarray | Dynamic programming for coding interviews • Joey'sTech • 1,525 views views
Watch 9 more video solutions →Practice Longest Alternating Subarray with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor