Even-Odd Boundary Pairs — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Arrays and solve the Even-Odd Boundary Pairs problem optimally.
O(n)O(1)Problem Description
You are provided with an integer array nums of length n, where n >= 3. The array is considered 'boundary-balanced' if, for every index i from 0 to n // 2 - 1, the pair of elements (nums[i], nums[n - 1 - i]) contains exactly one even integer and exactly one odd integer. In other words, the parity of the element at the left boundary must differ from the parity of the element at the corresponding right boundary for all symmetric pairs.
Your task is to determine whether the given array satisfies this boundary-balanced property. Return true if every symmetric pair consists of one even and one odd number; otherwise, return false.
Note: An integer is even if it is divisible by 2, and odd otherwise. The check must cover all pairs from the outermost to the innermost (excluding the middle element if n is odd).
DSA Pattern Breakdown
DSA Pattern Breakdown
"Even-Odd Boundary Pairs"
WHY DOES IT MATTER?
The two-pointer symmetry check reduces the problem from potentially O(n^2) with nested loops to O(n), which is critical for large datasets. It also eliminates the need for auxiliary storage, keeping space usage minimal.
OPTIMIZATION CHALLENGE
The key insight is that parity is a binary property; comparing modulo 2 of two numbers is a constant-time operation. By checking equality of parities, we can immediately reject a pair if both are even or both are odd.
REAL-WORLD CONNECTION
Think of a mirrored data backup system where each primary data block must have a complementary parity block on the opposite side of a storage ring. Ensuring one block is even and the other odd is analogous to verifying that each mirrored pair satisfies a complementary property.
When explaining this to an interviewer, emphasize the early exit strategy and the constant-space two-pointer traversal. Mention that the algorithm is linear and that you can prove correctness by induction on the number of processed pairs.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The core of the problem is parity symmetry: for every index i from 0 to n/2-1, the pair (nums[i], nums[n-1-i]) must contain one even and one odd number. A naive solution might iterate over all pairs, count evens and odds, and then compare counts, which adds unnecessary bookkeeping and can lead to O(n) time with O(n) auxiliary space if a list of pairs is stored. The optimal paradigm is a single linear scan that checks each pair on the fly: if nums[i] % 2 == nums[n-1-i] % 2, the array is not boundary-balanced. This approach uses only constant extra space and runs in O(n) time, making it scalable for very large arrays.
The algorithmic pattern here is a two-pointer technique that moves inward from both ends of the array. This pattern is common in problems involving symmetry, such as palindrome checks or two-sum with sorted arrays. By comparing elements at mirrored positions, we avoid nested loops and reduce the problem to a simple parity comparison.
Because the condition is local to each pair, we can terminate early as soon as a mismatch is found, which gives an average-case performance better than always scanning the entire array. This early exit is a key optimization that makes the solution efficient in practice, especially when the array is not boundary-balanced.
Interview Questions on This Problem
Q1How would you modify this algorithm to check if the array is 'boundary-balanced' when the array length is odd?
For odd lengths, the middle element has no counterpart, so it can be ignored. The algorithm remains the same: iterate i from 0 to floor(n/2)-1 and compare nums[i] and nums[n-1-i]. The middle element does not affect the parity condition.
Q2In a distributed system where each node holds a segment of the array, how would you determine if the global array is boundary-balanced?
Each node can locally check its boundary pairs and report a boolean. The coordinator then aggregates these booleans using logical AND. If any node reports false, the global array is not boundary-balanced.
Q3What is the time complexity if you were to sort the array first and then check for boundary balance?
Sorting takes O(n log n) time, and the subsequent check is O(n). Thus the overall complexity would be dominated by the sort, yielding O(n log n), which is worse than the optimal O(n) solution.
Examples
Input
nums = [1, 2, 3]
Output
true
Explanation: The array has length 3. The only symmetric pair is (nums[0], nums[2]) = (1, 3). Both 1 and 3 are odd. Since both are odd, the pair does not contain exactly one even and one odd. Wait, let me re-evaluate. 1 is odd, 3 is odd. This pair fails. Let's pick a better example. Revised Example 1: Input: nums = [1, 4, 3] Output: true Explanation: The array has length 3. The only symmetric pair is (nums[0], nums[2]) = (1, 3). 1 is odd, 3 is odd. This is false. Let's try [1, 4, 2]. Pair (1, 2). 1 is odd, 2 is even. This is true. Let's use [1, 4, 2]. Let's restart examples with correct logic. Example 1: Input: nums = [1, 4, 2] Output: true Explanation: n=3. Pair (nums[0], nums[2]) = (1, 2). 1 is odd, 2 is even. One odd, one even. Condition met. Return true.
Input
nums = [2, 4, 6, 8]
Output
false
Explanation: n=4. Pairs: (nums[0], nums[3]) = (2, 8). Both even. Fails. (nums[1], nums[2]) = (4, 6). Both even. Fails. Return false.
Input
nums = [1, 2, 3, 4]
Output
true
Explanation: n=4. Pair 1: (nums[0], nums[3]) = (1, 4). 1 is odd, 4 is even. OK. Pair 2: (nums[1], nums[2]) = (2, 3). 2 is even, 3 is odd. OK. All pairs valid. Return true.
Input
nums = [5, 10, 15, 20, 25]
Output
false
Explanation: n=5. Pair 1: (nums[0], nums[4]) = (5, 25). Both odd. Fails. Return false.
Constraints
- 3 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Using the two-pointer technique, we place one pointer at the start and another at the end of the array. In a single pass, we check if the elements at these pointers have different parity (one even, one odd). We increment the left pointer and decrement the right pointer, immediately returning false if any pair violates the condition.
Brute Force Approach
A naive approach would involve copying the array, reversing it, and checking if each element at index i in the original array has a different parity than the element at index i in the reversed array. This takes extra space and requires scanning the entire array twice.
Code Solutions
/**
* @param {number[]} nums
* @return {boolean}
*/
var isBoundaryBalanced = function(nums) {
const n = nums.length;
for (let i = 0; i < Math.floor(n / 2); i++) {
const a = nums[i];
const b = nums[n - 1 - i];
if ((a % 2 === 0 && b % 2 === 0) || (a % 2 !== 0 && b % 2 !== 0)) {
return false;
}
}
return true;
};class Solution {
public:
bool isBoundaryBalanced(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n / 2; ++i) {
int a = nums[i];
int b = nums[n - 1 - i];
if ((a % 2 == 0 && b % 2 == 0) || (a % 2 != 0 && b % 2 != 0)) {
return false;
}
}
return true;
}
};class Solution {
public boolean isBoundaryBalanced(int[] nums) {
int n = nums.length;
for (int i = 0; i < n / 2; i++) {
int a = nums[i];
int b = nums[n - 1 - i];
if ((a % 2 == 0 && b % 2 == 0) || (a % 2 != 0 && b % 2 != 0)) {
return false;
}
}
return true;
}
}class Solution:
def isBoundaryBalanced(self, nums: List[int]) -> bool:
n = len(nums)
for i in range(n // 2):
a = nums[i]
b = nums[n - 1 - i]
if (a % 2 == 0 and b % 2 == 0) or (a % 2 != 0 and b % 2 != 0):
return False
return True/**
* @param {number[]} nums
* @return {boolean}
*/
var isBoundaryBalanced = function(nums) {
const n = nums.length;
for (let i = 0; i < Math.floor(n / 2); i++) {
const a = nums[i];
const b = nums[n - 1 - i];
if ((a % 2 === 0 && b % 2 === 0) || (a % 2 !== 0 && b % 2 !== 0)) {
return false;
}
}
return true;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.