Sort Array By Parity
Problem Statement
Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.
Return any array that satisfies this condition.
Examples
Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Input: nums = [0]
Output: [0]
Constraints
1 <= nums.length <= 5000
0 <= nums[i] <= 5000
Brute Force Approach
What comes to your mind, when you read this problem, the first thought that likely comes to mind is the task of separating even and odd numbers while keeping the implementation simple.
This approach handles the problem by taking advantage of the fact that you can traverse the input array multiple times if necessary.
This approach solves the problem by going through the input array twice. In the first step, you look for all the even numbers and add them to a new list. Since even numbers come first in the result, they are handled first.
In the second step, you go through the array again to find all the odd numbers and add them to the same list after the even numbers.
This way, the result will have all the even numbers first, followed by all the odd numbers, in the right order.
Example
Let's take the example input: nums = [3, 1, 2, 4]
Step 1: Adding Even Numbers
- The first iteration (to collect even numbers): At the end of the first loop, the result contains: result = [2, 4]
- We loop through the nums array:
- nums[0] = 3: 3 % 2 != 0 (odd), so we don't add it to the result.
- nums[1] = 1: 1 % 2 != 0 (odd), so we don't add it to the result.
- nums[2] = 2: 2 % 2 == 0 (even), so we add 2 to the result.
- nums[3] = 4: 4 % 2 == 0 (even), so we add 4 to the result.
Step 2: Adding Odd Numbers
- Second iteration (to collect odd numbers): After the second loop, result contains: result = [2, 4, 3, 1]
- We loop through the nums array again:
- nums[0] = 3: 3 % 2 != 0 (odd), so we add 3 to the result.
- nums[1] = 1: 1 % 2 != 0 (odd), so we add 1 to the result.
- nums[2] = 2: 2 % 2 == 0 (even), so we don't add it to the result (already added in the first loop).
- nums[3] = 4: 4 % 2 == 0 (even), so we don't add it to the result (already added in the first loop).
Step 3: Returning the Result
Finally, the function returns the result vector, which now contains:
result = [2, 4, 3, 1]
Steps to write Code
Step 1: Initialize the Variables:
- Input size: Store the size of the nums array. This will be used to iterate over the array.
- Result container: Declare an empty vector result to store the final output (sorted array).
Step 2: First Loop - Collect Even Numbers:
- Iterate through the nums array:
- For each element, check if it is even (i.e., num % 2 == 0).
- If the number is even, add it to the result vector.
Step 3: Second Loop - Collect Odd Numbers:
- After collecting all even numbers, iterate through the nums array again:
- For each element, check if it is odd (i.e., num % 2 != 0).
- If the number is odd, add it to the result vector.
Step 4: Return the Result:
- Once both even and odd numbers have been added to the result array, return the result array.
Code for All Languages
C++
class Solution {
public:
// Function to sort the array by parity
vector<int> sortArrayByParity(vector<int>& nums) {
// Store the size of the input vector
int size = nums.size();
// Declare a vector to store the result (sorted array)
vector<int> result;
// Traverse the array to add all even numbers to the result vector
for (int i = 0; i < size; i++) {
// Check if the current number is even
if (nums[i] % 2 == 0) {
// Add the even number to the result vector
result.push_back(nums[i]);
}
}
// Traverse the array again to add all odd numbers to the result vector
for (int i = 0; i < size; i++) {
// Check if the current number is odd
if (nums[i] % 2 == 1) {
// Add the odd number to the result vector
result.push_back(nums[i]);
}
}
// Return the result vector containing even numbers followed by odd numbers
return result;
}
};
Java
class Solution {
public int[] sortArrayByParity(int[] nums) {
// Create a result array of the same length as the input array
int[] result = new int[nums.length];
// Initialize an index variable to keep track of the position in the result array
int index = 0;
// First pass: Add all even numbers to the result array
for (int num : nums) {
// Check if the current number is even
if (num % 2 == 0) {
// Place the even number at the current index and increment the index
result[index++] = num;
}
}
// Second pass: Add all odd numbers to the result array
for (int num : nums) {
// Check if the current number is odd
if (num % 2 != 0) {
// Place the odd number at the current index and increment the index
result[index++] = num;
}
}
// Return the result array containing even numbers followed by odd numbers
return result;
}
}
Python
class Solution(object):
def sortArrayByParity(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# Create an empty list to store the result
result = []
# First pass: Add all even numbers to the result list
for num in nums:
# Check if the current number is even
if num % 2 == 0:
# Append the even number to the result list
result.append(num)
# Second pass: Add all odd numbers to the result list
for num in nums:
# Check if the current number is odd
if num % 2 != 0:
# Append the odd number to the result list
result.append(num)
# Return the result list containing even numbers followed by odd numbers
return result
Javascript
/**
* @param {number[]} nums - Array of integers to be sorted by parity
* @return {number[]} - New array with even numbers first, followed by odd numbers
*/
var sortArrayByParity = function(nums) {
// Initialize an empty array to store the result
const result = [];
// First pass: Add all even numbers to the result array
for (let num of nums) {
// Check if the current number is even
if (num % 2 === 0) {
// Append the even number to the result array
result.push(num);
}
}
// Second pass: Add all odd numbers to the result array
for (let num of nums) {
// Check if the current number is odd
if (num % 2 !== 0) {
// Append the odd number to the result array
result.push(num);
}
}
// Return the result array containing even numbers followed by odd numbers
return result;
};
Time Complexity: O(n)
Here’s how we can analyze the time complexity:
- First Loop (Collecting Even Numbers):
- We iterate through each element of the array once to check if it is even.
- For each element, the condition to check if the number is even (num % 2 == 0) takes constant time, O(1).
- If the number is even, we add it to the result vector. The push_back operation for vectors generally takes O(1) time on average.
- Therefore, this loop runs once for each element of the array, resulting in a time complexity of O(n), where n is the size of the input array.
- Second Loop (Collecting Odd Numbers):
- After the first loop, we need to traverse the array again to collect the odd numbers.
- Similar to the first loop, for each element, the condition to check if the number is odd (num % 2 == 1) is evaluated in constant time, O(1).
- If the number is odd, it is added to the result vector, which takes O(1) time on average.
- This loop also runs once for each element of the array, contributing another O(n) to the overall time complexity.
Total Time Complexity:
- The first loop runs in O(n) time.
- The second loop also runs in O(n) time.
- Therefore, the total time complexity is O(n)+O(n)=O(2n).
Since constant factors are ignored in Big-O notation, the total time complexity simplifies to: O(n)
Space Complexity: O(n)
Components of Space Complexity:
- Input Array (nums):
- The input array nums is passed to the function, but it is not modified or duplicated, so it doesn't count towards additional space usage. The input size is O(n), but since it's given as input, we don't consider this as extra space in our analysis.
- Result Vector (result):
- The main extra space used in this solution is the result vector, which stores the sorted array by parity (even numbers followed by odd numbers).
- The result vector will eventually contain all the elements from the input array, as it stores both even and odd numbers. So, the size of the result vector will be the same as the size of the input array, which is n.
- The space used by the result vector is O(n) because it holds all the elements of the input array.
- Auxiliary Variables:
- In the code, a few variables are declared, such as size, used for tracking the size of the input array. These are simple integer variables, which take up constant space, O(1).
- The space taken by these auxiliary variables is insignificant in comparison to the space taken by the result vector.
Total Space Complexity:
- The only significant extra space used is the result vector, which takes O(n) space to store the output.
- The auxiliary variables take constant space, O(1).
Thus, the total space complexity is: O(n)
Does brute Force will run under given constraints
For n≤5000, our solution has a time complexity of O(n), which will comfortably meet the given constraints. This is well within the time limits of most competitive programming environments, which typically allow around 1-2 seconds for execution.
In such environments, it is common for problems to handle up to 10⁶ operations within these limits. Most competitive programming platforms, like LeetCode, allow up to 10⁶ operations per test case, meaning this solution should be able to handle the required number of operations efficiently.
When multiple test cases are involved, the total number of operations can go up to 10⁸. Thus, the O(n) time complexity is optimal and works efficiently even with the maximum input size of n=5000, ensuring the solution runs within the acceptable time frame without risking a Time Limit Exceeded (TLE) error.
Optimal Approach
In the brute-force method, we traverse the input array twice. In the first pass, we identify all the even numbers and copy them to a new result array. In the second pass, we do the same for odd numbers. This approach works well but has a drawback—it requires additional space proportional to the size of the input array (O(n) space complexity). While the logic is simple, the extra space can be a limitation, especially for large arrays.
If we carefully observe, the sorting of the array by parity doesn’t require us to maintain the relative order of the even and odd numbers. The only condition is that all even numbers appear before the odd ones. This means we can reorder the input array directly instead of creating a new one.
To solve the problem in-place (without extra space), we need a way to partition the array so that all even numbers are moved to the front and all odd numbers are moved to the back. This is where the two-pointer technique comes into play.
The idea behind this approach is to use two pointers to efficiently rearrange the array. One pointer, currentIndex, iterates through the array from start to finish, while another pointer, evenIndex, keeps track of the position where the next even number should be placed.
As we traverse the array, whenever an even number is encountered at currentIndex, we swap it with the number at evenIndex. This ensures that the even number is moved to the front of the array, and evenIndex is incremented to the next available position for an even number.
If the current number is odd, no action is taken, and we simply move to the next index. This approach works because the evenIndex guarantees that all numbers before it are even, and swapping an even number into this position does not disturb the order of the odd numbers that are yet to be processed.
By the time the iteration is complete, all even numbers have been shifted to the front, while the odd numbers naturally remain at the back of the array, achieving the desired arrangement efficiently and in-place.
Example
Input: nums = [3, 1, 2, 4]
- Initialization:
- We initialize evenIndex = 0, which points to the position where the next even number should be placed.
- We start iterating over the array with currentIndex = 0, which traverses the array from left to right.
- First iteration (currentIndex = 0):
- The current element is nums[0] = 3.
- Since 3 is odd, we do nothing and simply move to the next element by incrementing currentIndex.
- Array remains: [3, 1, 2, 4].
- Second iteration (currentIndex = 1):
- The current element is nums[1] = 1.
- Since 1 is odd, we do nothing and move to the next element by incrementing currentIndex.
- Array remains: [3, 1, 2, 4].
- Third iteration (currentIndex = 2):
- The current element is nums[2] = 2.
- Since 2 is even, we swap nums[evenIndex] with nums[currentIndex]. Here, evenIndex = 0 and currentIndex = 2.
- We swap nums[0] (which is 3) with nums[2] (which is 2).
- After the swap, the array becomes: [2, 1, 3, 4].
- We increment the evenIndex to 1, indicating that the next even number should go to the index 1.
- We move to the next element by incrementing currentIndex.
- Fourth iteration (currentIndex = 3):
- The current element is nums[3] = 4.
- Since 4 is even, we swap nums[evenIndex] with nums[currentIndex]. Here, evenIndex = 1 and currentIndex = 3.
- We swap nums[1] (which is 1) with nums[3] (which is 4).
- After the swap, the array becomes: [2, 4, 3, 1].
- We increment evenIndex to 2, and since we've finished processing all elements, we end the loop.
Final Output: After completing the loop, the array has been reordered such that all even numbers come before all odd numbers.
The final result is: [2, 4, 3, 1].
Steps to write Code
Step 1: Initialize Variables
- Declare evenIndex = 0. This will be the index where the next even number should go.
- Use currentIndex to iterate through the array. It will start from 0 and go up to n-1.
Step 2: Iterate Through the Array
- Use a for loop to iterate through the array, using currentIndex to traverse each element.
- If the element at nums[currentIndex] is even, swap it with the element at nums[evenIndex], and increment evenIndex.
Step 3: Return the Result
After iterating through the array, return the modified array.
Code for All Languages
C++
class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
// Initialize n as the size of the input array
int n = nums.size();
// Pointer to track the position where the next even number should be placed
int evenIndex = 0;
for (int currentIndex = 0; currentIndex < n; currentIndex++) {
// If the current number is even, swap it with the number at the evenIndex position
if (nums[currentIndex] % 2 == 0) {
swap(nums[evenIndex++], nums[currentIndex]);
}
}
// Return the modified array
return nums;
}
};
Java
class Solution {
public int[] sortArrayByParity(int[] nums) {
// Initialize n as the size of the input array
int n = nums.length;
// Pointer to track the position where the next even number should be placed
int evenIndex = 0;
for (int currentIndex = 0; currentIndex < n; currentIndex++) {
// If the current number is even, swap it with the number at the evenIndex position
if (nums[currentIndex] % 2 == 0) {
int temp = nums[evenIndex];
nums[evenIndex] = nums[currentIndex];
nums[currentIndex] = temp;
evenIndex++;
}
}
// Return the modified array
return nums;
}
}
Python
class Solution:
def sortArrayByParity(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
# Initialize n as the length of the input array
n = len(nums)
# Pointer to track the position where the next even number should be placed
even_index = 0
for current_index in range(n):
# If the current number is even, swap it with the number at the even_index position
if nums[current_index] % 2 == 0:
nums[even_index], nums[current_index] = nums[current_index], nums[even_index]
even_index += 1
# Return the modified array
return nums
Javascript
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArrayByParity = function(nums) {
// Initialize n as the length of the input array
let n = nums.length;
// Pointer to track the position where the next even number should be placed
let evenIndex = 0;
for (let currentIndex = 0; currentIndex < n; currentIndex++) {
// If the current number is even, swap it with the number at the evenIndex position
if (nums[currentIndex] % 2 === 0) {
[nums[evenIndex], nums[currentIndex]] = [nums[currentIndex], nums[evenIndex]];
evenIndex++;
}
}
// Return the modified array
return nums;
};
Time Complexity: O(1)
- Initialization:
- We initialize a variable to keep track of the position where the next even number should be placed (called evenIndex).
- This operation is constant time O(1), as we're only initializing a single variable.
- Loop Over the Array:
- We iterate through the array exactly once using a pointer (currentIndex).
- For each element in the array, we check if it's even (using the modulo operation). This check is a constant-time operation (O(1)).
- If the current element is even, we swap it with the element at evenIndex and then move the evenIndex to the next position. Both the swap operation and the increment of evenIndex are constant-time operations (O(1)).
Total Time Complexity: O(1)
Space Complexity: O(1)
- Auxiliary Space:
- Variables:
- evenIndex and currentIndex are the only extra variables used by the algorithm.
- These are both integer variables, which consume constant space regardless of the size of the input array.
- No Additional Data Structures:
- The algorithm modifies the input array nums in place, meaning it does not use any additional arrays or complex data structures (like stacks, queues, lists, etc.).
So, the total auxiliary space is O(1), since only a constant amount of space is used for storing these variables.
2. Total Space:
Total space includes:
- The space used by the input data.
- The auxiliary space used by the algorithm.
- Input Array (nums):
- The input array nums is passed into the function and is modified directly. The space used by nums is not counted in the auxiliary space, but it is part of the total space complexity.
Since the input array nums is the only large memory-consuming element, the space complexity for the input array is O(n), where n is the size of the array.
Total Space Complexity:
- The total space complexity is the sum of the space for the input data and the auxiliary space used by the algorithm.
- Input data space is O(n), and auxiliary space is O(1).
Therefore, the total space complexity is: O(n)+O(1)=O(n)
Key Takeaways
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.
You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.
You should return the array of nums such that the the array follows the given conditions:
- Every consecutive pair of integers have opposite signs.
- For all integers with the same sign, the order in which they were present in nums is preserved.
- The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.