0421MediumArrayTwo PointersSimulation

Interleaving the Statement Lines

Tracked in this browser only

Trains the technique from

LeetCode 2149Rearrange Array Elements by Sign

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A bookkeeper is re-issuing a statement. The old statement is nums, one signed amount per line: a positive amount is a credit and a negative amount is a debit. No line is ever zero, the statement has an even number of lines, and it holds exactly as many credits as debits.

House style says the re-issued statement must read credit, debit, credit, debit, and so on, beginning with a credit. Within each kind, the bookkeeper must not shuffle anything: if one credit came before another credit on the old statement, it must still come before it on the new one, and the same holds for the debits.

Return the re-issued statement as a list of amounts in order. Exactly one arrangement satisfies house style.

Examples

Example 1

Input: nums = [3, -1, -2, 4]
Output: [3, -1, 4, -2]

The old statement's credits are 3 then 4 and its debits are -1 then -2. The re-issued statement alternates from a credit and each kind is still in its old sequence.

Example 2

Input: nums = [9, -4, -7, 2, 5, -3]
Output: [9, -4, 2, -7, 5, -3]

Credits appear as 9, 2, 5 and debits as -4, -7, -3. Reading the answer, the odd slots hold those debits in that same order and the even slots hold those credits in theirs.

Example 3

Input: nums = [1, -1]
Output: [1, -1]

Two lines only. The credit takes the first slot and the debit the second.

Example 4

Input: nums = [5, 5, -5, -5]
Output: [5, -5, 5, -5]

Both credits are 5 and both debits are -5, so any credit-first alternation matches house style, and the answer alternates from a credit.

Example 5

Input: nums = [-1, -2, -3, 3, 2, 1]
Output: [3, -1, 2, -2, 1, -3]

Here the old statement opens with all three debits. The re-issued one still begins with a credit, taking 3, 2, 1 in that order for the even slots and -1, -2, -3 for the odd slots.

Constraints

2 <= nums.length <= 2 * 10^5
nums.length is even
1 <= |nums[i]| <= 10^5
nums holds an equal number of positive and negative amounts.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def rearrange_array(nums: list[int]) -> list[int]:

Java

public int[] rearrangeArray(int[] nums)

The intended approach

Time O(n) for n lines: one pass over the old statement with constant work per line.Space O(n) for the re-issued statement that is returned; no other working storage.

Allocate the re-issued statement up front and keep two write cursors into it, one starting at slot 0 for credits and one starting at slot 1 for debits, each advancing by two after a write. Read the old statement front to back once and send every amount to the cursor for its sign. Because each cursor only ever moves forward and the source is read in order, the credits keep their old sequence and so do the debits, and the equal counts guarantee both cursors finish exactly at the end.

Pythonentry point: rearrange_array

def rearrange_array(nums):
    # Two write cursors over the fresh statement: credits land on the even
    # slots, debits on the odd ones. Reading the ledger once in order and never
    # rewinding a cursor is what keeps each sign's own sequence intact.
    total = len(nums)
    reissued = [0] * total
    credit_at = 0
    debit_at = 1
    for line in nums:
        if line > 0:
            reissued[credit_at] = line
            credit_at += 2
        else:
            reissued[debit_at] = line
            debit_at += 2
    return reissued

The obvious version

Fill the new statement slot by slot. Slot k wants the (k // 2)-th credit when k is even and the (k // 2)-th debit when k is odd, so scan the whole old statement from the start counting amounts of that sign until the right one turns up. O(n^2).

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_rearrange_array(nums):
    total = len(nums)
    answer = []
    for slot in range(total):
        want_credit = slot % 2 == 0
        rank = slot // 2
        seen = 0
        chosen = 0
        for line in nums:
            if (line > 0) == want_credit:
                if seen == rank:
                    chosen = line
                    break
                seen += 1
        answer.append(chosen)
    return answer

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in