Adjacent Increasing Subarrays Detection II

main.md

Leetcode #3350

Approach

I assembled every individual increasing set of elements into an array, arr, if all elements in the nums array are increasing, then size of arr will be 1, then we can return the result of the floor division of the length by 2, to give the maximum number of elements in each adjacent increasing group.

For an array with > 1 increasing groups, we iterate over the set of arrays, first we check for the possible adjacent grouping we can get from the current increasing group (max(res, len/2);), then we compare the adjacent increasing groups as well, picking the min of them, to ensure we have the maximum equal number of elemnts from each group.

For each computation, we keep the max value, which at the end gives the maximum possible valaue of elements that satisfy the adjacent incresing group rule.

class Solution {
public:
    int maxIncreasingSubarrays(vector<int>& nums) {
        vector<vector<int>> arr = {{nums.at(0)}};

        int res = 0;

        for(int i = 1; i < nums.size(); i++) {
            int curr_len = arr.size() - 1;
            int curr_n_len = arr[curr_len].size() - 1;

            if(nums.at(i) > arr[curr_len][curr_n_len]) {
                arr[curr_len].push_back(nums.at(i));
                continue;
            }

            arr.push_back({nums.at(i)});
        }

        if(arr.size() == 1) return arr.at(0).size()/2;

        for(int i = 0; i < arr.size() - 1; i++) {
            int len = arr.at(i).size();
            int nxt = arr.at(i+1).size();

            res = max(res, len/2);
            
            int curr_nxt = min(len, nxt);

            res = max(res, curr_nxt);
        }

        int last_len = arr.at(arr.size() - 1).size();

        res = max(res, last_len/2);

        return res;
    }
};

Complexities

Space complexity: O(N)

Time Complexity: O(N)