LeetCode Problem 2765

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

LeetCode 2765 - Longest Alternating Subarray

Problem Understanding

This problem asks us to find the longest contiguous subarray that follows a very specific alternating pattern.

Given an integer array nums, we need to identify subarrays where:

1. The subarray length is at least 2.
2. The second element is exactly one greater than the first element.
3. Every subsequent difference alternates between -1 and +1.

If a valid alternating subarray starts with values [x, x + 1], then every following element must continue the pattern:

x, x+1, x, x+1, x, x+1, ...

For example:

[3, 4, 3, 4, 3]

is valid because the consecutive differences are:

+1, -1, +1, -1

However:

[3, 4, 5]

is not valid because the differences are:

+1, +1

which does not alternate.

The input consists of an array nums with length between 2 and 100. Since the array is quite small, even quadratic solutions are acceptable. The values themselves range up to 10^4, but the actual magnitude of the numbers is not important. What matters is the relationship between neighboring elements.

The output should be the length of the longest valid alternating subarray. If no alternating subarray exists, we return -1.

Several edge cases are important:

• Arrays where no adjacent pair differs by exactly 1.
• Arrays containing multiple valid alternating subarrays.
• Arrays where a valid alternating sequence begins in the middle.
• Arrays where the longest valid subarray has length exactly 2.
• Arrays where an alternating pattern breaks after several elements.

Because the array length is only 100, we can afford to examine every possible starting position and extend the alternating sequence as far as possible.

Approaches

Brute Force

The most direct solution is to examine every possible subarray.

For each starting index i, we can generate every ending index j > i and verify whether the subarray nums[i:j+1] satisfies the alternating conditions.

To validate a subarray, we must check:

• The first difference equals +1.
• Every later difference alternates between -1 and +1.

Since there are O(n²) subarrays and each validation may require O(n) work, the total complexity becomes O(n³).

This approach is straightforward and obviously correct because it explicitly checks every candidate subarray. However, it performs unnecessary repeated work when verifying overlapping subarrays.

Optimal Enumeration

Instead of generating every subarray, we can treat each index as a potential starting point.

A valid alternating subarray must begin with:

nums[i+1] = nums[i] + 1

If this condition is not satisfied, index i cannot start a valid alternating sequence.

Once we find a valid start, we extend the sequence to the right while tracking the expected difference. After the initial +1, the next difference must be -1, then +1, then -1, and so on.

As soon as a difference does not match the expected value, the alternating sequence ends.

This avoids repeatedly validating the same prefix and reduces the complexity to O(n²).

Comparison of Approaches

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every subarray and validates each one independently
Optimal	O(n²)	O(1)	Extends alternating sequences from each starting position

Algorithm Walkthrough

Optimal Algorithm

1. Initialize the answer as -1. This represents the case where no valid alternating subarray exists.
2. Iterate through every index i from 0 to n - 2. Each index is considered as a possible starting position.
3. Check whether nums[i + 1] == nums[i] + 1. If not, no valid alternating subarray can start at i, so move to the next index.
4. If the condition is satisfied, we already have a valid alternating subarray of length 2. Update the answer accordingly.
5. Set the current length to 2.
6. The next required difference is -1, because the first difference was already +1.
7. Continue extending the subarray using index j starting from i + 2.
8. For each position, compute:

nums[j] - nums[j - 1]

9. If this difference equals the currently expected value, extend the alternating sequence:

• Increase the current length.
• Update the answer.
• Flip the expected difference by multiplying it by -1.

10. If the difference does not match the expected value, stop extending from this starting index.
11. After processing all starting positions, return the answer.

Why it works

For every possible starting index, the algorithm checks exactly the longest alternating subarray beginning at that position. Any valid alternating subarray must have some starting index, and when that starting index is examined, the algorithm extends the sequence until the first violation occurs. Therefore every valid alternating subarray is considered, and the maximum length among them is recorded. Since the algorithm never accepts a sequence that violates the required alternating differences, the final answer is correct.

Python Solution

from typing import List

class Solution:
    def alternatingSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        answer = -1

        for start in range(n - 1):
            if nums[start + 1] != nums[start] + 1:
                continue

            current_length = 2
            answer = max(answer, current_length)

            expected_diff = -1

            for end in range(start + 2, n):
                if nums[end] - nums[end - 1] == expected_diff:
                    current_length += 1
                    answer = max(answer, current_length)
                    expected_diff *= -1
                else:
                    break

        return answer

The implementation begins by storing the array length and initializing the answer to -1.

The outer loop examines every index as a potential starting position. A valid alternating subarray must begin with a difference of exactly +1, so positions that fail this requirement are skipped immediately.

When a valid start is found, a length-2 alternating subarray already exists. The algorithm records this and initializes the next expected difference to -1.

The inner loop attempts to extend the alternating sequence. Each new difference is compared against the expected value. If it matches, the subarray length increases, the answer is updated, and the expected difference is flipped. If it does not match, the current alternating sequence cannot continue, so the loop stops.

After all starting positions are processed, the maximum length found is returned.

Go Solution

func alternatingSubarray(nums []int) int {
	n := len(nums)
	answer := -1

	for start := 0; start < n-1; start++ {
		if nums[start+1] != nums[start]+1 {
			continue
		}

		currentLength := 2
		if currentLength > answer {
			answer = currentLength
		}

		expectedDiff := -1

		for end := start + 2; end < n; end++ {
			if nums[end]-nums[end-1] == expectedDiff {
				currentLength++

				if currentLength > answer {
					answer = currentLength
				}

				expectedDiff *= -1
			} else {
				break
			}
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. Since the constraints are very small, standard integer arithmetic is completely safe and there is no risk of overflow. Go slices provide efficient indexed access, so no additional data structures are required.

Worked Examples

Example 1

nums = [2,3,4,3,4]

Start = 0

Initial pair:

2 -> 3
difference = +1

Valid start.

Step	Current Element	Difference	Expected	Length
Start	3	+1	+1	2
End=2	4	+1	-1	Stop

Current best:

answer = 2

Start = 1

Initial pair:

3 -> 4
difference = +1

Valid start.

Step	Current Element	Difference	Expected	Length
Start	4	+1	+1	2
End=3	3	-1	-1	3
End=4	4	+1	+1	4

Current best:

answer = 4

Start = 2

Initial pair:

4 -> 3
difference = -1

Invalid start.

Start = 3

Initial pair:

3 -> 4
difference = +1

Valid start.

Length is only:

2

Final answer:

4

Example 2

nums = [4,5,6]

Start = 0

4 -> 5

Valid start.

Next difference:

6 - 5 = 1

Expected:

-1

Mismatch, stop.

Length:

2

Start = 1

5 -> 6

Valid start.

Length:

2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	For each starting index, we may extend through the remaining array
Space	O(1)	Only a few variables are maintained

The outer loop runs n times. In the worst case, each starting position may scan much of the remaining array, resulting in O(n²) time. No auxiliary data structures proportional to the input size are used, so the space complexity remains constant.

Test Cases

from typing import List

s = Solution()

assert s.alternatingSubarray([2, 3, 4, 3, 4]) == 4  # example 1
assert s.alternatingSubarray([4, 5, 6]) == 2  # example 2

assert s.alternatingSubarray([1, 2]) == 2  # smallest valid array
assert s.alternatingSubarray([2, 2]) == -1  # no valid start
assert s.alternatingSubarray([5, 4]) == -1  # difference is not +1

assert s.alternatingSubarray([1, 2, 1]) == 3  # exact alternating length 3
assert s.alternatingSubarray([1, 2, 1, 2]) == 4  # exact alternating length 4
assert s.alternatingSubarray([1, 2, 1, 2, 1]) == 5  # entire array valid

assert s.alternatingSubarray([1, 2, 3, 2, 3]) == 4  # longest starts later
assert s.alternatingSubarray([3, 4, 3, 4, 5]) == 4  # breaks at end

assert s.alternatingSubarray([10, 11, 10, 11, 10, 11]) == 6  # long alternating sequence

assert s.alternatingSubarray([7, 8, 7, 8, 9, 8]) == 4  # pattern breaks in middle

assert s.alternatingSubarray([1, 3, 5, 7]) == -1  # no adjacent +1 pair

assert s.alternatingSubarray([5, 6, 5, 6, 5, 6, 5]) == 7  # maximum covers entire array

Test Summary

Test	Why
[2,3,4,3,4]	Official example with longest length 4
[4,5,6]	Official example with answer 2
[1,2]	Smallest valid input
[2,2]	No valid alternating subarray
[5,4]	Adjacent difference is negative
[1,2,1]	Alternating sequence of length 3
[1,2,1,2]	Alternating sequence of length 4
[1,2,1,2,1]	Entire array alternates
[1,2,3,2,3]	Longest subarray begins after index 0
[3,4,3,4,5]	Alternation breaks near the end
[10,11,10,11,10,11]	Long valid sequence
[7,8,7,8,9,8]	Pattern interruption in the middle
[1,3,5,7]	No valid starting pair exists
[5,6,5,6,5,6,5]	Entire array forms one alternating subarray

Edge Cases

No Valid Starting Pair

Consider:

[1, 3, 5, 7]

Every valid alternating subarray must begin with a difference of exactly +1. Since no adjacent pair satisfies this condition, the answer should be -1. A common bug is accidentally returning 0 or 1. The implementation avoids this by initializing the answer to -1 and only updating it after finding a valid start.

Valid Subarray of Length Two Only

Consider:

[4, 5, 6]

The pair [4,5] is valid, but extending it fails because the next difference is +1 instead of -1. The implementation immediately records length 2 once a valid start is found, ensuring these cases are handled correctly.

Alternation Breaks After Several Elements

Consider:

[1, 2, 1, 2, 3]

The sequence alternates correctly until the final step. The difference from 2 to 3 is +1, but the expected difference is -1. The inner loop stops exactly when the pattern is violated, preserving the longest valid length found so far.

Longest Subarray Does Not Start at Index Zero

Consider:

[5, 5, 3, 4, 3, 4]

A solution that only examines sequences beginning at the first element would miss the correct answer. The algorithm explicitly checks every possible starting position, guaranteeing that alternating subarrays located anywhere in the array are considered.

Entire Array Is Alternating

Consider:

[8, 9, 8, 9, 8, 9]

The alternating pattern never breaks. The inner loop successfully extends to the end of the array, producing the full array length as the answer. This verifies that the implementation correctly handles the maximum possible extension from a starting position.