Sort Array By Parity II

🏠 ⬅️ ➡️

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] would also have been accepted.

Example 2:

Input: nums = [2,3] Output: [2,3]

Constraints:

  • 2 <= nums.length <= 2 * 104
  • nums.length is even.
  • Half of the integers in nums are even.
  • 0 <= nums[i] <= 1000

Follow Up: Could you solve it in-place?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, n, nums(4)

    ! Examples
    n = 4
    nums = (/ 4, 2, 5, 7 /)
    call sort_array(n, nums)
    write (*, '(A, I0, A, 4I0)') 'Example 1: ', n, ' -> ', nums

    n = 2
    nums = (/ 2, 3 /)
    call sort_array(n, nums)
    write (*, '(A, I0, A, 2I0)') 'Example 2: ', n, ' -> ', nums

contains

    subroutine sort_array(n, nums)
        implicit none
        integer, intent(inout) :: n
        integer, intent(inout) :: nums(:)
        integer :: i, j, temp

        do i = 1, n - 1
            do j = i + 1, n
                if (mod(nums(i), 2) == 0 .neqv. mod(j, 2) == 0) then
                    temp = nums(i)
                    nums(i) = nums(j)
                    nums(j) = temp
                end if
            end do
        end do
    end subroutine sort_array

end program main
❌ Compiled
❌ Executed
❌ Correct 
module sort_array
    implicit none
    private
    public :: sort_array
contains
    subroutine sort_array(nums)
        implicit none
        integer, intent(inout) :: nums(:)
        integer :: i, j, temp

        ! Loop through the array and swap odd and even elements
        do i = 1, size(nums) - 1
            if (mod(nums(i), 2) == 0) then
                do j = i + 1, size(nums)
                    if (mod(nums(j), 2) /= 0) then
                        temp = nums(i)
                        nums(i) = nums(j)
                        nums(j) = temp
                        exit
                    end if
                end do
            end if
        end do
    end subroutine sort_array
end module sort_array

program test_sort_array
    use sort_array
    implicit none
    integer, parameter :: nums(4) = [4, 2, 5, 7]
    integer :: i

    call sort_array(nums)

    do i = 1, size(nums)
        write (*,*) nums(i)
    end do
end program test_sort_array
🌐 Data from online sources 
from collections import defaultdict


def possible_bipartition(n, dislikes):
    def dfs(person, group):
        if person in groups:
            return groups[person] == group
        groups[person] = group
        for other in dislike_list[person]:
            if not dfs(other, -group):
                return False
        return True

    groups = {}
    dislike_list = defaultdict(list)
    for p1, p2 in dislikes:
        dislike_list[p1].append(p2)
        dislike_list[p2].append(p1)

    for person in range(1, n + 1):
        if person not in groups and not dfs(person, 1):
            return False

    return True

The problem can be modeled as a graph where each person is a node and dislikes are edges between nodes. We need to color the graph using two colors (or groups) such that if there is an edge between the nodes, they must have different colors. This is possible if and only if the graph is bipartite.

We can use Depth First Search (DFS) to check if the graph is bipartite. Start with an uncolored node, color it with group 1, and move to its neighbors. Each neighbor gets the opposite color (group) of the current node. If we find a node that has already been colored and it has the same color as the current node, then the graph is not bipartite, and we return false. If all nodes are successfully colored, the graph is bipartite, and we return true. The time complexity is O(n + e), where n is the number of nodes (people) and e is the number of edges (dislikes).

🌐 Data from online sources 
#include <vector>
using namespace std;

bool dfs(int person, int group, vector<int> &groups, vector<vector<int>> &dislikeList) {
    if (groups[person] != 0) {
        return groups[person] == group;
    }
    groups[person] = group;
    for (int other : dislikeList[person]) {
        if (!dfs(other, -group, groups, dislikeList)) {
            return false;
        }
    }
    return true;
}

bool possible_bipartition(int n, vector<vector<int>> &dislikes) {
    vector<int> groups(n + 1, 0);
    vector<vector<int>> dislikeList(n + 1);

    for (auto &dislikePair : dislikes) {
        dislikeList[dislikePair[0]].push_back(dislikePair[1]);
        dislikeList[dislikePair[1]].push_back(dislikePair[0]);
    }

    for (int person = 1; person <= n; person++) {
        if (groups[person] == 0 && !dfs(person, 1, groups, dislikeList)) {
            return false;
        }
    }

    return true;
}

The problem can be modeled as a graph where each person is a node and dislikes are edges between nodes. We need to color the graph using two colors (or groups) such that if there is an edge between the nodes, they must have different colors. This is possible if and only if the graph is bipartite.

We can use Depth First Search (DFS) to check if the graph is bipartite. Start with an uncolored node, color it with group 1, and move to its neighbors. Each neighbor gets the opposite color (group) of the current node. If we find a node that has already been colored and it has the same color as the current node, then the graph is not bipartite, and we return false. If all nodes are successfully colored, the graph is bipartite, and we return true. The time complexity is O(n + e), where n is the number of nodes (people) and e is the number of edges (dislikes).