Find Longest Increasing Subarray

Title: Find Longest Increasing Subarray

In this guide, you’ll learn how to find the longest increasing subarray in an array of integers using Java. Unlike the classic Longest Increasing Subsequence problem, the elements here must be contiguous, which makes a simple single pass through the array sufficient.

We’ll walk through the algorithm step by step, trace it on a sample input, and then cover the common mistakes, edge cases, and interview follow-up questions that come up when candidates are asked to solve this on a whiteboard.

Understanding the Problem

A longest increasing subarray is the longest run of consecutive elements in an array where each element is strictly greater than the one before it. For example, in [5, 6, 3, 5, 7, 8, 2, 4, 9], the subarray [3, 5, 7, 8] is the longest increasing run, with a length of 4.

The key word is subarray, not subsequence. A subarray must occupy consecutive positions in the original array, so you cannot skip elements. That constraint is what makes this problem solvable in O(n) time with a single pass, while the subsequence version needs dynamic programming.

Approach and Algorithm Steps

1. Handle the trivial case first: if the array is null or empty, throw an IllegalArgumentException since there is no subarray to return.
2. Initialize currentLength and maxLength to 1, since a single element is always an increasing subarray of length 1.
3. Initialize currentStart and maxStart to 0 to track where the current run and the best run found so far begin.
4. Iterate from index 1 to the end of the array, comparing each element nums[i] to its predecessor nums[i - 1].
5. If nums[i] > nums[i - 1], the run continues, so increment currentLength.
6. Otherwise the run breaks, so reset currentLength to 1 and move currentStart to the current index.
7. After updating the current run, compare currentLength to maxLength; if it is larger, update maxLength and maxStart.
8. Once the loop finishes, use maxStart and maxLength to extract and return the longest increasing subarray.

Java Program

import java.util.Arrays;

public class LongestIncreasingSubarray {

    public static int[] findLongestIncreasingSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Input array must not be null or empty");
        }

        int maxLength = 1;
        int maxStart = 0;
        int currentLength = 1;
        int currentStart = 0;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                currentLength++;
            } else {
                currentLength = 1;
                currentStart = i;
            }

            if (currentLength > maxLength) {
                maxLength = currentLength;
                maxStart = currentStart;
            }
        }

        return Arrays.copyOfRange(nums, maxStart, maxStart + maxLength);
    }

    public static void main(String[] args) {
        int[] nums = {5, 6, 3, 5, 7, 8, 2, 4, 9};
        int[] longestSubarray = findLongestIncreasingSubarray(nums);

        System.out.println("Length of the longest increasing subarray: " + longestSubarray.length);
        System.out.println("Longest increasing subarray: " + Arrays.toString(longestSubarray));
    }
}

Explanation of the Program

The method findLongestIncreasingSubarray keeps two running pairs of variables: currentLength and currentStart for the run ending at the current index, and maxLength and maxStart for the best run seen anywhere so far.

Inside the loop, the comparison nums[i] > nums[i - 1] decides whether the run continues or breaks. When it breaks, currentStart jumps to i because any new run can only start there.

Whenever currentLength exceeds maxLength, the method records both the new best length and where that run started. This way the final maxStart always points to the beginning of the longest run, even if several equally long runs are found.

Arrays.copyOfRange(nums, maxStart, maxStart + maxLength) then slices out the actual subarray, and main prints both its length and its contents.

Step-by-Step Trace

Let’s trace the algorithm on [1, 2, 2, 3, 4, 1, 5], where the longest increasing subarray is [2, 3, 4] with length 3.

At the end of iteration i, currentLength holds the length of the increasing run ending at index i, and maxLength holds the longest such run seen anywhere in nums[0..i].

Examples

Example 1: Already Sorted Array

int[] nums = {1, 2, 3, 4, 5};
// Longest increasing subarray: [1, 2, 3, 4, 5], length 5

Example 2: Strictly Decreasing Array

int[] nums = {9, 8, 7, 6, 5};
// Longest increasing subarray: [9], length 1

Example 3: Negative Numbers and Duplicates

int[] nums = {-3, -1, -1, 0, 2, 2, 5};
// Longest increasing subarray: [-1, 0, 2], length 3

Common Mistakes to Avoid

These are the mistakes candidates most often make when solving this problem under interview pressure.

• Using >= instead of > – treating equal neighboring elements as part of the increasing run, which returns a length of 3 for [2, 2, 2] instead of the correct answer of 1. Use strict > unless the problem explicitly asks for non-decreasing runs.
• Forgetting to reset currentLength – letting currentLength keep growing across a break in the sequence, which silently returns a length longer than any real run in the array. Reset it to 1 every time nums[i] <= nums[i - 1].
• Forgetting to move currentStart on a reset – resetting currentLength but leaving currentStart pointing at the old run, which produces a subarray that is the right length but starts at the wrong index. Set currentStart = i in the same branch that resets the length.
• Starting the loop at i = 0 – comparing nums[0] to nums[-1], which throws an ArrayIndexOutOfBoundsException. Start the loop at i = 1 since the first element has no predecessor to compare against.
• Confusing it with Longest Increasing Subsequence – reaching for an O(n log n) or O(n^2) dynamic programming solution because the problem sounds like LIS. Remember a subarray must be contiguous, so a single O(n) pass is enough.

Edge Cases to Test

Walk through these inputs out loud before you call the problem solved. Interviewers specifically look for this habit.

• Empty array
• Single-element array
• Already fully increasing array
• Strictly decreasing array
• All identical elements
• Increasing run at the very end of the array
• Negative numbers mixed with positive numbers
• Multiple runs tied for the maximum length

Additional Considerations

The single-pass solution runs in O(n) time since it visits each element exactly once, and it uses O(1) extra space beyond the handful of tracking variables. The only additional allocation is the Arrays.copyOfRange call at the end, which costs O(k) time and space where k is the length of the longest run.

Contrast this with the Longest Increasing Subsequence problem, where elements do not need to be contiguous. That version requires O(n^2) dynamic programming, or O(n log n) with binary search over a tails array, because any earlier element can potentially extend any later one.

If multiple runs tie for the longest length, this implementation returns the first one encountered, since it only updates maxStart when currentLength strictly exceeds maxLength. Switch the comparison to >= if you want the last tying run instead.

Interview Follow-up Questions

Once the base solution is working, interviewers often probe how well you understand the trade-offs behind it.

• What if the array should allow non-decreasing runs instead of strictly increasing ones? – change the comparison from nums[i] > nums[i - 1] to nums[i] >= nums[i - 1], which also changes how runs of equal elements are counted.
• What if you must solve it with O(1) extra space and cannot allocate a new array for the result? – return only maxStart and maxLength as a pair of integers instead of calling Arrays.copyOfRange, since the scan itself never needed more than a few tracking variables.
• What if the array is circular, so a run can wrap from the last element to the first? – conceptually append the array to itself, cap the scan length at 2 * n - 1, and cap any run length at n so you never count an element twice.
• What if you need the longest increasing run in a 2D grid, along rows or columns? – run the same single-pass scan independently along each row and each column, keeping a single global maxLength across all of them.
• What if the array arrives as a stream and you cannot see the whole input at once? – keep only nums[i - 1], currentLength, and maxLength in memory, updating them as each new element arrives; the algorithm never needed random access to earlier elements.

Conclusion

Finding the longest increasing subarray is a great warm-up problem because it looks like Longest Increasing Subsequence but solves in linear time once you notice the contiguity constraint. The core idea, tracking a current run and a best run side by side, shows up again in many sliding-window style problems.

Try adapting the code in this guide to return non-decreasing runs instead, or to work on a List<Integer> instead of an int[], to make sure the logic has really sunk in. You can learn more about array-based problems in our Arrays category.