Skip to content

3350. Adjacent Increasing Subarrays Detection II

Description

Given an array nums of n integers, your task is to find the maximum value of k for which there exist two adjacent subarrays of length k each, such that both subarrays are strictly increasing. Specifically, check if there are two subarrays of length k starting at indices a and b (a < b), where:

  • Both subarrays nums[a..a + k - 1] and nums[b..b + k - 1] are strictly increasing.
  • The subarrays must be adjacent, meaning b = a + k.

Return the maximum possible value of k.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: nums = [2,5,7,8,9,2,3,4,3,1]

Output: 3

Explanation:

  • The subarray starting at index 2 is [7, 8, 9], which is strictly increasing.
  • The subarray starting at index 5 is [2, 3, 4], which is also strictly increasing.
  • These two subarrays are adjacent, and 3 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

Example 2:

Input: nums = [1,2,3,4,4,4,4,5,6,7]

Output: 2

Explanation:

  • The subarray starting at index 0 is [1, 2], which is strictly increasing.
  • The subarray starting at index 2 is [3, 4], which is also strictly increasing.
  • These two subarrays are adjacent, and 2 is the maximum possible value of k for which two such adjacent strictly increasing subarrays exist.

 

Constraints:

  • 2 <= nums.length <= 2 * 105
  • -109 <= nums[i] <= 109

Solutions

Solution 1: Single Pass

We can use a single pass to calculate the maximum length of adjacent increasing subarrays \(\textit{ans}\). Specifically, we maintain three variables: \(\textit{cur}\) and \(\textit{pre}\) represent the length of the current increasing subarray and the previous increasing subarray respectively, while \(\textit{ans}\) represents the maximum length of adjacent increasing subarrays.

Whenever we encounter a non-increasing position, we update \(\textit{ans}\), assign \(\textit{cur}\) to \(\textit{pre}\), and reset \(\textit{cur}\) to \(0\). The update formula for \(\textit{ans}\) is \(\textit{ans} = \max(\textit{ans}, \lfloor \frac{\textit{cur}}{2} \rfloor, \min(\textit{pre}, \textit{cur}))\), meaning the adjacent increasing subarrays come from either half the length of the current increasing subarray, or the smaller value between the previous increasing subarray and the current increasing subarray.

Finally, we just need to return \(\textit{ans}\).

The time complexity is \(O(n)\), where \(n\) is the length of the array. The space complexity is \(O(1)\).

1
2
3
4
5
6
7
8
9
class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        ans = pre = cur = 0
        for i, x in enumerate(nums):
            cur += 1
            if i == len(nums) - 1 or x >= nums[i + 1]:
                ans = max(ans, cur // 2, min(pre, cur))
                pre, cur = cur, 0
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int ans = 0, pre = 0, cur = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            ++cur;
            if (i == n - 1 || nums.get(i) >= nums.get(i + 1)) {
                ans = Math.max(ans, Math.max(cur / 2, Math.min(pre, cur)));
                pre = cur;
                cur = 0;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        int ans = 0, pre = 0, cur = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            ++cur;
            if (i == n - 1 || nums[i] >= nums[i + 1]) {
                ans = max({ans, cur / 2, min(pre, cur)});
                pre = cur;
                cur = 0;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
func maxIncreasingSubarrays(nums []int) (ans int) {
    pre, cur := 0, 0
    for i, x := range nums {
        cur++
        if i == len(nums)-1 || x >= nums[i+1] {
            ans = max(ans, max(cur/2, min(pre, cur)))
            pre, cur = cur, 0
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function maxIncreasingSubarrays(nums: number[]): number {
    let [ans, pre, cur] = [0, 0, 0];
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        ++cur;
        if (i === n - 1 || nums[i] >= nums[i + 1]) {
            ans = Math.max(ans, (cur / 2) | 0, Math.min(pre, cur));
            [pre, cur] = [cur, 0];
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn max_increasing_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let (mut ans, mut pre, mut cur) = (0, 0, 0);

        for i in 0..n {
            cur += 1;
            if i == n - 1 || nums[i] >= nums[i + 1] {
                ans = ans.max(cur / 2).max(pre.min(cur));
                pre = cur;
                cur = 0;
            }
        }

        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxIncreasingSubarrays = function (nums) {
    let [ans, pre, cur] = [0, 0, 0];
    const n = nums.length;
    for (let i = 0; i < n; ++i) {
        ++cur;
        if (i === n - 1 || nums[i] >= nums[i + 1]) {
            ans = Math.max(ans, cur >> 1, Math.min(pre, cur));
            [pre, cur] = [cur, 0];
        }
    }
    return ans;
};

Comments