Partition Array by Parity

▶

Steps

setup

Initialize insertPos pointer

We start by setting insertPos to 0, which marks the position where the next even number will be placed.

💡 This pointer helps us keep track of the boundary between even and odd numbers as we scan the array.

Line:

insertPos = 0

💡 insertPos starts at the beginning, ready to place even numbers at the front.

traverse

Start traversal with i=0

Begin scanning the array from the first element at index 0 with pointer i.

💡 Pointer i moves through each element to check if it is even or odd.

Line:

for i in range(len(nums)):

💡 We will examine each element one by one to decide if a swap is needed.

compare

Check if nums[i] is even (i=0)

Check if the element at index 0 (3) is even by computing 3 % 2.

💡 Only even numbers trigger a swap and insertPos increment.

Line:

if nums[i] % 2 == 0:

💡 Odd numbers are left in place and skipped.

traverse

Move i to next element (i=1)

Increment i to 1 to check the next element in the array.

💡 We continue scanning the array sequentially.

Line:

for i in range(len(nums)):  # next iteration

💡 The algorithm processes each element in order.

compare

Check if nums[i] is even (i=1)

Check if the element at index 1 (1) is even by computing 1 % 2.

💡 Again, only even numbers cause a swap and insertPos increment.

Line:

if nums[i] % 2 == 0:

💡 Odd numbers are skipped and do not move insertPos.

traverse

Move i to next element (i=2)

Increment i to 2 to check the next element in the array.

💡 We continue scanning the array sequentially.

Line:

for i in range(len(nums)):  # next iteration

💡 The algorithm processes each element in order.

compare

Check if nums[i] is even (i=2)

Check if the element at index 2 (2) is even by computing 2 % 2.

💡 Even numbers trigger a swap with the element at insertPos.

Line:

if nums[i] % 2 == 0:

💡 Swapping places the even number at the front partition boundary.

insert

Swap nums[i] and nums[insertPos]

Swap the even number 2 at index 2 with the element at insertPos (index 0, value 3).

💡 This moves the even number to the front and pushes the odd number back.

Line:

nums[i], nums[insertPos] = nums[insertPos], nums[i]
insertPos += 1

💡 Swapping maintains the partition invariant: evens before insertPos, odds after.

traverse

Move i to next element (i=3)

Increment i to 3 to check the last element in the array.

💡 We continue scanning the array sequentially.

Line:

for i in range(len(nums)):  # next iteration

💡 The algorithm processes each element in order.

compare

Check if nums[i] is even (i=3)

Check if the element at index 3 (4) is even by computing 4 % 2.

💡 Even numbers trigger a swap with the element at insertPos.

Line:

if nums[i] % 2 == 0:

💡 Swapping places the even number at the front partition boundary.

insert

Swap nums[i] and nums[insertPos]

Swap the even number 4 at index 3 with the element at insertPos (index 1, value 1).

💡 This moves the even number to the front and pushes the odd number back.

Line:

nums[i], nums[insertPos] = nums[insertPos], nums[i]
insertPos += 1

💡 Swapping maintains the partition invariant: evens before insertPos, odds after.

reconstruct

Traversal complete, return result

All elements have been processed; the array is now partitioned with evens first.

💡 The array now satisfies the problem requirement: evens before odds.

Line:

return nums

💡 The final array is a valid partition by parity.

from typing import List

def partitionArrayByParity(nums: List[int]) -> List[int]:
    insertPos = 0  # STEP 1
    for i in range(len(nums)):  # STEP 2,4,6,9
        if nums[i] % 2 == 0:  # STEP 3,5,7,10
            nums[i], nums[insertPos] = nums[insertPos], nums[i]  # STEP 8,11
            insertPos += 1  # STEP 8,11
    return nums  # STEP 12

if __name__ == '__main__':
    print(partitionArrayByParity([3,1,2,4]))  # Output: [2,4,3,1]

📊

Partition Array by Parity - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and swap helps you understand how the algorithm partitions the array in one pass without extra space.

setup

insertPos

3

0

1

1

2

2

4

3

Result: []

compare

i

3

0

1

1

2

2

4

3

Result: []

compare

i

3

0

1

1

2

2

4

3

Result: []

compare

insertPos

3

0

i

1

1

2

2

4

3

Result: []

compare

insertPos

3

0

i

1

1

2

2

4

3

Result: []

compare

insertPos

3

0

1

1

i

2

2

4

3

Result: []

swap

insertPos

3

0

1

1

i

2

2

4

3

Result: []

swap

2

0

insertPos

1

1

i

3

2

4

3

Result: []

compare

2

0

insertPos

1

1

3

2

i

4

3

Result: []

swap

2

0

insertPos

1

1

3

2

i

4

3

Result: []

swap

2

0

4

1

insertPos

3

2

i

1

3

Result: []

return

2

0

4

1

insertPos

3

2

1

3

Result: ["2","4","3","1"]

Key Takeaways

✓ The insertPos pointer tracks the boundary where the next even number should be placed.

This insight is hard to see from code alone because the pointer's role is implicit in the swap logic.

✓ Only even numbers cause swaps and increment insertPos, while odd numbers are skipped.

Visually seeing which elements trigger swaps clarifies the partitioning mechanism.

✓ The algorithm completes in one pass, maintaining the invariant that all elements before insertPos are even.

Understanding this invariant is easier when watching the pointer and array state update step-by-step.

Practice

1. You are given two sorted arrays, where the first array has enough space at the end to hold all elements of the second array. You need to merge them into one sorted array in-place without using extra space. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Sort the combined elements after copying both arrays into a new array.

B. Use two pointers starting from the end of both arrays and merge in-place from the back.

C. Use a two-pointer approach starting from the front and merge into a new array.

D. Use a greedy approach by always picking the smaller element from the front of both arrays.

Solution

1. Step 1: Understand the problem constraints

   The first array has extra space at the end to hold all elements of the second array, allowing in-place merging.

2. Step 2: Identify the optimal approach

   Starting from the end with two pointers avoids overwriting unprocessed elements and achieves O(m+n) time with O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers from the back merge without extra space [OK]

Hint: Merge from the back to avoid overwriting [OK]

Common Mistakes:

• Merging from the front overwrites elements
• Sorting combined array wastes time

2. Consider the following Python function that finds the minimum difference between k closest elements in an array. What is the returned value when arr = [4, 1, 7, 9] and k = 2?

easy

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Sort the array

   Sorted array is [1, 4, 7, 9].

2. Step 2: Slide window of size 2 and compute differences

   Windows: [1,4] diff=3, [4,7] diff=3, [7,9] diff=2. Minimum difference is 2.

3. Step 3: Re-examine calculations

   Check carefully: differences are 3, 3, and 2. Minimum is 2, so answer is 2.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Minimum difference between any two sorted elements is 2 [OK]

Hint: Sort array, check adjacent pairs for min difference [OK]

Common Mistakes:

• Off-by-one error in window boundaries
• Confusing difference calculation with max-min of unsorted subset
• Returning 0 prematurely without checking all windows

3. Given the following code for trapping rain water, what is the value of the variable water returned by trap([2,0,2])?

easy

A. 4

B. 0

C. 2

D. 1

Solution

1. Step 1: Initialize variables

   left=0, right=2, left_max=0, right_max=0, water=0

2. Step 2: Trace iterations

   Iteration 1: height[left]=2, height[right]=2, height[left] not less than height[right], so process right pointer. right_max updated to 2, right moves to 1.
   Iteration 2: left=0, right=1, height[left]=2, height[right]=0, height[left] > height[right], process right pointer.
   height[right]=0 < right_max=2, water += 2 - 0 = 2, right moves to 0.
   Loop ends as left == right.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Water trapped between two height 2 bars with 0 in middle is 2 units [OK]

Hint: Trace pointers and water increments carefully [OK]

Common Mistakes:

• Off-by-one errors in pointer movement
• Confusing which pointer to move
• Incorrectly updating max heights

4. You are given a sorted array of integers and a target sum. You need to find two distinct elements whose sum equals the target. Which approach guarantees an optimal solution in terms of time complexity and correctness?

easy

A. Use two pointers starting at opposite ends of the array, moving inward based on the sum comparison.

B. Use a hash map to store elements and check complements in a single pass.

C. Use dynamic programming to store sums of all pairs and check for the target.

D. Use a greedy approach by iterating from the start and picking the first pair that sums to the target.

Solution

1. Step 1: Understand the problem constraints

   The array is sorted, so two pointers at opposite ends can efficiently find pairs by comparing sums.

2. Step 2: Evaluate each approach

   Greedy fails because it may miss pairs; DP is unnecessary overhead; hash map works but uses extra space and is not optimal for sorted arrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two pointers exploit sorting for O(n) time and O(1) space [OK]

Hint: Sorted array + two pointers -> optimal pair search [OK]

Common Mistakes:

• Assuming greedy always works
• Using DP unnecessarily
• Ignoring sorted property

5. Examine the following code snippet for 3Sum. Which line contains a subtle bug that can cause duplicate triplets in the output?

medium

A. Line 6: Missing check to skip duplicates for fixed element i

B. Line 10: Incorrect calculation of complement

C. Line 14: Not sorting triplet before appending

D. Line 16: Missing increment of j after skipping duplicates

Solution

1. Step 1: Identify duplicate handling for fixed element

   Line 6 lacks the check to skip duplicate nums[i], causing repeated triplets.

2. Step 2: Verify other lines

   Complement calculation and triplet sorting are correct; j increment after skipping duplicates is present.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Skipping duplicates for i is essential to avoid duplicate triplets [OK]

Hint: Skipping duplicates for fixed i prevents repeated triplets [OK]

Common Mistakes:

• Forgetting to skip duplicates for i
• Assuming sorting triplet is unnecessary
• Misplacing complement calculation