Find Longest Alternating Subarray

Title: Find Longest Alternating Subarray

In this guide, you will learn how to find the longest alternating subarray inside an array of integers using Java. This is a classic array-scanning problem that shows up often in coding interviews because it tests whether you can track a changing condition across a sliding window without extra memory.

We will look at the problem definition, build a linear-time algorithm from scratch, trace it by hand on a sample array, and then walk through common mistakes and interview follow-up questions so you are fully prepared to discuss this problem out loud.

Understanding the Problem

You are given an array of non-negative integers called nums. A subarray is considered alternating if it has at least two elements and the difference between each pair of consecutive elements flips sign every step: the first difference must be +1, the second must be -1, the third must be +1, and so on.

Your task is to return the length of the longest subarray that satisfies this pattern. If no two consecutive elements ever differ by exactly 1, no alternating subarray exists, and the function should return -1 instead of 0, since 0 would be ambiguous with a valid answer.

Approach

1. Initialize maxLen to -1 and the starting pointer i to 0; this sentinel value signals that no alternating subarray was found if the array never produces one.
2. At each i, check whether nums[i + 1] - nums[i] equals 1; if it does not, move i forward by one and try the next starting point.
3. When the first difference is 1, start extending a candidate run from index i: set j = i + 1 and expectedDiff = -1.
4. Keep extending while nums[j + 1] - nums[j] equals expectedDiff; each successful match flips expectedDiff between -1 and 1 and advances j by one.
5. Once the alternation breaks or the array ends, the run covers indices i through j, so update maxLen with j - i + 1 if it is larger.
6. Set i = j so the next outer-loop pass starts exactly where this run stopped, instead of skipping a potential new starting point.
7. Repeat these steps until i reaches the second-to-last index, then return maxLen.

Java Program

public class LongestAlternatingSubarray {

    public static int longestAlternatingSubarray(int[] nums) {
        int n = nums.length;
        int maxLen = -1;
        int i = 0;

        while (i < n - 1) {
            if (nums[i + 1] - nums[i] != 1) {
                i++;
                continue;
            }

            int j = i + 1;
            int expectedDiff = -1;

            while (j < n - 1 && nums[j + 1] - nums[j] == expectedDiff) {
                expectedDiff = -expectedDiff;
                j++;
            }

            maxLen = Math.max(maxLen, j - i + 1);
            i = j;
        }

        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {4, 5, 4, 5, 6, 7, 2};
        int result = longestAlternatingSubarray(nums);
        System.out.println("Longest alternating subarray length: " + result);
    }
}

Explanation of the Program

The method longestAlternatingSubarray scans the array once with two pointers, i and j. The outer while loop picks a candidate starting index, and the inner while loop stretches that candidate as far as the alternating pattern allows.

• maxLen starts at -1 so an array with no alternating pair correctly reports that no valid subarray was found.
• The outer loop only enters the candidate-building block when nums[i + 1] - nums[i] == 1, which is the required first step of every alternating run.
• expectedDiff starts at -1 because the second step of the pattern must be a decrease; it flips sign with -expectedDiff after every successful match.
• The inner loop condition j < n - 1 guards against reading nums[j + 1] past the end of the array.
• After the inner loop stops, the run spans indices i through j inclusive, so its length is j - i + 1.
• Setting i = j instead of i = j + 1 lets the next outer-loop pass reconsider index j as a fresh starting point, since the diff that broke the pattern might itself be +1.

Step-by-Step Trace

Consider nums = {1, 2, 1, 2, 3, 4, 2}, where the correct answer is 4. The table below follows the outer loop pointer i through every pass, showing how far each candidate run extends and how maxLen changes.

At the end of every outer-loop pass, maxLen holds the length of the longest alternating run found among all starting indices examined so far, which is why the final value returned once i reaches n - 1 is the answer for the whole array.

Examples

Example 1: A Strictly Increasing Array

When every element increases by more than one step, the only alternating runs possible are length-2 pairs, since the second required difference of -1 never appears.

int[] nums = {1, 2, 3, 4};
System.out.println(longestAlternatingSubarray(nums));
// Output: 2

Example 2: No Alternating Subarray Exists

A strictly decreasing array never produces a first difference of +1, so the method should return -1 rather than 0.

int[] nums = {10, 9, 8, 7};
System.out.println(longestAlternatingSubarray(nums));
// Output: -1

Example 3: Multiple Runs of Different Lengths

This array contains a long zigzag run followed by a short one, which demonstrates that the method keeps the maximum across every candidate it tries instead of returning as soon as one run ends.

int[] nums = {3, 4, 3, 4, 3, 4, 10, 11};
System.out.println(longestAlternatingSubarray(nums));
// Output: 6

Common Mistakes to Avoid

These are the mistakes learners most often make when implementing this exact algorithm.

• Checking nums[j + 1] without a bound check - using j < n instead of j < n - 1 inside the inner loop throws an ArrayIndexOutOfBoundsException when j reaches the last index. Guard the inner loop with j < n - 1.
• Forgetting to reset expectedDiff - reusing the value left over from the previous candidate run makes the next run's alternation check wrong from its very first comparison. Reset expectedDiff = -1 every time a new run starts.
• Returning 0 for no match - returning 0 when no alternating subarray exists is indistinguishable from a valid zero-length result and breaks any caller checking for failure. Return -1 as the sentinel instead.
• Advancing i past j - setting i = j + 1 after a run ends skips the possibility that index j starts a brand-new alternating run. Set i = j so that starting point is still considered.
• Comparing diffs with Math.abs - using Math.abs(nums[i + 1] - nums[i]) == 1 wrongly accepts a first step of -1, which is not part of this problem's definition. Compare against the exact signed value, == 1 for the first step and the signed expectedDiff afterward.

Edge Cases to Test

Walk through these input shapes out loud before you consider the solution finished.

• Empty array
• Single-element array
• Two-element array with a diff of exactly 1
• Strictly decreasing array (no diff of +1 anywhere)
• All elements identical
• Alternating run that spans the entire array
• Multiple runs of equal maximum length at different positions
• Integer.MIN_VALUE or Integer.MAX_VALUE present (overflow risk in the subtraction)

Additional Considerations

The algorithm runs in O(n) time. Although there are two nested while loops, the outer loop always resumes from where the inner loop stopped with i = j, so no index is revisited more than once across the whole scan; the total work is linear in the size of nums.

Space usage is O(1) since the method only tracks a handful of integer variables regardless of input size. The one subtlety worth testing is overflow: if nums can contain values near Integer.MIN_VALUE or Integer.MAX_VALUE, the subtraction nums[i + 1] - nums[i] can overflow a 32-bit int, so for untrusted input ranges consider casting to long before subtracting.

Interview Follow-up Questions

An interviewer will often extend this problem once you have the base solution working.

• What if the array is empty or has one element? - return -1 immediately, since no subarray of length greater than one can exist.
• What if the numbers arrive as a stream of unknown length? - keep only the previous value, the current run's expectedDiff, and the running maxLen in memory, and update them as each new number arrives instead of storing the whole array.
• What if you need the start and end indices of the longest run, not just its length? - store bestStart and bestEnd alongside maxLen and update all three together whenever a longer run is found.
• What if the first step of the pattern could be either +1 or -1? - run the scan twice, once requiring the first difference to be +1 and once requiring -1, and return the larger of the two results.
• What if nums has billions of elements and must be processed across multiple machines? - split the array into contiguous chunks, run the scan on each chunk independently, then merge results at chunk boundaries by checking whether the run at the end of one chunk continues into the start of the next.

Conclusion

Finding the longest alternating subarray comes down to recognizing that each valid run has a strict signed pattern, and that a single forward pass with two pointers is enough to find the longest one in linear time. The trickiest parts are the sentinel return value of -1 and making sure the next candidate run starts at exactly the right index.

Try adapting this same two-pointer, pattern-matching approach to other array problems that ask for the longest run satisfying some condition, such as the longest strictly increasing subarray or the longest subarray with alternating parity. You can learn more about array-based interview problems like this one: https://dailyjavaconcept.com/category/arrays/