922. Sort Array By Parity II

Problem Description

The problem presents us with an array named nums containing an equal number of odd and even integers. The task is to arrange this array in such a way that the parity of the elements matches the parity of their indices. In essence, all the even-indexed positions must contain even numbers, and all the odd-indexed positions must be filled with odd numbers. The challenge is to figure out a way to reorder the array to meet this requirement, knowing that there is at least one way to achieve it because of the even distribution of odd and even numbers.

Intuition

The approach to solving this problem involves in-place reordering of the elements to meet our even-odd position requirements. Since we know half the numbers are even and half are odd, we understand that there must be a correct place for each number in the 'reordered' array. The intuition is to iterate over the even indices and whenever we encounter an odd number at an even index, we search for an even number at an odd index to swap with. This is why we have a secondary pointer j starting at index 1, the first odd index, and it moves in steps of 2 (to remain at odd indices). Every time we find an even number at an odd index, we swap it with the mispositioned odd number we found at the even index.

This swapping continues until all even indices hold even numbers (and thus, all odd indices hold odd numbers) since we are swapping odd for even, maintaining the parity balance. Once we're done with the loop, every even index i will have an even number and ever odd index will have an odd number, resulting in an array that satisfies the conditions of the problem.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution provided uses a two-pointer approach to rearrange the array such that even-indexed elements are even, and odd-indexed elements are odd. The algorithm iterates through the array with these key steps:

We initialize two pointers, i and j. Here i starts at index 0 (the first even index) and will be incremented by 2 in each iteration to ensure it only points to even indices. Pointer j starts at index 1 (the first odd index) and will be moved in increments of 2 to jump to the next odd index when needed.
We loop over the array with i up to n (n being the length of the array), making steps of size 2.
At each iteration, we check if the number at index i is odd by observing the last bit nums[i] & 1. If it is equal to 1, it indicates that the number is odd and is in the wrong position since i is even.
When an odd number is observed at an even index i, we look for an even number at an odd index j. We perform an inner while loop to move j forward until we find an even number (also checking the last bit nums[j] & 1).
As soon as an even number is found at an odd index j, we swap the elements at indexes i and j. This is done using Python's tuple unpacking feature: nums[i], nums[j] = nums[j], nums[i].
The loop continues until i reaches the end of the array. At this point, all the even indices have even numbers due to our swapping mechanism, which ensures that every time we encounter a number out of place, we switch it with its corresponding pair.

No additional data structures are needed, and the in-place algorithm performs swaps only when necessary. This leads to a space complexity of O(1) and a time complexity that is O(n) since each element is looked at once and each odd index is evaluated at most once.

The elegance of this solution comes from recognizing that, given the constraints, for every mispositioned odd number at an even index, there must exist a mispositioned even number at an odd index that we can swap it with. Through careful stepping of the i and j pointers and efficient swapping, we're able to rearrange the array as needed without the use of any extra space.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use the following small example to illustrate the solution approach:

Consider the array nums = [3, 6, 1, 4, 7, 2]. Here, we have an equal number of odd and even integers. The even indices are 0, 2, 4, and they should have even numbers, while the odd indices 1, 3, 5 should have odd numbers.

Following the steps from the solution approach:

Initialize two pointers: i (starting at 0) and j (starting at 1).
Begin looping over the array with i going from 0 to the length of the array, incremented by 2.
On the first iteration: i is 0 and j is 1.
- nums[i] is 3, which is odd (3 & 1 equals 1), so it's out of place.
Now, we need to find an even number at an odd index j to swap with nums[i]. Since j is already at an odd index and nums[j] is 6, which is even (6 & 1 equals 0), we don't need to move j.
Swap the elements at indices i and j. After swapping, nums becomes [6, 3, 1, 4, 7, 2].
Increment i by 2. Now, i is 2.
- nums[i] is 1, which is odd and out of place at an even index.
Increment j by 2 to find the next even number. Now j is 3.
- nums[j] is 4, which is even.
Swap the elements at indices i and j. The array nums is now [6, 3, 4, 1, 7, 2].
Increment i by 2. Now, i is 4.
- nums[i] is 7, which is odd and incorrectly placed at an even index.
Increment j by 2 to move to the next odd index. Now j is 5.
- nums[j] is 2, which is even.
Swap the elements at indices i and j. The array nums is now [6, 3, 4, 1, 2, 7].

Now each even index (0, 2, 4) has even numbers and each odd index (1, 3, 5) has odd numbers. The process is complete and the array nums is successfully reordered. The result is an array where the parity of the elements matches the parity of their indices, thus [6, 3, 4, 1, 2, 7].

Solution Implementation

1class Solution:
2    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
3        # Get the length of the input list
4        length = len(nums)
5        # Initialize 'odd_index' to the first odd position
6        odd_index = 1
7      
8        # Iterate through all even indices of the list
9        for even_index in range(0, length, 2):
10            # Check if the current even position contains an odd number
11            if nums[even_index] % 2 == 1:
12                # Look for an even number at odd positions
13                while nums[odd_index] % 2 == 1:
14                    # Increase 'odd_index' by 2 to check the next odd position
15                    odd_index += 2
16              
17                # Swap the odd number at the even index with the even number at the odd index
18                nums[even_index], nums[odd_index] = nums[odd_index], nums[even_index]
19      
20        # Return the sorted by parity list
21        return nums
22

1class Solution {
2    public int[] sortArrayByParityII(int[] nums) {
3        // i points to the next even index, j points to the next odd index
4        int i = 0; // i should index even elements
5        int j = 1; // j should index odd elements
6
7        // Iterate over the array, considering only even indices for i
8        while (i < nums.length) {
9            // If the number at the current even index is odd,
10            // we need to swap it with a number at an odd index.
11            if ((nums[i] & 1) != 0) {
12                // Find the next number that's out of place at an odd index
13                while ((nums[j] & 1) != 0) {
14                    j += 2;
15                }
16                // Swap the numbers at indices i and j
17                int temp = nums[i];
18                nums[i] = nums[j];
19                nums[j] = temp;
20            }
21            // Move to the next even index
22            i += 2;
23        }
24        // Return the sorted array with even indices containing even numbers
25        // and odd indices containing odd numbers
26        return nums;
27    }
28}
29

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to sort the array so that at every even index we have an even number,
7    // and at every odd index, we have an odd number.
8    vector<int> sortArrayByParityII(vector<int>& nums) {
9        // Traverse through the elements at even indices.
10        for (int evenIndex = 0, oddIndex = 1; evenIndex < nums.size(); evenIndex += 2) {
11            // Check if the current even index has an odd number.
12            if ((nums[evenIndex] & 1) == 1) {
13                // Find the odd index that has an even number.
14                while ((nums[oddIndex] & 1) == 1) {
15                    oddIndex += 2;
16                }
17                // Swap the odd number at an even index with the even number at an odd index.
18                swap(nums[evenIndex], nums[oddIndex]);
19            }
20        }
21        // Return the sorted array.
22        return nums;
23    }
24};
25

1/**
2 * Sorts an array such that every even-indexed element is even and every odd-indexed element is odd.
3 * @param {number[]} nums - The input array to be sorted in place.
4 * @returns {number[]} The sorted array.
5 */
6function sortArrayByParityII(nums: number[]): number[] {
7    // Initialize two pointers, `evenIndex` for even indexes and `oddIndex` for odd indexes.
8    let evenIndex: number = 0;
9    let oddIndex: number = 1;
10
11    // Iterate over the array through the even indexes.
12    while (evenIndex < nums.length) {
13        // Check if the current even index contains an odd value.
14        if ((nums[evenIndex] & 1) === 1) {
15            // If so, look for an even value at the odd index positions.
16            while ((nums[oddIndex] & 1) === 1) {
17                oddIndex += 2;
18            }
19            // Swap the values at `evenIndex` and `oddIndex` to satisfy the condition.
20            [nums[evenIndex], nums[oddIndex]] = [nums[oddIndex], nums[evenIndex]];
21        }
22      
23        // Move the `evenIndex` pointer to the next even position.
24        evenIndex += 2;
25    }
26
27    // Return the sorted array.
28    return nums;
29}
30
31// Usage example:
32// const sorted = sortArrayByParityII([4, 2, 5, 7]); 
33// console.log(sorted);
34

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n), where n is the length of the input list nums. This is because the outer loop runs for every second element (i.e., each even-indexed position), which results in n/2 iterations. Inside the loop, we check if the current even-indexed number is odd. If it is odd, we perform a while loop to find the next odd-indexed position that contains an odd number to swap with.

The key point to note here is that each odd number is moved at most once since after it is moved to an even index, it doesn't need to be moved again. Therefore, the while loop altogether will also run for a maximum of n/2 odd numbers throughout the entire execution of the algorithm.

Combining the outer and inner loop we still have a linear relationship with the number of elements n, leading to a total time complexity of O(n).

Space Complexity

The space complexity of the code is O(1) since only a fixed number of extra variables (n, j) are used, and these do not grow with the input size. The swaps are done in-place, which means no additional space proportional to the input size is required.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know