3350. Adjacent Increasing Subarrays Detection II

Problem 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.

Intuition

The task is to determine the largest possible k for which two adjacent strictly increasing subarrays of length k can be formed. To tackle this, consider the following:

Traverse the Array: Iterate through nums to examine potential increasing sequences.
Track Lengths: Utilize two variables, cur and pre, to keep track of current and previous strictly increasing subarray lengths. Initialize both to zero at the start.
Check Strict Increase: For each element in the array, check if the current element forms a continuation of an increasing sequence compared to the next element. If an element is not part of a strictly increasing sequence, evaluate the possible k value using the smaller of pre and cur.
Calculate Maximum k: For any completed increasing sequence, attempt to update the maximum k by determining the maximum between the current known k and possible values based on completed sequences.
Move Sequence Forward: Once a strictly increasing sequence breaks, update pre to the value of cur and reset cur to start a new sequence check.

By iteratively updating these values, you can efficiently determine the largest k that allows for two adjacent strictly increasing subarrays.

Learn more about Binary Search patterns.

Solution Approach

The solution uses a single pass through the array nums to efficiently determine the maximum length k for which there exist two adjacent strictly increasing subarrays.

Initialize Variables:
- ans: To store the maximum value of k.
- pre: To store the length of the previous strictly increasing sequence.
- cur: To track the length of the current strictly increasing sequence.
Iterate Through the Array:
- Use a loop to traverse through each element x in nums using its index i.
Track Current Increasing Sequence:
- Increment cur for each element, as it is part of the current sequence.
- Check if the current element x is greater than or equal to the next one nums[i + 1]. This indicates the end of a strictly increasing sequence.
Update Maximum k:
- When the sequence ends, calculate potential k values:
  - cur // 2: Half of the current length can determine the k when both sequences are identical.
  - min(pre, cur): Minimum of the previous and current sequence lengths determines the largest possible adjacent subarray length.
- Update ans with the largest possible k from these calculations.
Prepare for Next Sequence:
- Assign cur value to pre and reset cur to zero, indicating a new sequence check.

This approach ensures that the algorithm runs in O(n) time complexity since it makes a single pass through the array, keeping track of necessary lengths and updating the maximum k efficiently using basic arithmetic and comparisons.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the array nums = [1, 2, 3, 1, 2, 3, 4]. We want to find the maximum value of k, where there are two adjacent strictly increasing subarrays of length k.

Initialize Variables:
- Set ans = 0 to store the maximum k.
- Set pre = 0 for the previous increasing sequence length.
- Set cur = 0 for the current increasing sequence length.
Iterate Through the Array:
- Start at index 0 (nums[i] = 1):
  - Increment cur to 1 since the sequence is starting.
  - nums[0] < nums[1], so continue the sequence (current sequence: [1, 2, 3]).
- At index 2 (nums[2] = 3):
  - nums[2] > nums[3] indicates the sequence is ending.
  - Calculate maximum k:
    - cur = 3, update ans using cur // 2 = 1 and min(pre, cur) = 0.
    - Update ans = 1.
  - Set pre = 3, reset cur = 0.
- Resume at index 3 (nums[3] = 1):
  - Increment cur to 1. Start new sequence.
  - Continue as nums[3] < nums[4] < nums[5] < nums[6] (current sequence: [1, 2, 3, 4]).
- At index 6 (nums[6] = 4):
  - End of array, complete sequence check.
  - Calculate maximum k:
    - cur = 4, update ans using cur // 2 = 2 and min(pre, cur) = 3.
    - Update ans to max(1, 2) = 2.

The largest possible k for two adjacent strictly increasing subarrays is 2. The subarrays are [1, 2] and [2, 3] starting at indices 2 and 3 respectively.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxIncreasingSubarrays(self, nums: List[int]) -> int:
5        # Initialize answer, previous segment length, and current segment length.
6        answer = previous_length = current_length = 0
7      
8        # Iterate over each element in the list with its index.
9        for index, num in enumerate(nums):
10            current_length += 1  # Increment the length of the current increasing subarray.
11          
12            # Check if the end of the list is reached or the current number is not less than the next number.
13            if index == len(nums) - 1 or num >= nums[index + 1]:
14                # Update the answer with the maximum of current answer, the half of current length,
15                # or the minimum of previous and current lengths.
16                answer = max(answer, current_length // 2, min(previous_length, current_length))
17              
18                # Update previous_length with current_length for the next iteration, reset current_length.
19                previous_length, current_length = current_length, 0
20      
21        return answer
22

1import java.util.List;
2
3class Solution {
4    public int maxIncreasingSubarrays(List<Integer> nums) {
5        int ans = 0; // Variable to store the maximum length of an increasing subarray
6        int previousLength = 0; // Length of the previous increasing subarray
7        int currentLength = 0; // Length of the current increasing subarray
8        int n = nums.size(); // Number of elements in the list
9      
10        // Iterate through the list of numbers
11        for (int i = 0; i < n; ++i) {
12            ++currentLength; // Increment the length of the current subarray
13          
14            // Check if the end of the list is reached or the current number is not smaller than the next one
15            if (i == n - 1 || nums.get(i) >= nums.get(i + 1)) {
16                // Update the maximum length found so far, comparing current, half of the current, and the previous lengths
17                ans = Math.max(ans, Math.max(currentLength / 2, Math.min(previousLength, currentLength)));
18              
19                // Update previousLength to be the currentLength for the next round
20                previousLength = currentLength;
21              
22                // Reset currentLength for a new potential subarray
23                currentLength = 0;
24            }
25        }
26      
27        return ans; // Return the maximum length of increasing subarrays found
28    }
29}
30

1class Solution {
2public:
3    int maxIncreasingSubarrays(vector<int>& nums) {
4        int ans = 0; // Initialize the variable to hold the maximum length 
5        int pre = 0; // Variable to store the length of the previous subarray
6        int cur = 0; // Variable to track the current subarray length
7        int n = nums.size(); // Get the size of the input vector
8
9        // Iterate through each element in the vector
10        for (int i = 0; i < n; ++i) {
11            ++cur; // Increment the current subarray length
12
13            // Check if it's the end of the vector or the next number is not greater
14            if (i == n - 1 || nums[i] >= nums[i + 1]) {
15                // Calculate maximum of ans, half of the current subarray, and minimum of previous and current subarrays
16                ans = max({ans, cur / 2, min(pre, cur)});
17                pre = cur; // Update pre to the current subarray length
18                cur = 0; // Reset cur for the next subarray
19            }
20        }
21      
22        return ans; // Return the maximum length found
23    }
24};
25

1function maxIncreasingSubarrays(nums: number[]): number {
2    // Initialize variables.
3    let [maxLength, previousLength, currentLength] = [0, 0, 0];
4    const n = nums.length;
5
6    // Iterate over the array to find increasing subarrays.
7    for (let i = 0; i < n; ++i) {
8        ++currentLength; // Increment current subarray length.
9      
10        // If the end of an increasing subarray is reached.
11        if (i === n - 1 || nums[i] >= nums[i + 1]) {
12            // Update the maximum length found so far.
13            maxLength = Math.max(maxLength, Math.floor(currentLength / 2), Math.min(previousLength, currentLength));
14            // Set previousLength to currentLength and reset currentLength to zero for new subarray.
15            [previousLength, currentLength] = [currentLength, 0];
16        }
17    }
18    return maxLength; // Return the maximum length of a valid increasing subarray.
19}
20

Time and Space Complexity

The code has a time complexity of O(n), where n is the length of the nums list. This is because each element in the nums list is processed exactly once in a single pass through the list.

The space complexity of the code is O(1) since only a constant amount of extra space is used, regardless of the input size. The variables ans, pre, cur, and loop index i consume constant space.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: