Rearrange Array Elements by Sign | Leetcode 2149

Are you struggling with the “Rearrange Array Elements by Sign” problem on LeetCode? Don’t worry! In this blog, we’ll break down the problem, show you two ways to solve it (Brute Force and Optimal), and explain everything in simple, easy-to-understand English. Let’s dive in!

Here’s the [Problem Link] to begin with.

What Does the Problem Say?

You are given an array of integers. Your task is to rearrange the elements so that positive and negative numbers appear one after another, starting with a positive number. The number of positive and negative numbers will always be the same.

Example 1

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

Output:
[3, -2, 1, -5, 2, -4]

Explanation:

• The first element is positive (3), the second is negative (-2), the third is positive (1), the fourth is negative (-5), and so on.

Example 2

Input:
nums = [-1, 1]

Output:
[1, -1]

Brute Force Solution

Intuition and Approach

Let’s think about how we can solve this problem step by step, using the simplest method:

1. Separate the Numbers:
   First, we need to separate the positive numbers and the negative numbers into two different lists. This way, we know exactly where all the positives and all the negatives are.
2. Rearrange Alternately:
   Next, we want to place the numbers back into the original array in an alternating order: first a positive, then a negative, then a positive, and so on.
3. Why Does This Work?
   Since the number of positive and negative numbers is always the same, we won’t run out of either type while rearranging. By first collecting all positives and negatives, and then placing them back one by one, we make sure the order is correct.

This approach is straightforward and easy to understand, even though it uses extra space for the two lists.

Code Implementation

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        pos = []
        neg = []
        n = len(nums)
        for i in range(len(nums)):
            if nums[i] > 0:
                pos.append(nums[i])
            else:
                neg.append(nums[i])
        for i in range(len(pos)):
            nums[2 * i] = pos[i]
            nums[2 * i + 1] = neg[i]
        return nums

Code Explanation

• Step 1: We create two empty lists: pos for positive numbers and neg for negative numbers.
• Step 2: We loop through the original array. If a number is positive, we add it to pos. If it’s negative, we add it to neg.
• Step 3: Now, we fill the original array. For every index i, we put pos[i] at position 2*i (even index) and neg[i] at position 2*i+1 (odd index).
• Step 4: Finally, we return the modified array.

Dry Run

Let’s dry run this code with an example:

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

• After separating:
  • pos = [3, - neg = [-2, -5, -4]`
• Now, fill the original array:
  • nums = 3 (first positive)
  • nums = -2 (first negative)
  • nums = 1 (second positive)
  • nums = -5 (second negative)
  • nums = 2 (third positive)
  • nums = -4 (third negative)

Final Output:
[3, -2, 1, -5, 2, -4]

Time and Space Complexity

• Time Complexity: O(N) + O(N) = O(2N), which is the same as O(N).
  • One pass to separate the numbers, one pass to rearrange.
• Space Complexity: O(N)
  • We use two extra lists to store positive and negative numbers.

Conclusion

The brute force solution is very easy to understand and works well for small to medium-sized arrays. However, it uses extra space because we store the positive and negative numbers separately.

Optimal Solution

Intuition and Approach

Let’s see if we can do better and use less extra space. Here’s the idea:

1. Direct Placement:
   Instead of storing positive and negative numbers in two separate lists, we can use a new array to place numbers directly in their correct positions as we go through the original array.
2. Use Two Pointers:
   We use two pointers (or indices): one for the next positive position (starting at index 0), and one for the next negative position (starting at index 1).
3. Fill as We Go:
   As we loop through the original array:
   • If we find a positive number, we put it at the next available even index (0, 2, 4, …).
   • If we find a negative number, we put it at the next available odd index (1, 3, 5, …).
4. Why Does This Work?
   This works because the number of positive and negative numbers is the same, so we never run out of space for either type.

This approach is more space-efficient and only needs one extra array.

Code Implementation

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        posIndex, negIndex = 0, 1
        for i in range(n):
            if nums[i] < 0:
                ans[negIndex] = nums[i]
                negIndex += 2
            else:
                ans[posIndex] = nums[i]
                posIndex += 2
        return ans

Code Explanation

• Step 1: We create a new array ans of the same size as nums, filled with zeros.
• Step 2: We set posIndex to 0 (for the next positive number) and negIndex to 1 (for the next negative number).
• Step 3: We loop through the original array:
  • If the current number is positive, we place it at ans[posIndex] and move posIndex by 2.
  • If the current number is negative, we place it at ans[negIndex] and move negIndex by 2.
• Step 4: Finally, we return the filled ans array.

Dry Run

Let’s dry run this code with the same example:

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

• Initial ans = [0, 0,osIndex = 0, negIndex = 1

Loop through nums:

• 3 is positive → ans = 3, posIndex = 2
• 1 is positive → ans = 1, posIndex = 4
• -2 is negative → ans = -2, negIndex = 3
• -5 is negative → ans = -5, negIndex = 5
• 2 is positive → ans = 2, posIndex = 6
• -4 is negative → ans = -4, negIndex = 7

Final Output:
[3, -2, 1, -5, 2, -4]

Time and Space Complexity

• Time Complexity: O(N)
  • Only one pass through the array.
• Space Complexity: O(N)
  • Only one extra array is used for the result.

Conclusion

The optimal solution is more efficient and elegant. It avoids using two separate lists and fills the answer array in a single pass. This is the best approach for interviews and large datasets.

Final Thoughts

The “Rearrange Array Elements by Sign” problem is a great way to practice array manipulation and pointer techniques. Start with the brute force method to build your understanding, and then move to the optimal solution for better performance and efficiency.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.