Skip to content

← leetcode

Find the Maximum Length of Valid Subsequence I

· Medium

LeetCode problem 3201

You can simply reword the question. Realise that to have a subsequence where adjacent elements sum:

  • to an even value, it implies that they are all of the same parity
  • to an odd value, it implies that they are of alternating parity

Simply just iterate through nums and keep track of three things:

  • the count of odd numbers
  • the count of even numbers
  • the length of numbers of alternating parity present in nums, starting from index 0

Finally, simply return the maximum value out of them three.

code

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int parityCount[2] = {0};
        int alternatingLength = 1;
        int alternatingParity = nums[0]%2;
        ++parityCount[nums[0]%2];
        for (int i = 1; i < nums.size(); ++i) {
            ++parityCount[nums[i]%2];
            if (nums[i]%2 != alternatingParity) {
                alternatingParity = nums[i]%2;
                ++alternatingLength;
            }
        }
        return max(alternatingLength, max(parityCount));
    }
};

complexity

  • Time: O(n) where n denotes the number of elements inside nums
  • Space: O(1)

time taken

  • 5 minutes and 49 seconds
    • i misread the question initially-