LeetCode 3350 - Adjacent Increasing Subarrays Detection II

The problem asks us to find the largest possible length k such that there exist two adjacent subarrays of length k in a given array nums, where both subarrays are strictly increasing.

leetcodemediumarraybinary-search

LeetCode Problem 3350

Difficulty: 🟡 Medium
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks us to find the largest possible length k such that there exist two adjacent subarrays of length k in a given array nums, where both subarrays are strictly increasing. In other words, we are looking for a situation where a sequence of k numbers increases consecutively, followed immediately by another sequence of k numbers that also increases consecutively. The output is the maximum k that satisfies this condition.

The input nums is a list of integers with length up to 2 * 10^5 and values ranging from -10^9 to 10^9. The constraints indicate that an O(n^2) approach is likely too slow, and we must aim for an O(n log n) or O(n) solution.

Edge cases to consider include arrays where all elements are equal, arrays where strictly increasing sequences barely exist, arrays with length exactly 2 (the minimum), and arrays with very large ranges.

Approaches

Brute Force

The brute-force solution would iterate over all possible values of k from 1 to n//2. For each k, we check all starting indices a from 0 to n - 2*k to see if both nums[a..a+k-1] and nums[a+k..a+2k-1] are strictly increasing.

This approach is correct but inefficient because for each k, we might scan up to 2*k elements for every starting index. In the worst case, this leads to O(n^2) time complexity, which is impractical for n = 2 * 10^5.

Optimal Approach

The key insight is that we can preprocess the array to quickly know the length of the strictly increasing subarray starting at each index. We define an array inc_len where inc_len[i] is the maximum length of the strictly increasing subarray starting at i. This array can be computed in O(n) by iterating backwards through nums.

Once we have inc_len, we can perform a binary search on k from 1 to n//2. For each candidate k, we check if there exists any index a such that inc_len[a] >= k and inc_len[a + k] >= k. If so, this k is feasible. Using binary search, we find the maximum feasible k efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all possible k and subarrays directly
Optimal O(n log n) O(n) Precompute strictly increasing subarray lengths and binary search over k

Algorithm Walkthrough

  1. Initialize an array inc_len of size n. Set inc_len[n-1] = 1 because a single element is trivially increasing.
  2. Iterate backward from i = n-2 to 0. For each i, if nums[i] < nums[i+1], then inc_len[i] = inc_len[i+1] + 1, otherwise inc_len[i] = 1. This step captures the length of the strictly increasing subarray starting at each index.
  3. Initialize binary search bounds low = 1 and high = n//2. We search for the maximum k.
  4. While low <= high, compute mid = (low + high) // 2. Check all starting indices a from 0 to n - 2*mid. If inc_len[a] >= mid and inc_len[a+mid] >= mid, then mid is feasible, and we can try a larger k. Otherwise, try smaller k.
  5. Continue binary search until convergence. Return the largest feasible k.

Why it works: The inc_len array guarantees that we know the maximum length of any strictly increasing subarray starting at each index. Binary search efficiently explores possible k values without checking all subarray lengths explicitly.

Python Solution

from typing import List

class Solution:
    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
        n = len(nums)
        inc_len = [1] * n
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                inc_len[i] = inc_len[i + 1] + 1

        low, high = 1, n // 2
        max_k = 0
        while low <= high:
            mid = (low + high) // 2
            found = False
            for i in range(n - 2 * mid + 1):
                if inc_len[i] >= mid and inc_len[i + mid] >= mid:
                    found = True
                    break
            if found:
                max_k = mid
                low = mid + 1
            else:
                high = mid - 1

        return max_k

Explanation: We first compute inc_len in reverse, ensuring each element stores the length of the strictly increasing subarray starting there. Then, we use binary search over k and check feasibility efficiently using inc_len.

Go Solution

func maxIncreasingSubarrays(nums []int) int {
    n := len(nums)
    incLen := make([]int, n)
    for i := range incLen {
        incLen[i] = 1
    }
    for i := n - 2; i >= 0; i-- {
        if nums[i] < nums[i+1] {
            incLen[i] = incLen[i+1] + 1
        }
    }

    low, high, maxK := 1, n/2, 0
    for low <= high {
        mid := (low + high) / 2
        found := false
        for i := 0; i <= n - 2*mid; i++ {
            if incLen[i] >= mid && incLen[i+mid] >= mid {
                found = true
                break
            }
        }
        if found {
            maxK = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return maxK
}

Go-specific notes: Slice initialization ensures all values start at 1. The reverse iteration logic is similar to Python. Integer division and indexing are carefully handled to avoid off-by-one errors.

Worked Examples

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

Compute inc_len:

i nums[i] inc_len[i]
9 1 1
8 3 1
7 4 2
6 3 3
5 2 3
4 9 1
3 8 2
2 7 3
1 5 4
0 2 2

Binary search for k finds k = 3 satisfies the condition at indices 2 and 5.

Example 2: nums = [1,2,3,4,4,4,4,5,6,7]

Compute inc_len similarly; binary search finds k = 2 feasible at indices 0 and 2.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) O(n) for inc_len computation, O(log n) binary search iterations, each checking O(n) indices
Space O(n) inc_len array stores length of strictly increasing subarrays

The complexity is optimal given constraints. Each subarray length check is reduced to O(1) per index using inc_len.

Test Cases

# Provided examples
assert Solution().maxIncreasingSubarrays([2,5,7,8,9,2,3,4,3,1]) == 3  # Example 1
assert Solution().maxIncreasingSubarrays([1,2,3,4,4,4,4,5,6,7]) == 2  # Example 2

# Boundary cases
assert Solution().maxIncreasingSubarrays([1,2]) == 1  # minimal array
assert Solution().maxIncreasingSubarrays([5,4]) == 0  # no increasing subarrays

# Larger sequences
assert Solution().maxIncreasingSubarrays([1,2,3,1,2,3,1,2,3]) == 3  # multiple repeated increasing sequences

# Constant array
assert Solution().maxIncreasingSubarrays([7,7,7,7]) == 0  # no strictly increasing pairs
Test Why
[2,5,7,8,9,2,3,4,3,1] Checks standard increasing sequences
`[1,2,3,4,4,4,4