Abstract / Summary

Arrange numbers in the array so all positive come first then all negative keeping their original order within each group

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 85% (1+ million submissions).

Typical patterns to solve this problem:

• Array
• Simulation
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that reorders an integer array so that positive and negative numbers appear alternately. It relies on two indices that walk through the original list, one seeking the next positive element and the other seeking the next negative element. As each pair is found, the values are appended to a new list, preserving the alternating pattern until the output list reaches the same length as the input.

Key Steps

Initialization

The method begins by creating an empty container for the reordered sequence and setting two cursor variables to the start of the input array.

result = []          # could be done without extra space, too
pos = neg = 0

The comment hints at a possible in-place variant, but the current version builds a separate result list.

Main Loop

A while loop drives the process, continuing until the result list contains as many elements as the original array.

while len(result) < len(nums):

Inside this loop, two inner loops advance the cursors to the next appropriate values.

Advancing to the Next Positive

The first inner loop moves the pos cursor forward until it points to a non-negative element.

while nums[pos] < 0:
    pos += 1

When the condition fails, pos references a positive number ready for placement.

Advancing to the Next Negative

Similarly, the second inner loop moves the neg cursor forward until it lands on a non-positive element.

while nums[neg] > 0:
    neg += 1

At this point neg references a negative number.

Appending the Pair

With both indices positioned, the method appends the positive value followed by the negative value to the result list.

result.append(nums[pos])
result.append(nums[neg])

After the pair is added, both cursors are incremented to continue the search for the next positive and negative elements.

pos += 1
neg += 1

Completion

When the outer loop condition is satisfied, the fully interleaved list is returned.

return result

Edge Cases Handled

The algorithm gracefully handles inputs where positive and negative numbers are interspersed in any order. The inner loops guarantee that each cursor stops precisely at the next element of the required sign, so sequences such as [ -1, 2, -3, 4 ] or [ 5, -6, 7, -8, 9, -10 ] are processed correctly. Because the cursors only move forward, the method naturally terminates when the result list reaches the length of the original array, ensuring that no extra elements are added beyond the input size.

Performance Optimizations

The design employs two forward-only pointers, eliminating the need for repeated scans of the array. Each element is examined at most once by either the positive or negative pointer, resulting in a linear traversal of the input. The use of a single result list avoids the overhead of repeatedly inserting into the original array, and the in-place comment suggests that the current approach already minimizes auxiliary data structures while maintaining clarity. The incremental advancement of both pointers after each pair reduces the number of loop iterations, contributing to efficient execution.

Imagine you have a big pile of mixed toys on the floor, but some are blue and some are red. You want to make a perfectly patterned row where every blue toy is followed by a red toy, and then another blue, and then another red.

The computer does this by using two magic fingers to look through the pile. One finger looks only for the blue toys, and the other finger looks only for the red toys. The computer creates a new empty space where it will place the toys in the correct order.

The first magic finger walks along the row until it finds a blue toy, and the second magic finger walks along until it finds a red toy. The computer grabs both of those toys and puts them into the new row side by side. Then both fingers step forward to look for the next pair of colors in the pile. This keeps happening over and over again until every single toy from the pile has moved into the new row, all lined up perfectly in their own special color pattern.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go	TS
	Progiez	C++	Python		Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fartem						Ruby
	fsq	C++
	JoshCrozier			JS
	lkwq007		Python
	pruthvikp		Python
	shreymehul					C#
	suxrobGM					C#
	varunu28				Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
pruthvikp	Python
shreymehul	C#
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality