Problem

Given an array of numbers, find the length of the longest contiguous subarray such that every element in the subarray is strictly greater than its previous element. The solution should run in O(n) time.

Examples

Example 1

1
2
3
4
5
6

Input:
nums = [5, 6, 3, 5, 7, 8, 9, 1, 2]
Output:
5
Explanation:
The longest increasing subarray is [3, 5, 7, 8, 9].

Example 2

1
2
3
4
5
6

Input:
nums = [12, 13, 1, 5, 4, 7, 8, 10, 10, 11]
Output:
4
Explanation:
The longest increasing subarray is [4, 7, 8, 10].

Solution

Also, this question is similar to Subarray With Given Sum. In this post, I’m going to cover topics like “sliding window”, dynamic programming, time/space complexity and so on.

Also, don’t confuse subarray with subsequence. Here is similar problem - Longest Increasing Subsequence.

Method 1 – Brute Force

The most straightforward approach is to examine every possible subarray and determine if it is strictly increasing. For each starting index, we check all possible ending indices and keep track of the longest increasing subarray found. While this method is simple and does not require extra memory, it is inefficient for large arrays.

Complexity

  • ⏰ Time complexity: O(n^2) — For each element, we may need to check all subsequent elements, resulting in a quadratic number of checks.
  • 🧺 Space complexity: O(1) — No extra space is needed beyond a few variables for tracking lengths and indices.

Method 2 – Single Pass Linear Scan

Intuition

Instead of checking all possible subarrays, we can scan the array once and keep track of the length of the current increasing subarray. Whenever the sequence breaks, we reset the length counter. This way, we efficiently find the longest increasing subarray in a single pass.

Approach

  1. Initialize two variables: ans for the maximum length found and len for the current increasing subarray length.
  2. Iterate through the array from the second element:
    • If the current element is greater than the previous, increment len.
    • Otherwise, update ans if len is greater, and reset len to 1.
  3. After the loop, update ans one last time in case the longest subarray ends at the last element.
  4. Return ans as the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int longestIncreasingSubarray(vector<int>& nums) {
        int ans = 1, len = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] > nums[i-1]) len++;
            else {
                ans = max(ans, len);
                len = 1;
            }
        }
        return max(ans, len);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func longestIncreasingSubarray(nums []int) int {
    ans, len := 1, 1
    for i := 1; i < len(nums); i++ {
        if nums[i] > nums[i-1] {
            len++
        } else {
            if len > ans {
                ans = len
            }
            len = 1
        }
    }
    if len > ans {
        ans = len
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int longestIncreasingSubarray(int[] nums) {
        int ans = 1, len = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) len++;
            else {
                ans = Math.max(ans, len);
                len = 1;
            }
        }
        return Math.max(ans, len);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun longestIncreasingSubarray(nums: IntArray): Int {
        var ans = 1
        var len = 1
        for (i in 1 until nums.size) {
            if (nums[i] > nums[i-1]) len++
            else {
                ans = maxOf(ans, len)
                len = 1
            }
        }
        return maxOf(ans, len)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def longest_increasing_subarray(nums: list[int]) -> int:
    ans = 1
    len_ = 1
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            len_ += 1
        else:
            ans = max(ans, len_)
            len_ = 1
    return max(ans, len_)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn longest_increasing_subarray(nums: Vec<i32>) -> i32 {
        let mut ans = 1;
        let mut len = 1;
        for i in 1..nums.len() {
            if nums[i] > nums[i-1] {
                len += 1;
            } else {
                ans = ans.max(len);
                len = 1;
            }
        }
        ans.max(len)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    longestIncreasingSubarray(nums: number[]): number {
        let ans = 1, len = 1;
        for (let i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i-1]) len++;
            else {
                ans = Math.max(ans, len);
                len = 1;
            }
        }
        return Math.max(ans, len);
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once, updating counters as we go.
  • 🧺 Space complexity: O(1) — Only a few variables are used for tracking lengths.

Method 3 – Sliding Window

Intuition

Instead of checking every possible subarray, we can use a sliding window to efficiently track the longest increasing segment. By maintaining two pointers, we expand the window as long as the sequence is increasing, and reset the window when the sequence breaks. This approach ensures we only scan the array once and always keep track of the longest valid window.

Approach

  1. Handle edge cases: if the array is empty, return 0; if it has one element, return 1.
  2. Initialize two pointers, start and end, to mark the current window, and a variable max_len to store the maximum length found.
  3. Iterate through the array:
    • If the current element is greater than the previous, expand the window and update max_len if needed.
    • If not, move start to the current position to begin a new window.
  4. Continue until the end of the array and return max_len.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int longestIncreasingSubarray(vector<int>& nums) {
        if (nums.empty()) return 0;
        int start = 0, max_len = 1;
        for (int end = 1; end < nums.size(); ++end) {
            if (nums[end] > nums[end-1]) {
                max_len = max(max_len, end - start + 1);
            } else {
                start = end;
            }
        }
        return max_len;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func longestIncreasingSubarray(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    start, maxLen := 0, 1
    for end := 1; end < len(nums); end++ {
        if nums[end] > nums[end-1] {
            if end-start+1 > maxLen {
                maxLen = end-start+1
            }
        } else {
            start = end
        }
    }
    return maxLen
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int longestIncreasingSubarray(int[] nums) {
        if (nums.length == 0) return 0;
        int start = 0, maxLen = 1;
        for (int end = 1; end < nums.length; end++) {
            if (nums[end] > nums[end-1]) {
                maxLen = Math.max(maxLen, end - start + 1);
            } else {
                start = end;
            }
        }
        return maxLen;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun longestIncreasingSubarray(nums: IntArray): Int {
        if (nums.isEmpty()) return 0
        var start = 0
        var maxLen = 1
        for (end in 1 until nums.size) {
            if (nums[end] > nums[end-1]) {
                maxLen = maxOf(maxLen, end - start + 1)
            } else {
                start = end
            }
        }
        return maxLen
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def longest_increasing_subarray(nums: list[int]) -> int:
    if not nums:
        return 0
    if len(nums) == 1:
        return 1
    start = 0
    max_len = 1
    for end in range(1, len(nums)):
        if nums[end] > nums[end - 1]:
            max_len = max(max_len, end - start + 1)
        else:
            start = end
    return max_len
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn longest_increasing_subarray(nums: Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }
        let mut start = 0;
        let mut max_len = 1;
        for end in 1..nums.len() {
            if nums[end] > nums[end - 1] {
                max_len = max_len.max((end - start + 1) as i32);
            } else {
                start = end;
            }
        }
        max_len
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    longestIncreasingSubarray(nums: number[]): number {
        if (nums.length === 0) return 0;
        let start = 0, maxLen = 1;
        for (let end = 1; end < nums.length; end++) {
            if (nums[end] > nums[end-1]) {
                maxLen = Math.max(maxLen, end - start + 1);
            } else {
                start = end;
            }
        }
        return maxLen;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — We scan the array once, updating pointers and the maximum length.
  • 🧺 Space complexity: O(1) — Only a few variables are used for tracking indices and lengths.