1. Introduction
Given an array of integers nums, half of the integers in nums are odd, and the other half are even.
Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.
Return any answer array that satisfies this condition.
Example 1:
Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] is also the correct answer.
Example 2:
Input: nums = [2,3]
Output: [2,3]
Method Signature:
public int[] sortArrayByParityII(int[] nums) {
}
2. Content
The input array comprises half of odd and half of even numbers. We can just create a new result array and insert even numbers in even index and odd numbers in odd index. This solution uses auxiliary space. The interesting part of this problem is to solve n O(1) space. I will provide both the solutions with their time and space complexity.
3. O(n) Auxiliary Space Solution.
- Initialize a result
public int[] sortArrayByParityII(int[] nums) {
int[] result = new int[nums.length];
}
- Insert even elements in the even index.
public int[] sortArrayByParityII(int[] nums) {
int[] result = new int[nums.length];
int evenIndex = 0;
for (int val : nums) {
if (val % 2 == 0) {
result[evenIndex] = val;
evenIndex = evenIndex + 2;
}
}
}
- Insert odd elements in the odd index.
public int[] sortArrayByParityIIExtraSpace(int[] nums) {
int[] result = new int[nums.length];
int evenIndex = 0;
for (int val : nums) {
if (val % 2 == 0) {
result[evenIndex] = val;
evenIndex = evenIndex + 2;
}
}
int oddIndex = 1;
for (int val : nums) {
if (val % 2 != 0) {
result[oddIndex] = val;
oddIndex = oddIndex + 2;
}
}
return result;
}
Time and Space Complexity nomenclature: n is the total number of elements in an array.
Time Complexity: O(n) as we have to traverse all elements in the array.
Space Complexity: O(n) as we are using auxiliary space.
4. O(1) Space solution
Idea is to move from left to right(even index) and right to left(odd index). Move the index by 2 places only if the current element is even. Same with the odd index. Now if both indexes cross each other, then all the elements are in the proper place. If they don’t cross, then there is a pair that needs to be swapped.
public int[] sortArrayByParityII(int[] nums) {
int evenIndex = 0, oddIndex = nums.length - 1;
while (evenIndex < nums.length && oddIndex >= 0) {
// Skip all even numbers that are in the proper place.
while (evenIndex < nums.length && nums[evenIndex] % 2 == 0)
evenIndex = evenIndex + 2;
// Skip all odd numbers that are in the proper place.
while (oddIndex >= 0 && nums[oddIndex] % 2 != 0)
oddIndex = oddIndex - 2;
// If all indexes are covered then numbers are
// in the proper place.
if (oddIndex < 0 || evenIndex >= nums.length) break;
// If we reached at this point then there
// exists even and odd number pair that need
// to be placed in the right place.
int temp = nums[evenIndex];
nums[evenIndex] = nums[oddIndex];
nums[oddIndex] = temp;
}
return nums;
}
5. Conclusion
In this article, we saw how to sort an array by parity where the odd numbers should be in the odd index and even numbers should be in the even index.