Move Zeroes

▶

Steps

setup

Initialize lastNonZeroFoundAt

We start by initializing the pointer 'lastNonZeroFoundAt' to 0, which will track where to place the next non-zero element.

💡 This pointer marks the boundary between processed non-zero elements and the rest of the array.

Line:

lastNonZeroFoundAt = 0

💡 Setting this pointer prepares the algorithm to overwrite zero elements with non-zero values as we find them.

traverse

Start traversal with i=0

Begin traversing the array with pointer 'i' at index 0 to inspect the first element.

💡 We examine each element to decide if it should be moved forward or skipped.

Line:

for num in nums:
    if num != 0:

💡 The traversal pointer 'i' scans every element to find non-zero values.

compare

Check if nums[0] is non-zero

Check if the element at index 0 (which is 0) is non-zero. It is zero, so no overwrite happens.

💡 Zero elements are skipped because they will be moved to the end later.

Line:

if num != 0:

💡 Zero elements do not advance the 'lastNonZeroFoundAt' pointer or overwrite any position.

traverse

Move i to 1, check nums[1]

Move pointer 'i' to index 1 to inspect the element 1, which is non-zero.

💡 Finding a non-zero means we will overwrite the element at 'lastNonZeroFoundAt'.

Line:

for num in nums:
    if num != 0:

💡 We are ready to move this non-zero element forward in the array.

insert

Overwrite nums[lastNonZeroFoundAt] with nums[i]

Since nums[1] is non-zero, overwrite nums[0] with nums[1] (1), then increment 'lastNonZeroFoundAt' to 1.

💡 This moves the non-zero element forward, compacting non-zero elements at the front.

Line:

nums[lastNonZeroFoundAt] = num
lastNonZeroFoundAt += 1

💡 Non-zero elements are collected at the front in their original order.

traverse

Move i to 2, check nums[2]

Move pointer 'i' to index 2 to inspect the element 0, which is zero.

💡 Zero elements are skipped and not moved forward.

Line:

for num in nums:
    if num != 0:

💡 Zeroes remain in place during the overwrite phase.

traverse

Move i to 3, check nums[3]

Move pointer 'i' to index 3 to inspect the element 3, which is non-zero.

💡 We will overwrite the element at 'lastNonZeroFoundAt' with this non-zero value.

Line:

for num in nums:
    if num != 0:

💡 Non-zero elements are moved forward to maintain order.

insert

Overwrite nums[lastNonZeroFoundAt] with nums[i]

Overwrite nums[1] with nums[3] (3), then increment 'lastNonZeroFoundAt' to 2.

💡 This moves the non-zero element 3 forward, compacting the array.

Line:

nums[lastNonZeroFoundAt] = num
lastNonZeroFoundAt += 1

💡 The array front now contains [1,3] as non-zero elements in order.

traverse

Move i to 4, check nums[4]

Move pointer 'i' to index 4 to inspect the element 12, which is non-zero.

💡 We will overwrite the element at 'lastNonZeroFoundAt' with this non-zero value.

Line:

for num in nums:
    if num != 0:

💡 Continuing to compact non-zero elements at the front.

insert

Overwrite nums[lastNonZeroFoundAt] with nums[i]

Overwrite nums[2] with nums[4] (12), then increment 'lastNonZeroFoundAt' to 3.

💡 This places the last non-zero element in the compacted front section.

Line:

nums[lastNonZeroFoundAt] = num
lastNonZeroFoundAt += 1

💡 All non-zero elements are now at the front in original order.

fill_cells

Traversal complete, start filling zeroes

After processing all elements, start filling zeroes from index 'lastNonZeroFoundAt' (3) to the end of the array.

💡 This step moves all zeroes to the end by overwriting remaining positions.

Line:

for i in range(lastNonZeroFoundAt, len(nums)):
    nums[i] = 0

💡 Zeroes are placed after all non-zero elements, preserving order.

fill_cells

Fill zero at index 3

Set nums[3] to 0, replacing the old value 3 with zero.

💡 This overwrites leftover elements with zeroes to complete the transformation.

Line:

nums[i] = 0

💡 Zeroes are placed in the tail positions after all non-zero elements.

fill_cells

Fill zero at index 4

Set nums[4] to 0, replacing the old value 12 with zero.

💡 Completing the zero fill phase by overwriting the last element.

Line:

nums[i] = 0

💡 All zeroes are now moved to the end of the array.

reconstruct

Algorithm complete, final array

The array is now fully processed with all non-zero elements at the front and zeroes at the end, preserving order.

💡 This final state shows the answer ready to be returned or used.

Line:

print(arr)

💡 The algorithm successfully partitions the array in-place without extra space.

def moveZeroes(nums):
    lastNonZeroFoundAt = 0  # STEP 1
    for num in nums:  # STEP 2,4,6,7,9
        if num != 0:  # STEP 3,5,8,10
            nums[lastNonZeroFoundAt] = num  # STEP 5,8,10
            lastNonZeroFoundAt += 1  # STEP 5,8,10
    for i in range(lastNonZeroFoundAt, len(nums)):  # STEP 11
        nums[i] = 0  # STEP 12,13

if __name__ == "__main__":
    arr = [0,1,0,3,12]
    moveZeroes(arr)
    print(arr)  # STEP 14

📊

Move Zeroes - Watch the Algorithm Execute, Step by Step

Watching each pointer movement and array modification helps you understand how the algorithm partitions the array into processed non-zero elements and remaining elements to be zeroed.

setup

lastNonZeroFoundAt

0

0

1

1

0

2

3

3

12

4

Result: []

compare

lastNonZeroFoundAt

0

0

1

1

0

2

3

3

12

4

Result: []

compare

lastNonZeroFoundAt

0

0

1

1

0

2

3

3

12

4

Result: []

compare

lastNonZeroFoundAt

0

0

i

1

1

0

2

3

3

12

4

Result: []

swap

1

0

lastNonZeroFoundAt

1

1

0

2

3

3

12

4

Result: [1]

compare

1

0

lastNonZeroFoundAt

1

1

i

0

2

3

3

12

4

Result: [1]

compare

1

0

lastNonZeroFoundAt

1

1

0

2

i

3

3

12

4

Result: [1]

swap

1

0

3

1

lastNonZeroFoundAt

0

2

i

3

3

12

4

Result: [1,3]

compare

1

0

3

1

lastNonZeroFoundAt

0

2

3

3

i

12

4

Result: [1,3]

swap

1

0

3

1

12

2

lastNonZeroFoundAt

3

3

i

12

4

Result: [1,3,12]

move_right

1

0

3

1

12

2

fillIndex

3

3

12

4

Result: [1,3,12]

record

1

0

3

1

12

2

fillIndex

0

3

12

4

Result: [1,3,12]

record

1

0

3

1

12

2

0

3

fillIndex

0

4

Result: [1,3,12]

done

1

0

3

1

12

2

0

3

0

4

Result: [1,3,12]

Key Takeaways

✓ The 'lastNonZeroFoundAt' pointer partitions the array into processed non-zero elements and the rest, enabling in-place compaction.

This insight is hard to see from code alone because the pointer's role is implicit without visualization.

✓ Non-zero elements are overwritten at the front in their original order, preserving relative order while moving zeroes to the end.

Visualizing the overwrite steps clarifies how order is maintained despite in-place modifications.

✓ Zero elements are skipped during traversal and only filled in after all non-zero elements are placed, showing a two-phase approach.

Seeing the separate phases of overwrite and zero fill helps understand why zeroes don't disrupt order.

Practice

1. You are given an integer array and a target value. The task is to count the number of triplets in the array such that the sum of the triplet is less than the target. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use three nested loops to check all triplets and count those with sum less than target.

B. Sort the array, then for each element use two pointers to find pairs that form triplets with sum less than target.

C. Use dynamic programming to store counts of sums and build up to triplets.

D. Use a greedy approach by always picking the smallest elements first to form triplets.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting triplets with sum less than a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach that reduces complexity

   Sorting and using two pointers allows scanning pairs efficiently for each fixed element, reducing complexity from O(n^3) to O(n^2).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + two pointers is a classic pattern for 3Sum variants [OK]

Hint: Sorting + two pointers reduces triple loops to quadratic [OK]

Common Mistakes:

• Assuming brute force is optimal
• Thinking DP applies directly here
• Believing greedy always works for sum constraints

2. You are given an array and a value. You need to remove all occurrences of this value in-place and return the new length of the array after removals. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Brute force shifting elements left whenever the value is found, resulting in nested loops

B. Two pointers with one scanning from start and the other from end, swapping unwanted elements to the end

C. Sorting the array first, then using binary search to find and remove the value

D. Using a hash set to track elements to keep and reconstruct the array

Solution

1. Step 1: Understand problem constraints

   The problem requires in-place removal with minimal time and space complexity.

2. Step 2: Evaluate approaches

   Brute force shifting is O(n^2), sorting changes order and is O(n log n), hash set uses extra space. Two pointers swapping from start and end achieves O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers swapping approach is optimal and in-place [OK]

Hint: Two pointers swapping from ends -> O(n) in-place removal [OK]

Common Mistakes:

• Confusing sorting or hash sets as optimal in-place solutions

3. You are given a problem where you must reverse the order of characters in an array in-place, without using extra space. Which algorithmic approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Using two pointers starting at opposite ends of the array and swapping elements until they meet.

B. Using a brute force approach that creates a new array and copies elements in reverse order.

C. Using a dynamic programming approach to store intermediate reversed substrings.

D. Using a greedy approach that swaps characters only when they are vowels.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing characters in-place without extra space, so approaches that use additional arrays are suboptimal.

2. Step 2: Identify the optimal approach

   Two pointers starting at opposite ends allow swapping characters in O(n) time and O(1) extra space, fulfilling the problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer in-place reversal is standard for optimal string reversal [OK]

Hint: Two pointers from ends swap in-place efficiently [OK]

Common Mistakes:

• Thinking DP or greedy applies to reversing strings
• Assuming extra space is allowed
• Confusing brute force with optimal in-place

4. What is the time complexity of the optimal approach that sorts the array and then uses a sliding window to find the minimum difference between k closest elements?

medium

A. O(n * k) because for each element we check a window of size k

B. O(n^2) because we compare all pairs of elements

C. O(k log n) because we only sort the first k elements

D. O(n log n) due to sorting, plus O(n) for sliding window traversal

Solution

1. Step 1: Identify sorting complexity

   Sorting the array takes O(n log n) time.

2. Step 2: Analyze sliding window traversal

   Sliding window moves linearly over the array, O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting dominates, sliding window is linear [OK]

Hint: Sorting dominates complexity, sliding window linear [OK]

Common Mistakes:

• Assuming sliding window is O(n*k) due to window size
• Confusing sorting only first k elements with full sort
• Mistaking pairwise comparisons as needed

5. Examine the following buggy code for removing duplicates from a sorted array:

def remove_duplicates(nums):
    if len(nums) == 0:
        return 0
    uniqueIndex = 0
    for currentIndex in range(1, len(nums)):
        if nums[currentIndex] != nums[uniqueIndex]:
            uniqueIndex += 1
            nums[currentIndex] = nums[uniqueIndex]
    return uniqueIndex + 1

Which line contains the bug that causes incorrect behavior?

medium

A. Line 2: if len(nums) == 0: return 0

B. Line 8: nums[currentIndex] = nums[uniqueIndex]

C. Line 6: if nums[currentIndex] != nums[uniqueIndex]:

D. Line 7: uniqueIndex += 1

Solution

1. Step 1: Identify assignment direction

   The correct code assigns nums[uniqueIndex] = nums[currentIndex] to overwrite duplicates; here it is reversed.

2. Step 2: Understand impact

   Assigning nums[currentIndex] = nums[uniqueIndex] overwrites scanning pointer's value incorrectly, breaking the unique sequence.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Assignment direction error causes wrong array modification [OK]

Hint: Assignment must overwrite uniqueIndex position, not currentIndex [OK]

Common Mistakes:

• Swapping assignment indices
• Forgetting to increment uniqueIndex