Longest Alternating Subarray

Easy

#2482Time: O(n²), where `n` is the length of `nums`. The nested loops give a quadratic time complexity in the worst case (e.g., an array that is entirely alternating).Space: O(1), as we only use a few variables to store lengths and indices, requiring constant extra space.

Patterns

Enumeration

Data structures

Array

Prompt

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

m is greater than 1.
s₁ = s₀ + 1.
The 0-indexed subarray s looks like [s₀, s₁, s₀, s₁,...,s_{(m-1) % 2}]. In other words, s₁ - s₀ = 1, s₂ - s₁ = -1, s₃ - s₂ = 1, s₄ - s₃ = -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] <= 10⁴

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves checking every possible starting position in the array for an alternating subarray. For each starting position i, we check if an alternating subarray can begin with nums[i] and nums[i+1]. If it can, we then try to extend this subarray as far as possible to the right, keeping track of the maximum length found.

Algorithm

Initialize maxLength to -1 to store the maximum length found.
Iterate through the array with an outer loop using index i from 0 to n-1. This index i represents the starting point of a potential alternating subarray.
For each i, check if a valid alternating subarray of at least length 2 can start. This requires i+1 to be a valid index and nums[i+1] to be equal to nums[i] + 1.
If this condition is met, we have found an alternating subarray of length 2. We update maxLength to be at least 2.
We then start an inner loop with index j from i+2 to n-1 to try and extend this subarray.
The condition for extending the subarray is based on the alternating pattern [s₀, s₁, s₀, s₁, ...], which implies that s[k] == s[k-2]. In terms of the nums array, this means we check if nums[j] == nums[j-2].
If the pattern holds, we increment the length of the current alternating subarray and update maxLength if the new length is greater.
If the pattern breaks (nums[j] != nums[j-2]), we stop extending from the current starting point i and break the inner loop.
After checking all possible starting points, the final value of maxLength is the answer.

Walkthrough

The core idea is to use nested loops. The outer loop selects a starting index i for a potential subarray. The first condition for an alternating subarray is s[1] = s[0] + 1. So, for each i, we first check if nums[i+1] == nums[i] + 1. If this condition is met, we have found an alternating subarray of length 2. We initialize a currentLength to 2 and update our maxLength. Then, we use an inner loop (from j = i + 2) to see how far this subarray can be extended. The pattern of an alternating subarray is [s₀, s₁, s₀, s₁, ...]. This means that for any element at index k, it must be equal to the element at k-2. So, we check if nums[j] == nums[j-2]. If the pattern continues, we increment currentLength and update maxLength. If the pattern breaks, we stop extending from the starting index i and move to the next potential start. We initialize maxLength to -1, and if no alternating subarray is found, this value is returned.

1class Solution {2    public int alternatingSubarray(int[] nums) {3        int n = nums.length;4        int maxLength = -1;5 6        for (int i = 0; i < n - 1; i++) {7            // Check for the start of an alternating subarray8            if (nums[i + 1] == nums[i] + 1) {9                // Found a subarray of at least length 210                int currentLength = 2;11                if (currentLength > maxLength) {12                    maxLength = currentLength;13                }14 15                // Try to extend this subarray16                for (int j = i + 2; j < n; j++) {17                    // The pattern is s[k] == s[k-2]18                    if (nums[j] == nums[j - 2]) {19                        currentLength++;20                        if (currentLength > maxLength) {21                            maxLength = currentLength;22                        }23                    } else {24                        // Pattern broken25                        break;26                    }27                }28            }29        }30        return maxLength;31    }32}

Complexity

Time

O(n²), where `n` is the length of `nums`. The nested loops give a quadratic time complexity in the worst case (e.g., an array that is entirely alternating).

Space

O(1), as we only use a few variables to store lengths and indices, requiring constant extra space.

Trade-offs

Pros

Relatively simple to understand and implement.
Sufficiently efficient for the given constraints (n <= 100).

Cons

The time complexity is not optimal. For larger input arrays, this approach could be too slow.

A more efficient approach is to iterate through the array just once. We can maintain the length of the current alternating subarray ending at the previous position. At each new position, we determine if we can extend the current subarray or if a new one starts, updating the maximum length found so far in a single pass. This approach can be seen as a space-optimized dynamic programming solution.

Algorithm

Handle the edge case where the array has fewer than two elements by returning -1.
Initialize maxLength = 0 to store the result and currentLength = 0 to track the length of the alternating subarray ending at the current position.
Iterate through the array with index i from 1 to n-1.
At each i, we first check if we can extend the alternating subarray that ended at i-1. This is possible if currentLength > 0 (an alternating subarray was active) and nums[i] == nums[i-2] (the pattern s[k] = s[k-2] holds). If so, we increment currentLength.
If we cannot extend, we check if a new alternating subarray of length 2 starts at i-1. This is true if nums[i] == nums[i-1] + 1. If so, we set currentLength = 2.
If neither of the above conditions is met, then no alternating subarray ends at i. We reset currentLength = 0.
After determining the currentLength for the subarray ending at i, we update maxLength = max(maxLength, currentLength).
After the loop, if maxLength is greater than 1, it means we found at least one valid alternating subarray, so we return maxLength. Otherwise, we return -1.

Walkthrough

We iterate through the array from the second element (i = 1). At each step, we decide the length of the alternating subarray ending at the current index i. This length depends on the length of the alternating subarray ending at i-1 and the values of nums[i], nums[i-1], and nums[i-2]. Let currentLength be the length of the alternating subarray ending at the previous index, i-1. When we consider index i, we first check if we can extend the previous subarray. This is possible if currentLength > 0 (meaning there was an active alternating subarray) and nums[i] == nums[i-2] (the alternating pattern continues). If so, the new length is currentLength + 1. If we cannot extend, we check if a new alternating subarray of length 2 starts at i-1. This happens if nums[i] == nums[i-1] + 1. If so, the new length is 2. If neither of these conditions is met, there is no alternating subarray ending at i, so the length is reset. We use a variable currentLength to track the length of the alternating subarray ending at the current index i, and update a maxLength variable at each step.

1class Solution {2    public int alternatingSubarray(int[] nums) {3        int n = nums.length;4        if (n < 2) {5            return -1;6        }7        8        int maxLength = 0;9        int currentLength = 0; // Length of alternating subarray ending at i-110 11        for (int i = 1; i < n; i++) {12            int newLength;13            // Check if we can extend the previous alternating subarray14            if (currentLength > 0 && nums[i] == nums[i - 2]) {15                newLength = currentLength + 1;16            } else {17                // If not, check if a new alternating subarray starts here18                if (nums[i] == nums[i - 1] + 1) {19                    newLength = 2;20                } else {21                    // No alternating subarray ending at i22                    newLength = 0;23                }24            }25            currentLength = newLength;26            if (currentLength > maxLength) {27                maxLength = currentLength;28            }29        }30 31        return maxLength > 1 ? maxLength : -1;32    }33}

Complexity

Time

O(n), where `n` is the length of `nums`. We iterate through the array only once.

Space

O(1), as we only use a constant number of extra variables regardless of the input size.

Trade-offs

Pros

Optimal time complexity, making it efficient for any input size.
Optimal space complexity, as it uses only a constant amount of extra memory.

Cons

The logic is slightly more complex to derive compared to the brute-force approach.

Solutions

Solution

1class Solution {2public3  int alternatingSubarray(int[] nums) {4    int ans = -1, n = nums.length;5    for (int i = 0; i < n; ++i) {6      int k = 1;7      int j = i;8      for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {9        k *= -1;10      }11      if (j - i + 1 > 1) {12        ans = Math.max(ans, j - i + 1);13      }14    }15    return ans;16  }17}

1class Solution {2public:3  int alternatingSubarray(vector<int> &nums) {4    int ans = -1, n = nums.size();5    for (int i = 0; i < n; ++i) {6      int k = 1;7      int j = i;8      for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {9        k *= -1;10      }11      if (j - i + 1 > 1) {12        ans = max(ans, j - i + 1);13      }14    }15    return ans;16  }17};

1class Solution:2    def alternatingSubarray(self, nums: List[int]) -> int: ans, n = - 1, len(nums) for i in range(n): k = 1 j = i while j + 1 < n and nums[j + 1] - nums[j] == k: j += 1 k *= - 1 if j - i + 1 > 1: ans = max(ans, j - i + 1) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem