Sort Array by Parity - codepath/compsci_guides GitHub Wiki

TIP102 Unit 1 Session 2 Advanced (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Easy
  • ⏰ Time to complete: 10 mins
  • 🛠️ Topics: Arrays, Two-pointer technique

U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Q: What is the input to the function?

    • A: The input is an integer array nums.

  • Q: What is the expected output of the function?

    • A: The function should return the array nums with all even integers moved to the beginning followed by all odd integers.

  • Q: Should the order of the even or odd integers be preserved?

    • A: The problem does not require preserving the order of the even or odd integers, so any valid output that separates evens and odds is acceptable.

  • Q: Can the function modify the input array in-place?

    • A: Yes, the function can modify the input array in-place and should return the modified array.

  • Q: What should the function return if the input array is empty?

    • A: If the array is empty, the function should return an empty array.

  • The function sort_by_parity() should take an integer array and rearrange the elements such that all even integers come before all odd integers. The function can return any arrangement that satisfies this condition.

HAPPY CASE
Input: [3, 1, 2, 4]
Expected Output: [2, 4, 3, 1] (or any valid arrangement)

EDGE CASE
Input: [0]
Expected Output: [0]

P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use the two-pointer technique to rearrange the elements in the array, where one pointer moves from the beginning and the other from the end. Swap elements if necessary based on their parity.

1. Initialize two pointers: `left` at the start (0) and `right` at the end (len(nums) - 1) of the array.
2. While `left` is less than `right`:
   a. If the element at `left` is odd and the element at `right` is even, swap them.
   b. If the element at `left` is even, increment the `left` pointer.
   c. If the element at `right` is odd, decrement the `right` pointer.
3. Return the modified array

⚠️ Common Mistakes

  • Failing to handle cases with only even or only odd numbers.
  • Incorrectly managing pointer movements after a swap.

I-mplement

Implement the code to solve the algorithm.

def sort_by_parity(nums):
    left = 0
    right = len(nums) - 1
    
    while left < right:
        if nums[left] % 2 > nums[right] % 2:
            nums[left], nums[right] = nums[right], nums[left]
        
        if nums[left] % 2 == 0:
            left += 1
        if nums[right] % 2 == 1:
            right -= 1
    
    return nums