← leetcode

Longest Strictly Increasing or Strictly Decreasing Subarray

· Easy

LeetCode problem 3105

one pass, keeping the length of the current run in curr and its direction in isIncreasing, which is a bitmask:

  • 2 means the run is increasing
  • 1 means it's decreasing
  • 3 means it could still go either way.

then each number is compared with the one before it:

  • if it keeps going in a direction the run allows, the run gets longer and that direction is locked in
  • if it goes the other way, the run ends, and a new run of length 2 starts in the flipped direction (isIncreasing ^ 3 turns 2 into 1 and 1 into 2)
  • if it's equal, the run ends, and a new run of length 1 starts that could go either way

code link to code

class Solution {
public:
    int longestMonotonicSubarray(vector<int>& nums) {
        int ans{1}, curr{1};
        int isIncreasing = 3;

        for (int i = 1; i < nums.size(); ++i) {
            if ((nums[i] > nums[i-1] && (isIncreasing & 2)) || (nums[i] < nums[i-1] && (isIncreasing & 1))) {
                ++curr;
                isIncreasing = (nums[i] > nums[i-1]) ? 2 : 1;
            } else if (nums[i] != nums[i-1]) {
                ans = max(ans, curr);
                isIncreasing = isIncreasing ^ 3;
                curr = 2;
            } else {
                ans = max(ans, curr);
                isIncreasing = 3;
                curr = 1;
            }
        }
        return max(ans, curr);
    }
};

complexity link to complexity

  • Time: O(n) where n = len(nums)
  • Space: O(1)

time taken link to time taken

  • 13 minutes and 22 seconds