Skip to content

905. Sort Array By Parity

Description

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.

 

Example 1:

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.

Example 2:

Input: nums = [0]
Output: [0]

 

Constraints:

  • 1 <= nums.length <= 5000
  • 0 <= nums[i] <= 5000

Solutions

Solution 1: Two Pointers

Thinking

Even numbers should precede odds; relative order is free. An extra array would work, but the permutation can be done in place. Two pointers move inward: advance the left on an even, the right on an odd, otherwise swap. Each index is visited a constant number of times.

We use two pointers \(i\) and \(j\) to point to the beginning and end of the array respectively. When \(i < j\), we perform the following operations.

  • If \(nums[i]\) is even, then increment \(i\) by \(1\).
  • If \(nums[j]\) is odd, then decrement \(j\) by \(1\).
  • If \(nums[i]\) is odd and \(nums[j]\) is even, then swap \(nums[i]\) and \(nums[j]\). Then increment \(i\) by \(1\), and decrement \(j\) by \(1\).

Finally, return the array \(nums\).

The time complexity is \(O(n)\), where \(n\) is the length of the array \(nums\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] % 2 == 0:
                i += 1
            elif nums[j] % 2 == 1:
                j -= 1
            else:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            if (nums[i] % 2 == 0) {
                ++i;
            } else if (nums[j] % 2 == 1) {
                --j;
            } else {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
                ++i;
                --j;
            }
        }
        return nums;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& nums) {
        int i = 0, j = nums.size() - 1;
        while (i < j) {
            if (nums[i] % 2 == 0) {
                ++i;
            } else if (nums[j] % 2 == 1) {
                --j;
            } else {
                swap(nums[i++], nums[j--]);
            }
        }
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func sortArrayByParity(nums []int) []int {
    for i, j := 0, len(nums)-1; i < j; {
        if nums[i]%2 == 0 {
            i++
        } else if nums[j]%2 == 1 {
            j--
        } else {
            nums[i], nums[j] = nums[j], nums[i]
        }
    }
    return nums
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function sortArrayByParity(nums: number[]): number[] {
    for (let i = 0, j = nums.length - 1; i < j;) {
        if (nums[i] % 2 === 0) {
            ++i;
        } else if (nums[j] % 2 === 1) {
            --j;
        } else {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            ++i;
            --j;
        }
    }
    return nums;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn sort_array_by_parity(mut nums: Vec<i32>) -> Vec<i32> {
        let (mut i, mut j) = (0, nums.len() - 1);
        while i < j {
            if nums[i] % 2 == 0 {
                i += 1;
            } else if nums[j] % 2 == 1 {
                j -= 1;
            } else {
                nums.swap(i, j);
                i += 1;
                j -= 1;
            }
        }
        nums
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArrayByParity = function (nums) {
    for (let i = 0, j = nums.length - 1; i < j;) {
        if (nums[i] % 2 === 0) {
            ++i;
        } else if (nums[j] % 2 === 1) {
            --j;
        } else {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            ++i;
            --j;
        }
    }
    return nums;
};

Comments