Adjacent Increasing Subarrays Detection II

Medium
1846.

Adjacent Increasing Subarrays Detection II

Adjacent Increasing Subarrays Detection II is a medium coding problem on arrays and binary search, asked in Amazon and Google interviews.

Given an array nums of length n, find the largest k for which there exist two adjacent subarrays of length k that are both strictly increasing — that is, an index a such that nums[a..a + k - 1] and nums[a + k..a + 2k - 1] are both strictly increasing.

Return that maximum k. Since n >= 2, k = 1 always works.

Example 1

Input
nums = [2,5,7,8,9,2,3,4,3,1]
Output
3
Explanation
[7,8,9] and [2,3,4] are adjacent and increasing; no `k = 4` pair exists.

Example 2

Input
nums = [1,2,3,4,4,4,4,5,6,7]
Output
2
Explanation
Inside the run [1,2,3,4] the windows [1,2] and [3,4] work; the run [4,5,6,7] gives the same.

Example 3

Input
nums = [5,4]
Output
1

Constraints

  • 2 <= nums.length <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxIncreasingSubarrays = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Adjacent Increasing Subarrays Detection II — Solution

Adjacent Increasing Subarrays Detection II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Adjacent Increasing Subarrays Detection II is a medium coding problem on arrays and binary search, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Binary Search
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array nums of length n, find the largest k for which there exist two adjacent subarrays of length k that are both strictly increasing — that is, an index a such that nums[a..a + k - 1] and nums[a + k..a + 2k - 1] are both strictly increasing.

Return that maximum k. Since n >= 2, k = 1 always works.

Example 1

Input: nums = [2,5,7,8,9,2,3,4,3,1]
Output: 3
Explanation: [7,8,9] and [2,3,4] are adjacent and increasing; no `k = 4` pair exists.

Example 2

Input: nums = [1,2,3,4,4,4,4,5,6,7]
Output: 2
Explanation: Inside the run [1,2,3,4] the windows [1,2] and [3,4] work; the run [4,5,6,7] gives the same.

Example 3

Input: nums = [5,4]
Output: 1

Constraints

  • 2 <= nums.length <= 2 * 10^5
  • -10^9 <= nums[i] <= 10^9

Hints for Adjacent Increasing Subarrays Detection II

  1. Hint 1

    Split the array into maximal strictly increasing runs. The two windows either both fit in one run, or meet exactly at the boundary of two consecutive runs.

  2. Hint 2

    Inside one run of length L, the best is floor(L / 2). Across consecutive runs of lengths p and c, the best is min(p, c).

  3. Hint 3

    Keep the previous run length and the current one as you scan; update the answer with both formulas at every index.

How to solve Adjacent Increasing Subarrays Detection II

The answer is the best over two shapes: both windows inside one maximal increasing run (floor(L / 2)), or the first window ending one run and the second starting the next (min(prev, cur)). One left-to-right scan with two run lengths evaluates both.

Approach

  1. Set prev = 0, cur = 1, best = 0.
  2. For i = 1 .. n - 1: if nums[i] > nums[i - 1] extend cur; otherwise prev = cur, cur = 1.
  3. Update best = max(best, cur / 2, min(prev, cur)).
  4. Return best.

Why it works

Take an optimal pair of windows. If no run break falls strictly inside the span [a, a + 2k - 1], both lie in one run of length at least 2k, caught by cur / 2. Otherwise the only break can be between the windows (each window is itself increasing), so the first is a suffix of one run and the second a prefix of the next, caught by min(prev, cur) when cur reaches that run's length. Conversely, every value the formulas produce is achievable, so the maximum is exact.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • A binary search over k with an O(n) check also works, but is unnecessary — and the check must still handle both shapes.
  • Equal elements break a run (strictly increasing).

Reference solution

Python

from typing import List

def maxIncreasingSubarrays(nums: List[int]) -> int:
    prev, cur, best = 0, 1, 0
    for i in range(1, len(nums)):
        if nums[i] > nums[i - 1]:
            cur += 1
        else:
            prev, cur = cur, 1
        best = max(best, cur // 2, min(prev, cur))
    return best

Java

public static int maxIncreasingSubarrays(int[] nums) {
    int prev = 0, cur = 1, best = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) cur++;
        else { prev = cur; cur = 1; }
        best = Math.max(best, Math.max(cur / 2, Math.min(prev, cur)));
    }
    return best;
}

C++

int maxIncreasingSubarrays(vector<int>& nums) {
    int prev = 0, cur = 1, best = 0;
    for (size_t i = 1; i < nums.size(); i++) {
        if (nums[i] > nums[i - 1]) cur++;
        else { prev = cur; cur = 1; }
        best = max(best, max(cur / 2, min(prev, cur)));
    }
    return best;
}

JavaScript

var maxIncreasingSubarrays = function(nums) {
    var prev = 0, cur = 1, best = 0;
    for (var i = 1; i < nums.length; i++) {
        if (nums[i] > nums[i - 1]) cur++;
        else { prev = cur; cur = 1; }
        best = Math.max(best, Math.floor(cur / 2), Math.min(prev, cur));
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Binary Search