Adjacent Increasing Subarrays Detection II

Adjacent Increasing Subarrays Detection II - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: We can find two adjacent subarrays [2,3,4] and [3] where both are strictly increasing, but the maximum length is 3 with subarrays [5,7,8] and [8,9] (not adjacent). Actually, [2,3,4] at index 5-7 is increasing, but we need adjacent pairs. The answer is 1 as we can find adjacent increasing subarrays of length 1.

Example 2 — No Adjacent Pairs

$ Input: nums = [1,2,3,2,1]

› Output: 0

💡 Note: No two adjacent subarrays can both be strictly increasing since the array has decreasing parts that prevent valid adjacent pairs.

Example 3 — Small Array

$ Input: nums = [1,2]

› Output: 0

💡 Note: Array is too small to have two adjacent subarrays of any positive length.

Constraints

2 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with potential increasing subsequences

Find Adjacent Pairs

Look for adjacent subarrays that are both strictly increasing

Return Maximum k

Find the largest possible length k

Key Takeaway

🎯 Key Insight: Precompute increasing run lengths to efficiently find the maximum k

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to precompute the length of increasing runs starting from each position, then use binary search to find the maximum k. The optimal approach has Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Try all possible lengths k and check if adjacent increasing subarrays exist
Precompute Increasing Lengths	O(n²)	O(n)	Precompute the length of increasing sequence starting at each position
Binary Search on Answer	O(n log n)	O(n)	Binary search on the answer k with efficient feasibility checking

Brute Force — Algorithm Steps

Step 1: Try each possible length k from 1 to n/2
Step 2: For each k, check all positions for adjacent increasing subarrays
Step 3: Return the maximum k found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try k=1

Check all positions for adjacent increasing subarrays of length 1

Try k=2

Check all positions for adjacent increasing subarrays of length 2

Find Maximum

Return the largest k that works

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int* nums, int n) {
    int maxK = 0;
    
    // Try all possible lengths k
    for (int k = 1; k <= n / 2; k++) {
        // Check all positions where we can place two adjacent subarrays
        for (int i = 0; i <= n - 2 * k; i++) {
            // Check if first subarray is strictly increasing
            bool firstIncreasing = true;
            for (int j = i; j < i + k - 1; j++) {
                if (nums[j] >= nums[j + 1]) {
                    firstIncreasing = false;
                    break;
                }
            }
            
            if (!firstIncreasing) continue;
            
            // Check if second subarray is strictly increasing
            bool secondIncreasing = true;
            for (int j = i + k; j < i + 2 * k - 1; j++) {
                if (nums[j] >= nums[j + 1]) {
                    secondIncreasing = false;
                    break;
                }
            }
            
            if (secondIncreasing) {
                maxK = k;
                break;
            }
        }
    }
    
    return maxK;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: k values × positions × checking increasing property

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

8.5K Views

Medium Frequency

~25 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler