3619. Adjacent Increasing Subarrays Detection Ii¶

3619. Adjacent Increasing Subarrays Detection II

Medium

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 * 10⁵
-10⁹ <= nums[i] <= 10⁹

Solution¶

class Solution {
    public int maxIncreasingSubarrays(List<Integer> nums) {
        int n = nums.size();
        int isincreasing[] = new int[n];
        Arrays.fill(isincreasing, 1);
        for (int i = n - 2; i >= 0; i--) {
            if (nums.get(i) < nums.get(i + 1)) isincreasing[i] = isincreasing[i + 1] + 1;
        }
        int low = 0;
        int high = n / 2 + 1;
        int ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            boolean flag = false;
            for (int i = 0; i + 2 * mid <= n; i++) {
                if (isincreasing[i] >= mid && isincreasing[i + mid] >= mid) {
                    flag = true;
                    break;
                }
            }
            if (flag == true) {
                ans = mid;
                low = mid + 1;
            }
            else high = mid - 1;
        }
        return ans;
    }

    private boolean check(List<Integer> nums, int start, int end, int k) {
        int n = nums.size();
        int prev = -2000;        
        for (int i = start; i < start + k; i++) {
            if (prev == -2000) {
                prev = nums.get(i);
            }
            else {
                if (nums.get(i) <= prev) return false;
                prev = nums.get(i);
            }
        }
        prev = -2000;
        for (int i = start + k; i < end; i++) {
            if (prev == -2000) {
                prev = nums.get(i);
            }
            else {
                if (nums.get(i) <= prev) return false;
                prev = nums.get(i);
            }
        }
        return true;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Explanation¶

[Add detailed explanation here]