When I first encountered this problem on LeetCode, I did what most developers do - jumped straight to the naive solution. What followed was a journey through increasingly elegant optimizations, each revealing deeper insights about algorithmic thinking. This documents that evolution from a working-but-slow O(n³) solution to an optimal O(n) algorithm.

the problem

Given an array of integers, find the maximum value of k for which there exist two adjacent subarrays of length k each, where both subarrays are strictly increasing.

Constraints:

  • Both subarrays must be strictly increasing
  • The subarrays must be adjacent
  • Array length can be up to 200,000 elements

Example:

nums = [2,5,7,8,9,2,3,4,3,1] output = 3  The subarray [7,8,9] is strictly increasing The subarray [2,3,4] is strictly increasing They are adjacent, and k=3 is the maximum

the naive approach

The straightforward solution: try every possible value of k, check every possible window, and verify if both halves are increasing.

class Solution { public:     bool isStrictlyIncreasing(vector<int>& nums, int start, int length) {         for (int i = start + 1; i < start + length; i++) {             if (nums[i] <= nums[i-1]) return false;         }         return true;     }      int maxIncreasingSubarrays(vector<int>& nums) {         int n = nums.size();          for (int k = n/2; k >= 1; k--) {             for (int i = 0; i <= n - 2*k; i++) {                 if (isStrictlyIncreasing(nums, i, k) &&                     isStrictlyIncreasing(nums, i + k, k)) {                     return k;                 }             }         }         return 0;     } };

Time complexity: O(n² × k) ≈ O(n³) Space complexity: O(1)

With n = 200,000, this times out immediately.

first optimization: precomputation

The naive solution repeatedly checks if subarrays are increasing. The key insight: precompute how long each increasing sequence is.

run length array

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

At index 4, runLength[4] = 5 means there's an increasing sequence of length 5 ending at position 4.

class Solution { public:     int maxIncreasingSubarrays(vector<int>& nums) {         int n = nums.size();         vector<int> runLength(n, 1);          for (int i = 1; i < n; i++) {             if (nums[i] > nums[i-1]) {                 runLength[i] = runLength[i-1] + 1;             }         }          int maxK = 0;         for (int i = 0; i < n - 1; i++) {             for (int k = 1; k <= (n - i) / 2; k++) {                 if (runLength[i + k - 1] >= k &&                     runLength[i + 2*k - 1] >= k) {                     maxK = max(maxK, k);                 }             }         }          return maxK;     } };

Time complexity: O(n²) Space complexity: O(n)

Better, but still quadratic. With n = 200,000, we're at 40 billion operations.

the optimal solution

The breakthrough: at any point in the array, there are exactly two ways to form adjacent increasing subarrays.

scenario 1: bridge two separate runs

Previous Run          Current Run [...........] [break] [...........]    length=A              length=B  maximum k = min(A, B)

scenario 2: split a single run

One Long Run [........................]         length=L  maximum k = L / 2

the algorithm

class Solution { public:     int maxIncreasingSubarrays(vector<int>& nums) {         int n = nums.size();          int currentRunLength = 1;         int previousRunLength = 0;         int maxK = 0;          for (int i = 1; i < n; i++) {             if (nums[i] > nums[i - 1]) {                 currentRunLength++;             } else {                 previousRunLength = currentRunLength;                 currentRunLength = 1;             }              int kFromTwoRuns = min(previousRunLength, currentRunLength);             int kFromSplittingRun = currentRunLength / 2;              maxK = max({maxK, kFromTwoRuns, kFromSplittingRun});         }          return maxK;     } };

Time complexity: O(n) Space complexity: O(1)

Single pass, constant space.

the visualization

split run example | bridge runs example

current state

position 0
current run 1
previous run 0

maximum k

0

what's happening

click next step to begin

algorithm complete

complexity comparison

approach time space
naive O(n³) O(1)
precomputation O(n²) O(n)
optimal O(n) O(1)

lessons learned

start simple - The naive solution helped understand the problem deeply.

precomputation is powerful - When repeating calculations, precompute them.

state tracking enables single passes - Track just enough state to make decisions without looking back.

pattern recognition matters - Recognizing there are exactly two ways to form the answer unlocks the O(n) solution.

This problem taught me that optimization isn't just about making code faster - it's about understanding the problem structure deeply enough to see elegant solutions. The journey from O(n³) to O(n) wasn't just about removing loops; it was about recognizing fundamental patterns in the problem itself.