Difficulty: Easy | Acceptance: 35.30% | Paid: No
Topics: Array, Enumeration
You are given a 0-indexed integer array nums. A subarray s of length m is called alternating if: - m > 1 - s₁ - s₀ = 1 - sᵢ₊₁ - sᵢ = (-1)ⁱ for 0 ≤ i < m - 1. For example, [3, 4, 3, 4, 3] is an alternating subarray because [s₁ - s₀, s₂ - s₁, s₃ - s₂, s₄ - s₃] = [1, -1, 1, -1]. Return the maximum length of an alternating subarray of nums, or -1 if no such subarray exists. A subarray is a contiguous non-empty sequence of elements within an array.
- Examples
- Constraints
- Brute Force
- Optimized Enumeration
- Dynamic Programming
- Single Pass (Two Pointers)
Examples
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 has length 4.
Input
nums = [4,5,6]
Output
2
Explanation
The alternating subarrays are [4, 5] and [5, 6]. Both have length 2.
Constraints
- 2 ≤ nums.length ≤ 100
- 1 ≤ nums[i] ≤ 10⁴
Brute Force
Intuition
Check every possible subarray to see if it satisfies the alternating condition.
Steps
- Iterate through all possible starting indices ‘i’ from 0 to n-1.
- Iterate through all possible ending indices ‘j’ from i+1 to n-1.
- For each subarray nums[i…j], verify if the difference between consecutive elements follows the pattern [1, -1, 1, -1, …].
- The difference at index ‘k’ relative to the start ‘i’ should be nums[k+1] - nums[k] == (-1)^(k-i).
- Keep track of the maximum length found among all valid subarrays.
class Solution:
def alternatingSubarray(self, nums: List[int]) -> int:
n = len(nums)
ans = -1
for i in range(n):
for j in range(i + 1, n):
is_alternating = True
for k in range(i, j):
expected_diff = 1 if (k - i) % 2 == 0 else -1
if nums[k+1] - nums[k] != expected_diff:
is_alternating = False
break
if is_alternating:
ans = max(ans, j - i + 1)
return ansComplexity
- Time: O(n³), where n is the length of the array. We iterate through all pairs of indices (n²) and for each pair, we iterate through the subarray (n).
- Space: O(1), as we only use a few variables to track indices and the maximum length.
- Notes: Given the constraints (n ≤ 100), O(n³) is acceptable, but more efficient solutions exist.
Optimized Enumeration
Intuition
Instead of re-checking the entire subarray for every end index, extend the subarray from a fixed start index as long as the condition holds.
Steps
- Iterate through each index ‘i’ as a potential start of an alternating subarray.
- Check if the first difference nums[i+1] - nums[i] is 1. If not, this ‘i’ cannot start a valid subarray.
- If it is 1, continue checking subsequent elements ‘j’.
- The condition for alternating values starting at ‘i’ is that nums[j] must equal nums[i] + (j - i) % 2.
- Stop as soon as the condition is violated and update the maximum length.
class Solution:
def alternatingSubarray(self, nums: List[int]) -> int:
n = len(nums)
ans = -1
for i in range(n - 1):
if nums[i+1] - nums[i] == 1:
for j in range(i + 1, n):
if nums[j] == nums[i] + (j - i) % 2:
ans = max(ans, j - i + 1)
else:
break
return ansComplexity
- Time: O(n²), where n is the length of the array. We iterate through each starting index and potentially scan the rest of the array.
- Space: O(1), as we only use a few variables.
- Notes: This is a significant improvement over O(n³) and is very efficient for the given constraints.
Dynamic Programming
Intuition
The length of an alternating subarray ending at index ‘i’ can be derived from the length of the alternating subarray ending at index ‘i-1’.
Steps
- Define dp[i] as the length of the longest alternating subarray ending at index ‘i’.
- Initialize all dp[i] to 1 (a single element is technically a subarray, though the problem requires length > 1).
- For each index ‘i’ from 1 to n-1:
- Calculate diff = nums[i] - nums[i-1].
- If diff == 1: if dp[i-1] > 1 and the previous difference was -1 (nums[i-1] - nums[i-2] == -1), then dp[i] = dp[i-1] + 1. Otherwise, dp[i] = 2 (starting a new sequence).
- If diff == -1: if dp[i-1] > 1 and the previous difference was 1 (nums[i-1] - nums[i-2] == 1), then dp[i] = dp[i-1] + 1. Otherwise, dp[i] = 1 (cannot start with -1).
- Otherwise, dp[i] = 1.
- The answer is the maximum value in dp that is greater than 1, or -1 if no such value exists.
class Solution:
def alternatingSubarray(self, nums: List[int]) -> int:
n = len(nums)
dp = [1] * n
ans = -1
for i in range(1, n):
diff = nums[i] - nums[i-1]
if diff == 1:
if i > 1 and nums[i-1] - nums[i-2] == -1:
dp[i] = dp[i-1] + 1
else:
dp[i] = 2
elif diff == -1:
if i > 1 and nums[i-1] - nums[i-2] == 1:
dp[i] = dp[i-1] + 1
if dp[i] > 1:
ans = max(ans, dp[i])
return ansComplexity
- Time: O(n), where n is the length of the array. We perform a single pass through the array.
- Space: O(n) to store the DP array. This can be optimized to O(1) by only keeping track of the previous DP value.
- Notes: This approach is optimal in terms of time complexity.
Single Pass (Two Pointers)
Intuition
Use a sliding window approach to find the longest valid subarray in a single traversal.
Steps
- Initialize ‘ans’ to -1 and ‘i’ to 0.
- While ‘i’ is less than n-1:
- Check if nums[i+1] - nums[i] == 1. If not, increment ‘i’ and continue.
- If it is 1, we found a start. Use a second pointer ‘j’ starting at i+1.
- Extend ‘j’ as long as nums[j+1] == nums[j-1] (this maintains the alternating property x, x+1, x, x+1…).
- Update ‘ans’ with the length j - i + 1.
- Set ‘i’ to ‘j’ to start looking for the next sequence from the end of the current one.
class Solution:
def alternatingSubarray(self, nums: List[int]) -> int:
n = len(nums)
ans = -1
i = 0
while i < n - 1:
if nums[i+1] - nums[i] != 1:
i += 1
continue
j = i + 1
while j + 1 < n and nums[j+1] == nums[j-1]:
j += 1
ans = max(ans, j - i + 1)
i = j
return ansComplexity
- Time: O(n), where n is the length of the array. Each element is visited at most twice (once by ‘i’ and once by ‘j’).
- Space: O(1), as we only use a few variables to track indices.
- Notes: This is the most efficient approach in terms of both time and space.