Pular para o conteúdo principal

Sort Array By Parity II

This question is asked by Amazon. Given an array of integers, nums, sort the array in any manner such that when i is even, nums[i] is even and when i is odd, nums[i] is odd.

Note: It is guaranteed that a valid sorting of nums exists.

Example(s)​

Example 1:

Input: nums = [1, 2, 3, 4]
Output: [2, 1, 4, 3]
Explanation:
- Index 0 (even): nums[0] = 2 (even) ✓
- Index 1 (odd): nums[1] = 1 (odd) ✓
- Index 2 (even): nums[2] = 4 (even) ✓
- Index 3 (odd): nums[3] = 3 (odd) ✓

Example 2:

Input: nums = [4, 2, 5, 7]
Output: [4, 5, 2, 7]
Explanation:
- Index 0: 4 (even) ✓
- Index 1: 5 (odd) ✓
- Index 2: 2 (even) ✓
- Index 3: 7 (odd) ✓

Example 3:

Input: nums = [2, 3]
Output: [2, 3]
Explanation:
- Index 0: 2 (even) ✓
- Index 1: 3 (odd) ✓

Solution​

The solution uses two pointers:

  1. Separate even and odd: Collect even and odd numbers separately
  2. Place in correct positions: Place evens at even indices, odds at odd indices
  3. Two pointers: Use two pointers to efficiently place numbers

JavaScript Solution - Two Pointers

/**
* Sort array so even indices have even numbers, odd indices have odd numbers
* @param {number[]} nums - Input array
* @return {number[]} - Sorted array
*/
function sortArrayByParityII(nums) {
const n = nums.length;
const result = new Array(n);

// Separate even and odd numbers
const evens = [];
const odds = [];

for (const num of nums) {
  if (num % 2 === 0) {
    evens.push(num);
  } else {
    odds.push(num);
  }
}

// Place evens at even indices, odds at odd indices
let evenIndex = 0;
let oddIndex = 0;

for (let i = 0; i < n; i++) {
  if (i % 2 === 0) {
    // Even index: place even number
    result[i] = evens[evenIndex++];
  } else {
    // Odd index: place odd number
    result[i] = odds[oddIndex++];
  }
}

return result;
}

// Test cases
console.log('Example 1:', sortArrayByParityII([1, 2, 3, 4])); 
// [2, 1, 4, 3]

console.log('Example 2:', sortArrayByParityII([4, 2, 5, 7])); 
// [4, 5, 2, 7]

console.log('Example 3:', sortArrayByParityII([2, 3])); 
// [2, 3]
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (In-Place with Two Pointers)​

Here's an in-place solution that doesn't use extra arrays:

/**
 * In-place solution using two pointers
 */
function sortArrayByParityIIInPlace(nums) {
  const n = nums.length;
  let evenPtr = 0; // Points to next even index that needs an even number
  let oddPtr = 1;  // Points to next odd index that needs an odd number
  
  while (evenPtr < n && oddPtr < n) {
    // Find even index with odd number
    while (evenPtr < n && nums[evenPtr] % 2 === 0) {
      evenPtr += 2;
    }
    
    // Find odd index with even number
    while (oddPtr < n && nums[oddPtr] % 2 === 1) {
      oddPtr += 2;
    }
    
    // Swap if both pointers are valid
    if (evenPtr < n && oddPtr < n) {
      [nums[evenPtr], nums[oddPtr]] = [nums[oddPtr], nums[evenPtr]];
      evenPtr += 2;
      oddPtr += 2;
    }
  }
  
  return nums;
}

Complexity​

  • Time Complexity: O(n) - Where n is the length of the array. We make a single pass to separate numbers, then another pass to place them.
  • Space Complexity:
    • Two arrays approach: O(n) - For the even and odd arrays
    • In-place approach: O(1) - Only using a constant amount of extra space

Approach​

The solution uses two arrays and two pointers:

  1. Separate numbers:

    • Collect all even numbers in one array
    • Collect all odd numbers in another array

  2. Place in result:

    • For even indices (0, 2, 4, ...): place even numbers
    • For odd indices (1, 3, 5, ...): place odd numbers

  3. Use pointers:

    • evenIndex: tracks position in evens array
    • oddIndex: tracks position in odds array

Key Insights​

  • Separate first: Easier to separate even/odd, then place
  • Two arrays: One for evens, one for odds
  • Two pointers: Track positions in each array
  • Guaranteed valid: Problem states a valid sorting exists
  • O(n) time: Single pass to separate, single pass to place

Step-by-Step Example​

Let's trace through Example 1: nums = [1, 2, 3, 4]

Step 1: Separate even and odd numbers
  nums = [1, 2, 3, 4]
  evens = [2, 4]
  odds = [1, 3]

Step 2: Place in result array
  result = [_, _, _, _]
  
  i = 0 (even index):
    result[0] = evens[0] = 2
    evenIndex = 1
  
  i = 1 (odd index):
    result[1] = odds[0] = 1
    oddIndex = 1
  
  i = 2 (even index):
    result[2] = evens[1] = 4
    evenIndex = 2
  
  i = 3 (odd index):
    result[3] = odds[1] = 3
    oddIndex = 2
  
  result = [2, 1, 4, 3]

Result: [2, 1, 4, 3]

Visual Representation​

Example 1: nums = [1, 2, 3, 4]

Step 1: Separate
  Evens: [2, 4]
  Odds:  [1, 3]

Step 2: Place
  Index:  0    1    2    3
  Type:  even odd even odd
  Result: 2    1    4    3
          ↑    ↑    ↑    ↑
         even odd even odd

Verification:
  Index 0 (even): 2 (even) ✓
  Index 1 (odd):  1 (odd) ✓
  Index 2 (even): 4 (even) ✓
  Index 3 (odd):  3 (odd) ✓

Edge Cases​

  • All evens: Works correctly
  • All odds: Works correctly
  • Already sorted: Returns correct result
  • Two elements: Works correctly
  • Equal numbers: Works correctly (e.g., [2, 2, 1, 1])

Important Notes​

  • Guaranteed valid: Problem states a valid sorting exists
  • Any valid sorting: Multiple valid solutions possible
  • Even indices: 0, 2, 4, ... (0-indexed)
  • Odd indices: 1, 3, 5, ... (0-indexed)
  • O(n) time: Optimal (must process all elements)

Why It Works​

Key insight:

  • The problem guarantees equal numbers of evens and odds
  • We need exactly n/2 evens and n/2 odds
  • Even indices: 0, 2, 4, ... (n/2 positions)
  • Odd indices: 1, 3, 5, ... (n/2 positions)
  • By separating and placing, we ensure correct positions
  • Sort Array By Parity: Different problem (evens first, then odds)
  • Partition Array: Similar partitioning problem
  • Move Zeroes: Different problem
  • Wiggle Sort: Different sorting problem

Takeaways​

  • Separate then place is a clear approach
  • Two arrays for even and odd numbers
  • Two pointers track positions in each array
  • O(n) time is optimal
  • O(n) space for the two arrays (or O(1) with in-place)