3151.Special_Array_I(Easy).md

3151. Special Array I (Easy)

Date and Time: Feb 1, 2025, 11:34 (EST)

Link: https://leetcode.com/problems/special-array-i

Question:

An array is considered special if every pair of its adjacent elements contains two numbers with different parity.

You are given an array of integers nums. Return true if nums is a special array, otherwise, return false.

Example 1:

Input: nums = [1]

Output: true

Explanation:
There is only one element. So the answer is true.

Example 2:

Input: nums = [2,1,4]

Output: true

Explanation:
There is only two pairs: (2,1) and (1,4), and both of them contain numbers with different parity. So the answer is true.

Example 3:

Input: nums = [4,3,1,6]

Output: false

Explanation:
nums[1] and nums[2] are both odd. So the answer is false.

Constraints:

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 100

Walk-through:

First check if len(nums) == 1, then we can return True right away.

Otherwise, we use prev to keep track of previous element's parity by nums[i] % 2, then we use it to compare with current element's parity nums[i] % 2, if they are the same, we should return False. Otherwise, update prev to be the current parity.

Python Solution:

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        # prev = elem % 2 and check if it equals to current % 2

        # TC: O(n), n=len(nums), SC: O(1)
        if len(nums) == 1:
            return True
        prev = nums[0] % 2
        for i in range(1, len(nums)):
            if prev == nums[i] % 2:
                return False
            prev = nums[i] % 2
        return True

Time Complexity: $O(n)$
Space Complexity: $O(1)$