Special Pairs Problem

Problem Description

You are given an array nums consisting of integers. A pair of consecutive integers (nums[i], nums[i+1]) is called a special pair if both integers belong to the same "team":

• Team Even (🟢): Both integers are even.
• Team Odd (🔴): Both integers are odd.

The task is to process several queries. Each query is of the form [left, right], and you need to determine whether there are no special pairs between indices left and right in the array. If there are no special pairs, return true for the query; otherwise, return false.

Approach

Step 1: Build the Prefix Array

We create a prefix array prefix that counts the cumulative number of special pairs as we traverse the array:

• If two consecutive numbers have the same "team" (both 🟢 or both 🔴), we increase the count.
• Otherwise, the count remains unchanged.

For example, for nums = [4, 3, 1, 6]:

• At index 0: No pairs yet → prefix[0] = 0.
• At index 1: (4, 3) isn’t special → prefix[1] = 0.
• At index 2: (3, 1) is special → prefix[2] = 1.
• At index 3: (1, 6) isn’t special → prefix[3] = 1.

Final prefix array: [0, 0, 1, 1].

Step 2: Process Queries

For each query [left, right]:

• Calculate the number of special pairs in the range using the prefix array:
  javaCopy

  specialCount = prefix[right] - (left > 0 ? prefix[left - 1] : 0);
  

• If specialCount == 0, return true; otherwise, return false.

Complexity

• Building the prefix array: O(n), where n is the size of nums.
• Processing queries: O(q), where q is the number of queries.

Total: O(n + q).

Test Cases

Example 1

Input:

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

Output:

[true, false, false]

Explanation:

• Query [0, 1]: No special pairs → true.
• Query [1, 2]: (3, 1) is special → false.
• Query [0, 3]: (3, 1) is special → false.

Example 2

Input:

nums = [2, 4, 6, 8];
queries = [[0, 3], [1, 2]];

Output:

[false, false]

Explanation:

• Query [0, 3]: All pairs are special → false.
• Query [1, 2]: (4, 6) is special → false.

Example 3

Input:

nums = [1, 3, 5, 7];
queries = [[0, 2], [1, 3]];

Output:

[false, false]

Explanation:

• Query [0, 2]: All pairs are special → false.
• Query [1, 3]: All pairs are special → false.