Check if Array can be sorted by swapping adjacent elements having odd sum

Given an array arr[], the task is to check if the array can be sorted using the given operation any number of times. In one operation, you can swap any two adjacent elements if their sum is odd.

Examples:

Input: arr[] = [1, 6, 31, 14]
Output: Yes
Explanation: Swap 31 and 14 (31 + 14 = 45 which is odd). The array will be [1, 6, 14, 31] which is sorted.

Input: arr[] = [4, 2]
Output: No
Explanation: Here no swap is possible. Hence the array can not be made sorted using the given operation.

Approach: To solve the problem follow the below idea:

Adjacent elements can only be swapped if they are of different parity. The given array can not be sorted if any element that is greater and of the same parity comes earlier in the array. So, If either the order of even elements or the order of odd elements is not non-decreasing, then it is impossible to sort the given array. We can made two separate arrays for storing even and odd elements and then can check either both of the arrays are in non-decreasing order or not separately.

Below are the steps for the above approach:

• Initialize two arrays/vectors say, even[] and odd[] that store even and odd elements respectively.
• Iterate the given array and check if arr[i] % 2 == 0, push the current element in the array even[], else push the current element in the array odd[].
• Check if both the arrays are separately in non-decreasing order, return true, else return false.

Below is the code for the above approach:

Time Complexity: O(N)
Auxiliary Space: O(N)

Given an array arr[], the task is to check if the array can be sorted using the given operation any number of times. In one operation, you can swap any two adjacent elements if their sum is odd.

Examples:

Input: arr[] = [1, 6, 31, 14]
Output: Yes
Explanation: Swap 31 and 14 (31 + 14 = 45 which is odd). The array will be [1, 6, 14, 31] which is sorted.

Input: arr[] = [4, 2]
Output: No
Explanation: Here no swap is possible. Hence the array can not be made sorted using the given operation.

Approach: To solve the problem follow the below idea:

Adjacent elements can only be swapped if they are of different parity. The given array can not be sorted if any element that is greater and of the same parity comes earlier in the array. So, If either the order of even elements or the order of odd elements is not non-decreasing, then it is impossible to sort the given array. We can made two separate arrays for storing even and odd elements and then can check either both of the arrays are in non-decreasing order or not separately.

Below are the steps for the above approach:

• Initialize two arrays/vectors say, even[] and odd[] that store even and odd elements respectively.
• Iterate the given array and check if arr[i] % 2 == 0, push the current element in the array even[], else push the current element in the array odd[].
• Check if both the arrays are separately in non-decreasing order, return true, else return false.

Below is the code for the above approach:

Time Complexity: O(N)
Auxiliary Space: O(N)