Problem Statement in English

In this question, we are given an array nums and we have to return the length of the longest subsequence such that the sum of every consecutive pair of elements in the subsequence is the same as the previous pair when moduloed by 2.

Approach

The thing is that this question has an input size of $10^5$ and, so by reading that we know that we have to find a solution that runs in $O(n)$ or $O(n \log n)$ time complexity.

The next thing to notice is that funky modulo by 2. That means the moduloed value can only be 0 or 1. So, we can divide the array into three parts: one with even numbers, one with odd numbers, or one with them alternating.

Think about it…that’s the only way to have the same moduloed value for every consecutive pair of elements in the subsequence.

From there it’s just about finding each of these cases by running through the array and counting the number of even and odd numbers, and one for the alternating case.

Solution in Python


class Solution:
    def maximumLength(self, nums: List[int]) -> int:
        if len(nums) <= 2:
            return len(nums)

        wantOdd = nums[0] % 2 == 0
        res = 1

        # alternating
        for n in nums[1:]:
            if (wantOdd and n % 2) or (not wantOdd and not n % 2):
                res += 1
                wantOdd = not wantOdd

        # only odd or only even
        odd = even = 0
        for n in nums:
            if n % 2:
                odd += 1
            else:
                even +=1
        
        res = max(odd, even, res)

        return res

Complexity

  • Time: $O(n)$
    Since we are iterating through the array a few times, the time complexity is linear.

  • Space: $O(1)$
    Since we are only using a few variables to keep track of the counts, the space complexity is constant.

Mistakes I Made

Forgot the case where it’s only even or odd 🤦‍♂️

And we are done.