leetcode - 3152. Special Array II

Description

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

You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is special or not.

Return an array of booleans answer such that answer[i] is true if nums[fromi…toi] is special.

Example 1:

Input: nums = [3,4,1,2,6], queries = [[0,4]]

Output: [false]

Explanation:

The subarray is [3,4,1,2,6]. 2 and 6 are both even.

Example 2:

Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]

Output: [false,true]

Explanation:

The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
The subarray is [1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

Solution

Binary search

Parse the nums to get 2 lists, if the current number is not special with its right, and if the current number is not special with its left. Then for each query, we want to get the smallest number at the right of the query start, and the largest number at the left of the query end. If these 2 numbers can form an interval, that means the subarray contains a non-special number, making this subarray a non-special one.

Time complexity: KaTeX parse error: Undefined control sequence: \logn at position 4: o(n\̲l̲o̲g̲n̲)
Space complexity: $o(n)$

Prefix sum

Solved after help…

Use a prefix sum to store the number of violations previously. So if the current number is not special with its left, then prefix[i] = prefix[i - 1] + 1, else prefix[i] = prefix[i - 1]. So for each query, if the prefix[query_end] - prefix[query-start] == 0, then we know there’s no violations during this query.

Time complexity: $o(m+n)$
Space complexity: $o(m)$

Code

Binary search

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        def find_right(nums: list, target: int) -> int:
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right) >> 1
                if nums[mid] >= target:
                    right = mid
                else:
                    left = mid + 1
            return (left + right) >> 1
        def find_left(nums: list, target: int) -> int:
            left, right = 0, len(nums) - 1
            while left < right:
                mid = (left + right + 1) >> 1
                if nums[mid] <= target:
                    left = mid
                else:
                    right = mid - 1
            return (left + right + 1) >> 1

        # non-special indexes left
        # non-sepcial indexes right
        # left, right
        non_special_indexes_left = []
        non_special_indexes_right = []
        for i in range(len(nums)):
            if i >= 1:
                if (nums[i] & 1 == 1 and nums[i - 1] & 1 == 1) or (nums[i] & 1 == 0 and nums[i - 1] & 1 == 0):
                    non_special_indexes_left.append(i)
            if i < len(nums) - 1:
                if (nums[i] & 1 == 1 and nums[i + 1] & 1 == 1) or (nums[i] & 1 == 0 and nums[i + 1] & 1 == 0):
                    non_special_indexes_right.append(i)
        res = []
        for q_start, q_end in queries:
            non_special_right_index = find_right(non_special_indexes_right, q_start)
            non_special_left_index = find_left(non_special_indexes_left, q_end)
            if (non_special_indexes_right and non_special_indexes_right[non_special_right_index] >= q_start) and (non_special_indexes_left and non_special_indexes_left[non_special_left_index] <= q_end):
                res.append(not non_special_indexes_right[non_special_right_index] < non_special_indexes_left[non_special_left_index])
            elif non_special_indexes_right and non_special_indexes_right[non_special_right_index] >= q_start:
                res.append(not non_special_indexes_right[non_special_right_index] < q_end)
            elif non_special_indexes_left and non_special_indexes_left[non_special_left_index] <= q_end:
                res.append(not non_special_indexes_left[non_special_left_index] > q_start)
            else:
                res.append(True)
        return res

Prefix

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        prefix_vio = [0]
        for i in range(1, len(nums)):
            if (nums[i] & 1 == 1 and nums[i - 1] & 1 == 1) or (nums[i] & 1 == 0 and nums[i - 1] & 1 == 0):
                prefix_vio.append(prefix_vio[-1] + 1)
            else:
                prefix_vio.append(prefix_vio[-1])
        res = []
        for q_start, q_end in queries:
            res.append(prefix_vio[q_end] - prefix_vio[q_start] == 0)
        return res