3350. Adjacent Increasing Subarrays Detection II

[mah-shamim]

Topics: Array, Binary Search, Weekly Contest 423

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⁹

Hint:

1. Find the boundaries between strictly increasing subarrays.
2. Can we use binary search?

Footnotes

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

[mah-shamim]

We need to find the maximum length k where there exist two adjacent strictly increasing subarrays of length k in the given array.

Let me break down the approach:

1. Understanding the problem: I need to find two subarrays of length k that are:

   • Both strictly increasing
   • Adjacent (the second starts right after the first ends)
   • And I need the maximum possible k

2. Key Insight:

   • I can precompute for each position, the length of the increasing sequence starting at that position
   • Then for each possible starting position, I can check if it can form two adjacent increasing subarrays

3. Optimization:

   • Use binary search to find the maximum k efficiently
   • Precompute increasing sequence lengths to quickly validate potential k values

Let's implement this solution in PHP: 3350. Adjacent Increasing Subarrays Detection II

<?php
/**
 * @param Integer[] $nums
 * @return Integer
 */
function maxIncreasingSubarrays($nums) {
    $n = count($nums);

    // Precompute the length of increasing sequence starting at each position
    $inc = array_fill(0, $n, 1);
    for ($i = $n - 2; $i >= 0; $i--) {
        if ($nums[$i] < $nums[$i + 1]) {
            $inc[$i] = $inc[$i + 1] + 1;
        } else {
            $inc[$i] = 1;
        }
    }

    // Binary search for maximum k
    $left = 1;
    $right = intval($n / 2);
    $answer = 0;

    while ($left <= $right) {
        $mid = intval(($left + $right) / 2);

        if (isValid($nums, $inc, $mid, $n)) {
            $answer = $mid;
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return $answer;
}


/**
 * Check if there exists two adjacent increasing subarrays of length k
 *
 * @param $nums
 * @param $inc
 * @param $k
 * @param $n
 * @return bool
 */
function isValid($nums, $inc, $k, $n) {
    // We need to find position i where both [i, i+k-1] and [i+k, i+2k-1] are increasing
    for ($i = 0; $i <= $n - 2 * $k; $i++) {
        // Check if first subarray is increasing
        if ($inc[$i] >= $k) {
            // Check if second subarray is increasing
            if ($inc[$i + $k] >= $k) {
                return true;
            }
        }
    }
    return false;
}

// Test cases
// Example 1
$nums1 = [2,5,7,8,9,2,3,4,3,1];
echo maxIncreasingSubarrays($nums1) . "\n"; // Output: 3

// Example 2
$nums2 = [1,2,3,4,4,4,4,5,6,7];
echo maxIncreasingSubarrays($nums2) . "\n"; // Output: 2
?>

Explanation:

1. Precomputation: The $inc array stores for each position i, the length of the strictly increasing sequence starting at i. This is computed by scanning from right to left.

2. Binary Search: I use binary search to find the maximum k between 1 and n/2 (since we need two subarrays).

3. Validation: For each candidate k, I check if there exists a position i where both subarrays [i, i+k-1] and [i+k, i+2k-1] are strictly increasing by verifying that inc[i] >= k and inc[i+k] >= k.

Time Complexity: O(n log n)

• Precomputation: O(n)
• Binary search with validation: O(log n) × O(n) = O(n log n)

Space Complexity: O(n) for the $inc array

The solution efficiently finds the maximum k by leveraging binary search and precomputed increasing sequence lengths, making it suitable for large input sizes up to 2×10⁵.

[kovatz]

Thanks for solving the problem of "Adjacent Increasing Subarrays Detection II"

[mah-shamim]

Thanks