Leetcode 922. Sort Array By Parity II

Problem

The problem expects us to sort an array in such a way that odd numbers are at odd indices and even numbers are at even indices. Given that the array A contains an equal number of even and odd numbers, our task is to arrange these numbers accordingly to the given condition.

Let's walkthrough this with the given example:

Input: [4,2,5,7]

So in this array, 4 and 2 are at even indices (0 and 1) but 5 and 7 are at odd indices (2 and 3). We need to arrange them in such a way such that the final array would look something like [4,5,2,7]. Here all the even numbers (4 and 2) are at even indices and odd numbers (5 and 7) are at odd indices.

Approach Used

We need to iterate over the list, two indices at a time. The 'i' index will iterate over even indices and the 'j' index will iterate over odd indices. When we find a number at an even index that is odd, we continue iterating through the list with the 'j' index until we find an even number at an odd index. Once this condition is met, we switch the numbers at the odd and even indices. This ensures that our rule, requiring an odd number at an odd index and an even number is at even index, is maintained.

Python solution

1
2Python
3class Solution:
4    def sortArrayByParityII(self, nums):
5        even_pointer = 0  # pointer for even indexed number in the list
6        odd_pointer = 1   # pointer for odd indexed number in the list
7        size = len(nums)
8
9        while even_pointer < size and odd_pointer < size:
10            # continue if already even number at even indexed position
11            if nums[even_pointer] % 2 == 0:
12                even_pointer += 2
13            # continue if already odd number at odd indexed position
14            elif nums[odd_pointer] % 2 != 0:
15                odd_pointer += 2
16            else:
17                # swap even number at odd indexed position with odd number at even position
18                nums[even_pointer], nums[odd_pointer] = nums[odd_pointer], nums[even_pointer]
19                even_pointer += 2
20                odd_pointer += 2
21
22        return nums

Java solution

1
2Java
3class Solution {
4    public int[] sortArrayByParityII(int[] nums) {
5        int size = nums.length, even = 0, odd = 1;
6        
7        while(even < size && odd < size){
8            if(nums[even] % 2 == 0){
9                even += 2;
10            } else if(nums[odd] % 2 != 0){
11                odd += 2;
12            } else {
13                // swapping even number at odd indexed position with odd number at even position
14                int temp = nums[even];
15                nums[even] = nums[odd];
16                nums[odd] = temp;
17                even += 2;
18                odd += 2;
19            }
20        }
21        
22        return nums;
23    }
24}

Javascript Solution

1
2javascript
3var sortArrayByParityII = function(nums) {
4    let size = nums.length;
5    let even = 0, odd = 1;
6    
7    while(even < size && odd < size){
8        if(nums[even] % 2 === 0){
9            even += 2;
10        } else if(nums[odd] % 2 !== 0){
11            odd += 2;
12        } else {
13            // swapping even number at odd indexed position with odd number at even position
14            let temp = nums[even];
15            nums[even] = nums[odd];
16            nums[odd] = temp;
17            even += 2;
18            odd += 2;
19        }
20    }
21    
22    return nums;
23};

C++ Solution

1
2Cpp
3class Solution {
4public:
5    vector<int> sortArrayByParityII(vector<int>& nums) {
6        int size = nums.size(), even = 0, odd = 1;
7        
8        while(even < size && odd < size){
9            if(nums[even] % 2 == 0){
10                even += 2;
11            } else if(nums[odd] % 2 != 0){
12                odd += 2;
13            } else {
14                // swapping even number at odd indexed position with odd number at even position
15                swap(nums[even], nums[odd]);
16                even += 2;
17                odd += 2;
18            }
19        }
20        
21        return nums;
22    }
23};

C# Solution

1
2csharp
3public class Solution {
4    public int[] SortArrayByParityII(int[] nums) {
5        int size = nums.Length, even = 0, odd = 1;
6        
7        while(even < size && odd < size){
8            if(nums[even] % 2 == 0){
9                even += 2;
10            } else if(nums[odd] % 2 != 0){
11                odd += 2;
12            } else {
13                // swapping even number at odd indexed position with odd number at even position
14                int temp = nums[even];
15                nums[even] = nums[odd];
16                nums[odd] = temp;
17                even += 2;
18                odd += 2;
19            }
20        }
21        
22        return nums;
23    }
24}

Each solution uses pointer manipulation and the modulo operation to check if a number is even or odd and swap accordingly. The even index pointer increments by 2 to check even indexed elements, and the same is done for odd indexed elements with the odd index pointer.All the solutions have time complexity O(n) as we have to go through all the elements in the array in worst case scenario, and space complexity O(1) because we are using only constant extra space.

So this was how you can arrange the elements of an array such that the even numbers are positioned at even indices and the odd numbers are at odd indices without using any extra space. Use these techniques to optimise your sorting and arrangement algorithms!

This method demonstrates the interplay of a number of fundamental computer science and programming concepts:

1. Pointers/indices: Pointers or indices allow your program to manipulate the position, or "point" at which a piece of data is accessed, often in the context of a data structure like an array or list.
2. Modulo operation: The modulo operation is used to determine the remainder of a division operation. When used with 2 as the divisor, it can conveniently determine whether a number is even or odd.
3. Swapping values: Swapping is a common operation that exchanges the positions or values of two data points.
4. Loops and conditionals: Loops and conditionals (if-then-else statements) are fundamental control flow structures used in virtually all programming and algorithm contexts.

And there you have it! A simple, efficient, and elegant solution to our problem in Python, Java, JavaScript, C++, and C#. Whether you're preparing for a technical interview, participating in a coding competition, or just trying to expand your programming knowledge and skills, this technique will no doubt come in handy. Happy coding!