Sort Array By Parity LeetCode Solution

Problem Statement

The Sort Array By Parity LeetCode Solution – “Sort Array By Parity” states that you are given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Note: Return any array that satisfies this condition.

Example:

Input:

Output:

All the even numbers of array (2, 4, 6) moved to the beginning while the odd numbers (3, 1, 5) of array are placed at the end.

Note: There could be other outputs as well {4, 2, 6, 1, 3, 5}, {6, 4, 2, 3, 5, 1}, etc.

Brute Force

Approach: Traverse the given input array nums, if number found to be as even we will place it in new output array and increment the array pointer. Traverse the given input array again, if number found to be as odd we will start placing them in output array from where the last even number is placed.

Code:

C++ Program of Sort Array By Parity

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        vector<int> output;
        for (auto it = nums.begin(); it != nums.end(); it++)
        {
            if((*it) % 2 == 0)
                output.push_back(*it);
        }
  	    for (auto it = nums.begin(); it != nums.end(); it++)
        {
            if((*it) % 2 != 0)
                output.push_back(*it);
        }
        return output;
    }
};

Java Program of Sort Array By Parity

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int result[]; 
        int p = 0;
        
        result = new int[nums.length];

        for (int i = 0; i < nums.length; i++)
            if (nums[i] % 2 == 0)
            {
                result[p] = nums[i];
                p++;
            } 
                
        for (int i = 0; i < nums.length; i++)
            if (nums[i] % 2 != 0)
            {
                result[p] = nums[i];
                p++;
            } 

        return result;
    }
}

Complexity Analysis

Time Complexity

Time Complexity of above code is O(2n) which is O(n) as we are traversing the array twice.

Space Complexity

Space Complexity of above code is O(n) as we are using a separate array to store the result.

Optimized Solution

Approach: We will use a two pointer approach left and right, where left is initialized to 0 while right is initialized to arr_size – 1.

Traverse an array from start:

• If number is odd swap it nums[right] and decrement the right pointer
• If number is even just increment the left pointer

Code:

C++ Program of Sort Array By Parity LeetCode Solution

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        
        int left = 0;
        int right = nums.size() - 1;

        while(left < right )
        {
            if(nums[left] % 2 != 0)
            {
                swap(nums[left], nums[right--]);
            }
            else
            {
                left++;
            }

        }
    return nums;
    }
};

Java Program of Sort Array By Parity LeetCode Solution

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0; 
        int right = nums.length - 1; 
        while(left < right ) 
        { 
            if(nums[left] % 2 != 0) 
            { 
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
                right--;
            } 
            else 
            { 
                left++; 
            } 
        }
        return nums;
    }
}

Complexity Analysis

Time Complexity

Time Complexity of above code is O(n) as in this approach are traversing the array only once.

Space Complexity

Space Complexity of above code is O(1) as no additional space is required.

Reference: https://algodaily.com/lessons/using-the-two-pointer-technique