Watch 10 video solutions for Longest Alternating Subarray, a easy level problem involving Array, Enumeration. This walkthrough by Joey'sTech has 1,525 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |