Special Array II - Practice Coding Problems

Special Array II - Problem

An array is considered special if every pair of its adjacent elements contains two numbers with different parity (one even, one odd).

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

Return an array of booleans answer such that answer[i] is true if nums[from_i..to_i] is special.

Input & Output

Example 1 — Mixed Parity Array

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

› Output: [false]

💡 Note: Checking subarray [3,4,1,2,6]: 3(odd),4(even)✓, 4(even),1(odd)✓, 1(odd),2(even)✓, 2(even),6(even)✗ - last pair has same parity

Example 2 — Perfect Alternating

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

› Output: [false,true]

💡 Note: Query [0,2] checks [4,3,1]: 4(even),3(odd)✓, 3(odd),1(odd)✗. Query [2,3] checks [1,6]: 1(odd),6(even)✓

Example 3 — Single Element

$ Input: nums = [1], queries = [[0,0]]

› Output: [true]

💡 Note: Single element subarray is always special since there are no adjacent pairs to check

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array with integers and query ranges

Check Parity

Verify adjacent elements have different parity (even/odd)

Output

Boolean array indicating which ranges are special

Key Takeaway

🎯 Key Insight: Use prefix sums to precompute bad pair positions for O(1) query answering

Asked in

G Google 23 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to precompute positions where adjacent elements have the same parity, then use prefix sums for O(1) query answering. Best approach uses prefix sum preprocessing. Time: O(n + q), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Each Query	O(q × n)	O(1)	For each query, iterate through the subarray to check if adjacent elements have different parity
Prefix Sum - Precompute Bad Pairs	O(n + q)	O(n)	Precompute positions where adjacent elements have same parity, then use prefix sums for O(1) query answering

Brute Force - Check Each Query — Algorithm Steps

For each query [from, to]
Iterate through nums[from] to nums[to-1]
Check if nums[i] and nums[i+1] have different parity
Return false if any pair has same parity

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Range

Select range [from, to] from query

Check Pairs

Iterate through adjacent pairs checking parity

Result

Return true if all pairs have different parity

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool* solution(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize) {
    bool* result = (bool*)malloc(queriesSize * sizeof(bool));
    
    for (int q = 0; q < queriesSize; q++) {
        int from = queries[q][0];
        int to = queries[q][1];
        bool isSpecial = true;
        
        for (int i = from; i < to; i++) {
            if (nums[i] % 2 == nums[i + 1] % 2) {
                isSpecial = false;
                break;
            }
        }
        
        result[q] = isSpecial;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int** queries = (int**)malloc(100 * sizeof(int*));
    int queriesSize = 0;
    
    char* start = strchr(line, '[');
    while (start != NULL) {
        start++;
        queries[queriesSize] = (int*)malloc(2 * sizeof(int));
        sscanf(start, "%d,%d", &queries[queriesSize][0], &queries[queriesSize][1]);
        queriesSize++;
        start = strchr(start, '[');
    }
    
    int queriesColSize[100];
    for (int i = 0; i < queriesSize; i++) {
        queriesColSize[i] = 2;
    }
    
    bool* result = solution(nums, numsSize, queries, queriesSize, queriesColSize);
    
    printf("[");
    for (int i = 0; i < queriesSize; i++) {
        printf("%s", result[i] ? "true" : "false");
        if (i < queriesSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × n)

For each of q queries, we might check up to n adjacent pairs

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for checking

✓ Linear Space

28.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Each Query — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler