Sort Array By Parity II – C++ Solution

Problem Description

Ah, the classic dilemma of sorting an array by parity! It’s like trying to organize a party where you want all the odd-numbered guests to mingle on one side and the even-numbered guests on the other. Imagine a party where the odd folks are wearing polka dots and the even folks are in stripes. You wouldn’t want them to mix, right?

In this problem, you are given an array of integers, and your task is to rearrange it so that every even index contains an even number and every odd index contains an odd number. Sounds simple? Well, it’s like trying to get your cat and dog to sit together without a fight!

Code Solution


class Solution {
 public:
  vector sortArrayByParityII(vector& nums) {
    const int n = nums.size();

    for (int i = 0, j = 1; i < n; i += 2, j += 2) {
      while (i < n && nums[i] % 2 == 0)
        i += 2;
      while (j < n && nums[j] % 2 == 1)
        j += 2;
      if (i < n)
        swap(nums[i], nums[j]);
    }

    return nums;
  }
};

Approach

The approach here is as straightforward as a game of musical chairs. We use two pointers: one for the even indices and another for the odd indices. We traverse the array, and whenever we find an even number in an odd index or an odd number in an even index, we swap them. This continues until we’ve sorted the entire array by parity.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n) - We traverse the array a constant number of times.
Space Complexity	O(1) - We are sorting the array in place, so no extra space is used.

Real-World Example

Think of it like organizing a bookshelf where you want all the fiction books on one shelf and all the non-fiction books on another. You wouldn’t want a biography sitting next to a fantasy novel, would you? Similarly, in our array, we want to keep the even numbers and odd numbers separated, just like those books!