Sort Array By Parity in Java | Programming Tutorial | LeetCode Problem

Sort Array as Odd numbers followed by Even numbers in Java | Sort array as store All even numbers first and all Odd numbers last.

Given an array of non-negative integers, return an array consisting of all the even elements of array followed by all the odd elements of array.

You may return any answer array that satisfies this condition.

Example 1 :-

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

See description in Leetcode :-

• Sort Array By Parity 
  

So lets see solution of above problem.

Solution 1 : In place with For loop

class Solution {
    public int[] sortArrayByParity(int[] array) {
        if (array.length > 1) {
            int rightIndex = array.length - 1;

            for (int leftIndex = 0; leftIndex < array.length;) {
                
                if (array[leftIndex] % 2 != 0 && array[rightIndex] % 2 == 0) {
                    int temp = array[leftIndex];
                    array[leftIndex] = array[rightIndex];
                    array[rightIndex] = temp;
                }
                
                if (rightIndex <= (leftIndex+1)) {
                    break;
                }
                
                if (array[leftIndex] % 2 == 0) {
                    leftIndex++;
                } 
                
                if (array[rightIndex] % 2 != 0) {
                    rightIndex--;
                }
                
            }
        }
        return array;
    }
} 

Solution Explanation :-

• In first condition check if array is greater than 1 or not. If it is greater than 1 then we are going inside.
• Declare one variable rightIndex and initialize with last array index value.
• Traverse array from left to right till array length.
• Now we want all Even numbers at left side and all odd numbers at right side in array so In if condition, check first array value is odd and last array value is even or not. If both condition becomes true then we swap both values.
• In second if condition, we are checking rightIndex is crossed by leftIndex or not. If it crossed that means our array is sorted and break the for loop.
• In third if, check leftIndex value is even or not. if it is even then we move to next index (leftIndex++).
• In fourth if, check rightIndex value is odd or not. if it is odd then move to previous index (Traverse array right to left).

Output Explanation :-

array = [3, 1, 2, 4]

• array.length > 1 becomes true.
• rightIndex = 3, leftIndex = 0
• array[0] % 2 != 0 && array[3] % 2 == 0 becomes true.
• First if | Swap both values. array = [4, 1, 2, 3]
• Second if | 3 <= 0 becomes false
  
• Third if | 4 % 2 == 0 becomes true. leftIndex = 1
• Fourth if | 3 % 2 != 0 becomes true. rightIndex = 2
  
  
• array = [4, 1, 2, 3], rightIndex = 2, leftIndex = 1
•  array[1] % 2 != 0 && array[2] % 2 == 0 becomes true.
• First if | Swap both values. array = [4, 2, 1, 3]
• Second if | 2 <= 2 becomes true. and break the for loop.
  
  
• array = [4, 2, 1, 3]

In above solution we are using for loop, in next solution let's try with while loop.

Solution 2 : In place with While loop

class Solution {
    
    public int[] sortArrayByParity(int[] array) {
        int leftIndex = 0, rightIndex = array.length - 1;
        while (leftIndex < rightIndex) {
            if (array[leftIndex] % 2 > array[rightIndex] % 2) {
                int temp = array[leftIndex];
                array[leftIndex] = array[rightIndex];
                array[rightIndex] = temp;
            }

            if (array[leftIndex] % 2 == 0) leftIndex++;
            if (array[rightIndex] % 2 == 1) rightIndex--;
        }

        return array;
    }
}

We can also solve this problem by using another empty array. So basically we can traverse through given array and check it is Even number or Odd number, based on that we can store values in newly array. 

So let's see how we can achieve that.

Solution 3 : Using extra array

class Solution {
    public int[] sortArrayByParity(int[] array) {
        int[] ans = new int[array.length];

        int leftIndex = 0;
        int rightIndex = array.length - 1;

        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                ans[leftIndex++] = array[i];
            } else {
                ans[rightIndex--] = array[i];
            }
        }

        return ans;
    }
}

Explanation :-

• In this solution, we are declare and creating new array same as old array length.
• Take two variables, leftIndex assign with 0 and rightIndex assign with array's last index.
• Traverse array from left to right.
• In if condition, check number is Even. If it is even then assign that value to newly created array at leftIndex. otherwise it is Odd value and assign value based on rightIndex.