Scale Engineer

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.
  • 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

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.

class Solution {    public int alternatingSubarray(int[] nums) {        int n = nums.length;        int maxLength = -1;         for (int i = 0; i < n - 1; i++) {            // Check for the start of an alternating subarray            if (nums[i + 1] == nums[i] + 1) {                // Found a subarray of at least length 2                int currentLength = 2;                if (currentLength > maxLength) {                    maxLength = currentLength;                }                 // Try to extend this subarray                for (int j = i + 2; j < n; j++) {                    // The pattern is s[k] == s[k-2]                    if (nums[j] == nums[j - 2]) {                        currentLength++;                        if (currentLength > maxLength) {                            maxLength = currentLength;                        }                    } else {                        // Pattern broken                        break;                    }                }            }        }        return maxLength;    }}

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.

Solutions

class Solution {public  int alternatingSubarray(int[] nums) {    int ans = -1, n = nums.length;    for (int i = 0; i < n; ++i) {      int k = 1;      int j = i;      for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {        k *= -1;      }      if (j - i + 1 > 1) {        ans = Math.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 →

Next problem