algoadvance

Leetcode 922. Sort Array By Parity II

Problem Statement

Given an array of integers nums, half of the integers in nums are odd, and the other half are even. Sort the array such that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any array that satisfies this condition.

Clarifying Questions

  1. What is the range of the input array size? Typically for coding problems, you may assume the array size to fit into memory efficiently (e.g., up to 10^5 elements).

  2. Are there any constraints on the values within the array? The problem does not specify any constraints, so assume they are general integers.

  3. Is it guaranteed that the number of odd and even elements are exactly half the array size each? Yes, the problem explicitly states that half of the integers are odd and the other half are even.

Strategy

  1. Two-Pointer Technique: Utilize two pointers to ensure the placement of even and odd numbers in their respective positions:
    • One pointer for the even index (starting from 0 and incrementing by 2).
    • One pointer for the odd index (starting from 1 and incrementing by 2).
  2. Scan Through the Array: Iterate through the array and place elements in their respective positions using the two pointers. Swap elements directly in the array to maintain the requirements.

Code

Here is the C++ code implementing the above strategy:

#include <vector>
#include <iostream>
using namespace std;

vector<int> sortArrayByParityII(vector<int>& nums) {
    int n = nums.size();
    int evenIdx = 0, oddIdx = 1;

    while (evenIdx < n && oddIdx < n) {
        if (nums[evenIdx] % 2 == 0) {
            evenIdx += 2;
        } else if (nums[oddIdx] % 2 == 1) {
            oddIdx += 2;
        } else {
            // Swap elements at evenIdx and oddIdx
            swap(nums[evenIdx], nums[oddIdx]);
            evenIdx += 2;
            oddIdx += 2;
        }
    }
    return nums;
}

int main() {
    vector<int> nums = {4, 2, 5, 7};
    vector<int> sortedArray = sortArrayByParityII(nums);

    for (int num : sortedArray) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Time Complexity

This approach effectively ensures that the array is sorted by parity while maintaining the required constraints on indices.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI