Rearrange Array Elements by Sign | 2 Varieties of same Problem

Main Ideas

The video explains two versions of the rearrange array elements by sign problem. In both versions, positive and negative values must alternate while preserving the original order among positive values and among negative values.

1. Equal Numbers of Positive and Negative Values

The array has even length, with exactly (n/2) positive and (n/2) negative values. The result starts with a positive value and alternates:

positive, negative, positive, negative, ...

Brute-Force Method

• Scan the input and collect positive and negative values into separate lists. Each list preserves the original relative order of its values.
• Build the result by placing the (i)-th positive at index 2 * i and the (i)-th negative at index 2 * i + 1.
• Time: (O(n))
• Space: (O(n)) for the lists and result.

One-Pass Placement Method

• Create a result array of length (n).
• Use two destination indices: 0 for the next positive slot and 1 for the next negative slot.
• Scan the input:
  • Place each positive value at the positive index, then advance that index by 2.
  • Place each negative value at the negative index, then advance that index by 2.
• Positive values go to even indices; negative values go to odd indices.
• Time: (O(n))
• Space: (O(n)) for the returned result, without separate positive and negative lists.

2. Unequal Numbers of Positive and Negative Values

The counts may differ. The result alternates for as long as both signs remain, then appends the remaining values while preserving their relative order.

Method

• Scan the input and collect positive and negative values into separate lists, preserving the order within each list.
• Interleave values from the two lists for as many pairs as possible—that is, for the smaller of the two list sizes.
• Append any remaining values from the list with more elements:
  • If there are more positive values, append the remaining positives.
  • If there are more negative values, append the remaining negatives.
• This method also handles equal counts; in that case, there are no leftover values.
• Time: (O(n))
• Space: (O(n)) for the sign-specific lists and result.

The even/odd-index placement method for the equal-count case depends on the counts matching. For unequal counts, using separate lists and appending the leftovers provides a straightforward solution.

Speakers and Sources

• Speaker: A single instructor or presenter, not named in the subtitles, presenting material from the takeUforward channel.
• Course/source: Striver’s A to Z DSA course.
• Platform/tool mentioned: CodeStudio and a code editor used to demonstrate and test the implementations.