Special Array II solution and explanation
9 more videos on this problem
Special Array II | 3 Detailed Approaches | Beginners Alert | Leetcode 3152 | codestorywithMIKcodestorywithMIK · 1:07:18 · 8K views
3152. Special Array II | 3151. Special Array I | Prefix Sums | ArraysAryan Mittal · 16:06 · 7K views
Special Array II | Leetcode 3152Techdose · 13:49 · 4K views
3152. Special Array II | leetcode daily challenge | shashcode | shashwat tiwariShashCode · 13:14 · 2K views
3152. Special Array II (Leetcode Medium)Programming Live with Larry · 8:26 · 703 views
Daily Leetcode #1714: Dec 09, 2024 - 3152. Special Array IIProgramming Live with Larry · 12:49 · 579 views
LeetCode 3152 Special Array II | Prefix Sum | Asked in NPCI Google AmazonCode Harmony · 18:11 · 307 views
Leetcode 3152 | Special Array II | Weekly Contest 398Road To FAANG · 6:05 · 248 views
Special Array II - Leetcode 3152 - DSA - ArraysTHE CODE CLUB · 7:35 · 92 views
Special Array II - Leetcode 3152 - JavaCode With K5KC · 8:18 · 91 views
The problem
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 isfalse. - 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 istrue.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1
Approach overview
Problem Overview: You receive an integer array nums and multiple queries [l, r]. A subarray is considered special if every pair of adjacent elements has different parity (one even, one odd). For each query, determine whether the subarray from index l to r satisfies this condition.
Approach 1: Brute Force Check per Query (O(q * n) time, O(1) space)
The most direct strategy is to evaluate every query independently. For a query [l, r], iterate from l to r-1 and check whether nums[i] % 2 equals nums[i+1] % 2. If two adjacent numbers share the same parity, the subarray is not special. This approach uses simple iteration and parity checks with constant extra memory. The downside is repeated work across overlapping queries, which pushes the worst‑case runtime to O(q * n). It works for small inputs but struggles when both the array length and query count are large.
Approach 2: Prefix Parity Difference Array (O(n + q) time, O(n) space)
An optimized approach precomputes where the array violates the special condition. Build a difference array where bad[i] = 1 if nums[i] and nums[i-1] have the same parity, otherwise 0. Next, compute a prefix sum over this array so you can quickly count parity violations in any range. For a query [l, r], check the prefix sum between l+1 and r. If the sum is 0, no adjacent elements share the same parity and the subarray is special. This transforms repeated scans into constant‑time checks using a prefix sum structure.
The key insight is that the property of being special depends only on adjacent pairs. Once those violations are precomputed, every query becomes a quick range check. This is a common pattern in array preprocessing problems: convert repeated validations into prefix statistics that answer queries instantly. While the problem lists binary search among related topics, the efficient solution mainly relies on prefix aggregation.
Recommended for interviews: Start by describing the brute force approach to show you understand the condition being checked. Then move to the prefix parity difference array, which reduces query time to O(1) after preprocessing. Interviewers typically expect this optimized O(n + q) solution because it demonstrates the ability to transform repeated range checks into prefix computations.
Approach 1: Brute Force Approach
This approach involves iterating over each subarray defined by the queries and checking every adjacent pair for differing parity. The naive nature of this method makes it straightforward but potentially inefficient for larger inputs.
def is_special(nums, queries):
answer = []
for query in queries:
start, end = query
is_special = True
for i in range(start, end):
if nums[i] % 2 == nums[i + 1] % 2:
is_special = False
break
answer.append(is_special)
return answerimport java.util.List;
import java.util.ArrayList;
class Solution {
public List<Boolean> isSpecial(int[] nums, int[][] queries) {
List<Boolean> answer = new ArrayList<>();
for(int[] query : queries) {
int start = query[0];
int end = query[1];
boolean isSpecial = true;
for(int i = start; i < end; i++) {
if(nums[i] % 2 == nums[i + 1] % 2) {
isSpecial = false;
break;
}
}
answer.add(isSpecial);
}
return answer;
}
}#include <vector>
using namespace std;
vector<bool> isSpecial(vector<int>& nums, vector<vector<int>>& queries) {
vector<bool> answer;
for(auto& query : queries) {
int start = query[0], end = query[1];
bool isSpecial = true;
for(int i = start; i < end; ++i) {
if((nums[i] % 2) == (nums[i + 1] % 2)) {
isSpecial = false;
break;
}
}
answer.push_back(isSpecial);
}
return answer;
}function isSpecial(nums, queries) {
const answer = [];
for(let [start, end] of queries) {
let isSpecial = true;
for(let i = start; i < end; i++) {
if((nums[i] % 2) === (nums[i + 1] % 2)) {
isSpecial = false;
break;
}
}
answer.push(isSpecial);
}
return answer;
}#include <stdbool.h>
int* isSpecial(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
*returnSize = queriesSize;
int* answer = (int*) malloc(queriesSize * sizeof(int));
for(int i = 0; i < queriesSize; i++) {
int start = queries[i][0];
int end = queries[i][1];
bool isSpecial = true;
for(int j = start; j < end; j++) {
if((nums[j] % 2) == (nums[j + 1] % 2)) {
isSpecial = false;
break;
}
}
answer[i] = isSpecial;
}
return answer;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<bool> IsSpecial(int[] nums, int[][] queries) {
List<bool> answer = new List<bool>();
foreach(var query in queries) {
int start = query[0];
int end = query[1];
bool isSpecial = true;
for(int i = start; i < end; i++) {
if((nums[i] % 2) == (nums[i + 1] % 2)) {
isSpecial = false;
break;
}
}
answer.Add(isSpecial);
}
return answer;
}
}This Python solution follows the brute-force approach: iterating through each query range and checking if all adjacent numbers differ in parity.
Time Complexity: O(len(queries) × len(nums)).
Space Complexity: O(len(queries)).
Approach 2: Prefix Parity Difference Array
This approach leverages the use of a prefix array to determine segment misfits based on parity changes. By preprocessing the array into a prefix difference array, each query can be answered in constant time by checking if any parity changes exist within the given range.
def is_special(nums, queries):
n = len(nums)
diff = [(nums[i] % 2) != (nums[i + 1] % 2) for i in range(n - 1)]
answer = []
for start, end in queries:
is_special = all(diff[i] for i in range(start, end))
answer.append(is_special)
return answerimport java.util.List;
import java.util.ArrayList;
class Solution {
public List<Boolean> isSpecial(int[] nums, int[][] queries) {
int n = nums.length;
boolean[] diff = new boolean[n - 1];
for (int i = 0; i < n - 1; i++) {
diff[i] = (nums[i] % 2) != (nums[i + 1] % 2);
}
List<Boolean> answer = new ArrayList<>();
for (int[] query : queries) {
int start = query[0];
int end = query[1];
boolean isSpecial = true;
for (int i = start; i < end; i++) {
if (!diff[i]) {
isSpecial = false;
break;
}
}
answer.add(isSpecial);
}
return answer;
}
}#include <vector>
using namespace std;
vector<bool> isSpecial(vector<int>& nums, vector<vector<int>>& queries) {
int n = nums.size();
vector<int> diff(n - 1);
for (int i = 0; i < n - 1; ++i) {
diff[i] = (nums[i] % 2) != (nums[i + 1] % 2);
}
vector<bool> answer;
for (auto& query : queries) {
int start = query[0], end = query[1];
bool isSpecial = true;
for (int i = start; i < end; ++i) {
if (!diff[i]) {
isSpecial = false;
break;
}
}
answer.push_back(isSpecial);
}
return answer;
}function isSpecial(nums, queries) {
const n = nums.length;
const diff = Array(n - 1);
for (let i = 0; i < n - 1; i++) {
diff[i] = (nums[i] % 2) !== (nums[i + 1] % 2);
}
const answer = [];
for (let [start, end] of queries) {
let isSpecial = true;
for (let i = start; i < end; i++) {
if (!diff[i]) {
isSpecial = false;
break;
}
}
answer.push(isSpecial);
}
return answer;
}#include <stdbool.h>
int* isSpecial(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
*returnSize = queriesSize;
int* answer = (int*) malloc(queriesSize * sizeof(int));
int* diff = (int*) malloc(numsSize * sizeof(int));
for (int i = 0; i < numsSize - 1; i++) {
diff[i] = (nums[i] % 2) != (nums[i + 1] % 2);
}
for (int i = 0; i < queriesSize; i++) {
int start = queries[i][0];
int end = queries[i][1];
bool isSpecial = true;
for (int j = start; j < end; j++) {
if (!diff[j]) {
isSpecial = false;
break;
}
}
answer[i] = isSpecial;
}
free(diff);
return answer;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<bool> IsSpecial(int[] nums, int[][] queries) {
int n = nums.Length;
bool[] diff = new bool[n - 1];
for (int i = 0; i < n - 1; i++) {
diff[i] = (nums[i] % 2) != (nums[i + 1] % 2);
}
List<bool> answer = new List<bool>();
foreach(var query in queries) {
int start = query[0];
int end = query[1];
bool isSpecial = true;
for(int i = start; i < end; i++) {
if(!diff[i]) {
isSpecial = false;
break;
}
}
answer.Add(isSpecial);
}
return answer;
}
}The Python implementation creates a preparatory parity-difference array to process subarray specialty requests briskly through logical checks within the 'diff' construct.
Time Complexity: O(n + q).
Space Complexity: O(n).
Approach 3: Record the Leftmost Special Array Position for Each Position
We can define an array d to record the leftmost special array position for each position, initially d[i] = i. Then we traverse the array nums from left to right. If nums[i] and nums[i - 1] have different parities, then d[i] = d[i - 1].
Finally, we traverse each query and check whether d[to] <= from holds.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array.
function isArraySpecial(nums: number[], queries: number[][]): boolean[] {
const n = nums.length;
const d: number[] = Array.from({ length: n }, (_, i) => i);
for (let i = 1; i < n; ++i) {
if (nums[i] % 2 !== nums[i - 1] % 2) {
d[i] = d[i - 1];
}
}
return queries.map(([from, to]) => d[to] <= from);
}func isArraySpecial(nums []int, queries [][]int) (ans []bool) {
n := len(nums)
d := make([]int, n)
for i := range d {
d[i] = i
}
for i := 1; i < len(nums); i++ {
if nums[i]%2 != nums[i-1]%2 {
d[i] = d[i-1]
}
}
for _, q := range queries {
ans = append(ans, d[q[1]] <= q[0])
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(len(queries) × len(nums)). |
| Prefix Parity Difference Array | Time Complexity: O(n + q). |
| Record the Leftmost Special Array Position for Each Position | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Check | O(q * n) | O(1) | Small arrays or few queries where simplicity matters more than performance |
| Prefix Parity Difference Array | O(n + q) | O(n) | Best general solution when many range queries must be answered quickly |
Frequently asked questions
Is Special Array II easy or hard?
Special Array II is rated Medium because the brute force solution is straightforward but inefficient. Recognizing that adjacent parity checks can be preprocessed with prefix sums is the key step that makes the problem efficient.
Special Array II Python/Java solution
Most implementations first compute a prefix array of parity violations, then answer each query using prefix differences. The logic is identical across Python, Java, C++, and other languages, with overall complexity O(n + q) time and O(n) space.
How to solve Special Array II in O(n)?
Precompute an array marking parity violations: bad[i] = 1 if nums[i] and nums[i-1] have the same parity. Build a prefix sum over this array. For a query [l, r], check whether the prefix sum difference between r and l+1 is zero. If it is zero, the subarray is special.
What is the best approach for Special Array II?
The most efficient solution uses a prefix parity difference array. Precompute positions where adjacent elements share the same parity, store them in a prefix sum, and answer each query by checking if any violations exist in the range. This reduces query time to O(1) after O(n) preprocessing.
Is Special Array II asked at Google/Amazon/Meta?
Problems involving prefix sums, parity checks, and range queries frequently appear in interviews at companies like Google, Amazon, and Meta. Special Array II reflects a common pattern where preprocessing allows fast query evaluation.
What data structure is used in Special Array II?
The main structure is a prefix sum array built from a parity violation indicator array. This allows constant-time range checks to determine whether any adjacent elements in a subarray share the same parity.
What is the time complexity of Special Array II?
The optimal prefix sum approach runs in O(n + q) time, where n is the array length and q is the number of queries. Preprocessing the parity violations takes O(n), and each query is answered in constant time using prefix sums.