Adjacent Increasing Subarrays Detection II

MEDIUM

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

Approaches

Checkout 4 different approaches to solve Adjacent Increasing Subarrays Detection II. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach involves checking every possible length k and every possible starting position a. For each combination, it verifies if the two adjacent subarrays of length k are strictly increasing.

Algorithm

Iterate through all possible lengths k from n/2 down to 1. The first k that satisfies the condition will be the maximum, so we can return it immediately.
For each k, iterate through all possible starting indices a for the first subarray, from 0 to n - 2k.
For each pair (k, a), define two subarrays: sub1 = nums[a...a+k-1] and sub2 = nums[a+k...a+2k-1].
Use a helper function isIncreasing(subarray) that checks if a given subarray is strictly increasing. This function iterates through the subarray and checks if sub[i] > sub[i-1] for all i.
If both sub1 and sub2 are strictly increasing, we have found our maximum k and can return it.
If the loops complete without finding a valid k, it means no such pair of subarrays exists, so we return 0.

The most straightforward method is to test every possibility. We can iterate through all potential lengths k, starting from the largest possible (n/2) down to 1. For each k, we check every possible starting position a. At each position, we form two adjacent subarrays of length k and check if both are strictly increasing. The first value of k for which we find such a pair of subarrays is the maximum possible k.

class Solution {
    private boolean isIncreasing(int[] nums, int start, int end) {
        for (int i = start + 1; i <= end; i++) {
            if (nums[i] <= nums[i - 1]) {
                return false;
            }
        }
        return true;
    }

    public int findMaximumK(int[] nums) {
        int n = nums.length;
        for (int k = n / 2; k >= 1; k--) {
            for (int a = 0; a <= n - 2 * k; a++) {
                // Check first subarray: nums[a...a+k-1]
                boolean firstOk = isIncreasing(nums, a, a + k - 1);
                // Check second subarray: nums[a+k...a+2k-1]
                boolean secondOk = isIncreasing(nums, a + k, a + 2 * k - 1);

                if (firstOk && secondOk) {
                    return k; // Found the largest k, return immediately
                }
            }
        }
        return 0;
    }
}

Complexity Analysis

Time Complexity: O(n^3). The outer loop for `k` runs up to `n/2` times. The middle loop for `a` runs up to `n` times. The check for each pair of subarrays takes `O(k)` time. In the worst case, this is `O(n * n * n)`.Space Complexity: O(1) extra space, as we are not using any auxiliary data structures that scale with the input size.

Pros and Cons

Pros:

Simple to understand and implement.
Uses constant extra space.

Cons:

Extremely inefficient and will result in a 'Time Limit Exceeded' error for large inputs.

Code Solutions

Checking out 3 solutions in different languages for Adjacent Increasing Subarrays Detection II. Click on different languages to view the code.

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;
  }
}

Video Solution

Watch the video walkthrough for Adjacent Increasing Subarrays Detection II

Algorithms:

Binary Search

Data Structures:

Array