Pages

08/06/2021

[Java] Partition array moving all zero and negative elements at the end

We've already seen a possible solution for the Dutch flag problem where we partition an array given a pivot, so that all elements smaller than the pivot appear first, then all elements equal to it, then all elements bigger.

In this variant, we do not care about smaller, equal, bigger so we can use simpler logic to move all zero and negative elements at the end of an array.

Using two converging pointers starting at each end of the array, we can test pair of elements and swap if necessary. When the pointers meet, we are done and can also return the index marking the end of the positive portion of the array.

You can check my implementation of partitionArrayZerosAndNegativesLast on my Gist along with some tests in PartitionArrayZerosAndNegativesLastJTests.

No comments:

Post a Comment

With great power comes great responsibility