What defines a special array in Special Array II?

A special array requires that every pair of adjacent elements has different parity, meaning no two consecutive numbers are both even or both odd.

Can prefix sums handle all queries efficiently?

Yes, by precomputing where parity violations occur, each query can be answered in O(1) using prefix sums.

Why use binary search over the valid answer space here?

Binary search guides thinking about splitting the array into non-overlapping continuous special subarrays, ensuring correct evaluations of large ranges.

What happens if the subarray has only one element?

Single-element subarrays are trivially special since there are no adjacent pairs to violate the parity condition.

How does GhostInterview validate subarray correctness instantly?

It uses precomputed parity violations and prefix sums to check any query range instantly, showing true if no violations exist and false otherwise.

#3152

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

特殊数组 II

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个特殊数组。你有一个整数数组 nums 和一个二维整数矩阵 queries ，对于 queries[i] = [from i , to i ] ，请你帮助你检查子数组 nums[from i ..to i ] 是不是一个特…

数组二分查找前缀和

题目描述

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

你有一个整数数组 nums 和一个二维整数矩阵 queries，对于 queries[i] = [from_i, to_i]，请你帮助你检查子数组 nums[from_i..to_i] 是不是一个 特殊数组 。

返回布尔数组 answer，如果 nums[from_i..to_i] 是特殊数组，则 answer[i] 为 true ，否则，answer[i] 为 false 。

示例 1：

输入：nums = [3,4,1,2,6], queries = [[0,4]]

输出：[false]

解释：

子数组是 [3,4,1,2,6]。2 和 6 都是偶数。

示例 2：

输入：nums = [4,3,1,6], queries = [[0,2],[2,3]]

输出：[false,true]

解释：

子数组是 [4,3,1]。3 和 1 都是奇数。因此这个查询的答案是 false。
子数组是 [1,6]。只有一对：(1,6)，且包含了奇偶性不同的数字。因此这个查询的答案是 true。

提示：

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

lightbulb

解题思路

方法一：记录每个位置的最左特殊数组位置

我们可以定义一个数组 $d$ 来记录每个位置的最左特殊数组位置，初始时 $d[i] = i$ 。然后我们从左到右遍历数组 $nums$ ，如果 $nums[i]$ 和 $nums[i - 1]$ 的奇偶性不同，那么 $d[i] = d[i - 1]$ 。

最后我们遍历每个查询，判断 $d[to] <= from$ 是否成立即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。

1

2

3

4

5

6

7

8

9

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        d = list(range(n))
        for i in range(1, n):
            if nums[i] % 2 != nums[i - 1] % 2:
                d[i] = d[i - 1]
        return [d[t] <= f for f, t in queries]

speed

复杂度分析

指标	值
时间	complexity is O(M + N), where N is the length of nums and M is the number of queries, because we precompute violations in one pass and answer each query in O(1). Space complexity is O(N) for storing the prefix sum array of violations.
空间	O(M)

psychology

面试官常问的追问

外企场景

question_mark
Expect discussion of edge cases with consecutive even or odd numbers.
question_mark
Look for recognition of prefix sums as a method to optimize multiple queries over large arrays.
question_mark
Watch for attempts to split arrays and reasoning about continuous special subarrays using binary search patterns.

warning

常见陷阱

外企场景

error
Failing to check that the prefix sum correctly reflects violations at the last element of the subarray.
error
Assuming the subarray is special if the first and last elements are different parity, ignoring internal violations.
error
Overcomplicating with full nested loops instead of precomputing violations efficiently.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Check for special subarrays where the parity difference must alternate every two elements instead of each adjacent pair.
arrow_right_alt
Determine the maximum length of a special subarray within a single query range.
arrow_right_alt
Modify nums dynamically and answer queries in real-time, requiring a segment tree or binary indexed tree.

help

常见问题

外企场景

继续练习

#3261 统计满足 K 约束的子字符串数量 II #3312 查询排序后的最大公约数 #2968 执行操作使频率分数最大