Sort Array By Parity II – Java Solution

Explore Solutions in Other Languages

Problem Description

Welcome to the whimsical world of arrays, where even and odd numbers are having a party, and they just can’t seem to get along! The problem at hand, Sort Array By Parity II, is like trying to organize a dance floor where all the even-numbered guests are on one side and the odd-numbered guests are on the other.

Imagine you’re at a party, and you have a mix of friends who are either wearing blue (even numbers) or red (odd numbers). Your task is to rearrange them so that they alternate colors. So, if you have a group of friends represented by an array, you need to ensure that every even-indexed position has a blue friend (even number) and every odd-indexed position has a red friend (odd number).

In simpler terms, if you have an array of integers, you need to sort it such that:

nums[0], nums[2], nums[4], … are all even
nums[1], nums[3], nums[5], … are all odd

And just like that, you’ve got a perfectly organized party!

Code Solution


class Solution {
  public int[] sortArrayByParityII(int[] nums) {
    final int n = nums.length;

    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) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }
    }

    return nums;
  }
}

Approach

The approach taken in this solution is quite straightforward. We use two pointers: one (i) for the even indices and another (j) for the odd indices. The algorithm works as follows:

Start with i at index 0 (even) and j at index 1 (odd).
Move i forward until you find an odd number at an even index.
Move j forward until you find an even number at an odd index.
If both indices are valid, swap the numbers at these indices.
Repeat until all numbers are in their correct positions.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the input array. We traverse the array a constant number of times.
Space Complexity	O(1), as we are sorting the array in place without using any additional data structures.

Real-World Example

Think of a school dance where boys and girls are supposed to alternate in the line-up. If you have a line of students represented by an array, you need to ensure that every even position has a boy and every odd position has a girl. Just like in our problem, you would need to swap students around until everyone is in the right spot.