2149. Rearrange Array Elements by Sign

Problem Description

The task involves an integer array nums which has an even number of elements, split equally between positive and negative integers. The goal is to rearrange nums so that:

Each consecutive pair of integers have opposite signs, meaning a positive integer is always followed by a negative integer and vice versa.
The order of integers with the same sign should remain the same as in the original array.
The first integer in the rearranged array should be positive.

Our objective is to generate this modified array that satisfies all of the conditions stated above.

Intuition

To solve this problem, we can approach it by separating the positive and negative numbers while maintaining their original order. Since the array is guaranteed to have an equal number of positive and negative numbers and the array starts with a positive number, we can alternate placing positive and negative numbers to satisfy the condition that pairs must have opposite signs.

The process can be visualized more easily by thinking of two queues: one for positive numbers and one for negative numbers. We pick the numbers from each queue alternately and place them sequentially in the result array, ensuring that positive numbers are placed at even indices starting from 0, and negative numbers are placed at odd indices starting from 1.

By doing this, we leverage the fact that the indices used will ensure that positive and negative numbers are always paired (as they occupy adjacent slots in the array) while their relative order among positives and negatives is preserved.

The solution code realizes this conceptual process by using two pointers i and j to represent the positions in the result array where the next positive or negative number, respectively, will be placed. The pointers start from 0 for i (positive) and 1 for j (negative) and are incremented by 2 after each number is placed to maintain the required conditions. By iterating through the input array once and distributing numbers according to their sign, we can complete the rearrangement in one pass, resulting in an efficient and straightforward solution.

Learn more about Two Pointers patterns.

Solution Approach

The solution provided follows a simple yet effective approach that takes advantage of the array's specific constraints and properties. Here is a detailed explanation of how the solution is implemented:

We initialize a new array ans with the same length as the input array nums. This array will hold the rearranged elements.
We create two pointers i and j. The pointer i starts at 0 and will be used to place positive integers at even indices of ans. The pointer j starts at 1 and will be used for negative integers at odd indices of ans.
We then iterate over the original array nums. For each number, we check if it is positive or negative.
If the number num is positive, we place it at ans[i], and then increase i by 2. This ensures that the next positive number will be placed two indices later, thereby maintaining the alternating positive-negative pattern.
If the number num is negative, we follow a similar process by placing it at ans[j] and incrementing j by 2.
The loop continues until all elements from nums have been placed into ans. Thanks to the dual-pointer approach, there is no need for extra checks since the conditions stated in the problem guarantee that the final array will start with a positive number and exhibit the alternating sign pattern.
Once the loop is complete, the ans array, which is now a correctly rearranged version of nums, is returned.

In terms of algorithms and data structures, this solution primarily relies on array manipulation with pointers. We use a deterministic pattern to distribute elements and do not need additional data structures, like stacks or queues, because we have the guarantee of an equal number of positive and negative numbers.

In summary, this solution takes a linear-time algorithm (O(n)) as we pass through the array exactly once. Its space complexity is also linear (O(n)) due to the additional ans array used to store the rearranged elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the following nums array:

nums = [3, -1, 2, -2]

Following the steps of our solution approach:

We initialize our answer array ans to be of the same size as nums. Thus ans starts as [0, 0, 0, 0].
We set up two pointers, i starting at 0 for positive numbers, and j starting at 1 for negative numbers.
We iterate over nums. The first number is 3, which is positive. We place it at ans[i] (where i is 0), so ans becomes [3, 0, 0, 0], and then we increase i by 2. Now i is 2.
Next number is -1, which is negative. We place it at ans[j] (where j is 1), so ans becomes [3, -1, 0, 0], and then we increase j by 2. Now j is 3.
We continue and encounter the positive number 2. We place it at ans[i] (where i is 2), making ans [3, -1, 2, 0], and increase i by 2 again. However, i is now 4, which is out of bounds for this array so we won't use i anymore.
Finally, -2 is negative and goes to ans[j] (where j is 3), giving us ans [3, -1, 2, -2]. Incrementing j by 2 doesn't matter anymore since we've finished processing the array.

The loop finishes with all elements placed correctly, resulting in an array where each positive number is followed by a negative one. The processed ans array [3, -1, 2, -2] is now returned. This array is the rearranged version of nums with alternating signs, starting with a positive integer.

This example has followed the solution steps exactly and provided the desired output in accordance with the original problem's requirements.

Solution Implementation

1from typing import List
2
3class Solution:
4    def rearrangeArray(self, nums: List[int]) -> List[int]:
5        # Initialize an array of the same length as `nums` with all elements set to 0
6        rearranged = [0] * len(nums)
7      
8        # `positive_index` tracks the next position for a positive number
9        # `negative_index` tracks the next position for a negative number
10        positive_index, negative_index = 0, 1
11      
12        # Iterate over all numbers in the given list
13        for num in nums:
14            if num > 0:
15                # If the current number is positive, place it in the next available positive index
16                rearranged[positive_index] = num
17                # Increment the positive index by 2 to point to the next position for a positive number
18                positive_index += 2
19            else:
20                # If the current number is negative, place it in the next available negative index
21                rearranged[negative_index] = num
22                # Increment the negative index by 2 to point to the next position for a negative number
23                negative_index += 2
24      
25        # Return the rearranged array where positive and negative numbers alternate
26        return rearranged
27

1class Solution {
2    public int[] rearrangeArray(int[] nums) {
3        // Initialize a new array to hold the rearranged elements
4        int[] rearrangedArray = new int[nums.length];
5      
6        // Two pointers to place positive and negative numbers in the array.
7        // Positives will be placed at even indices and negatives at odd indices.
8        int positiveIndex = 0, negativeIndex = 1;
9      
10        // Iterate through all the numbers in the input array.
11        for (int num : nums) {
12            if (num > 0) {
13                // When we encounter a positive number, we place it at the next even index
14                rearrangedArray[positiveIndex] = num;
15                positiveIndex += 2; // Move the pointer to the next position for a positive number
16            } else {
17                // When we encounter a negative number, we place it at the next odd index
18                rearrangedArray[negativeIndex] = num;
19                negativeIndex += 2; // Move the pointer to the next position for a negative number
20            }
21        }
22      
23        // Return the rearranged array where no two consecutive numbers have the same sign
24        return rearrangedArray;
25    }
26}
27

1#include <vector>
2
3class Solution {
4public:
5    // This method rearranges the elements of the input array such that
6    // positive and negative numbers alternate, beginning with a positive number.
7    // It expects a vector of integers and returns the rearranged vector.
8    std::vector<int> rearrangeArray(std::vector<int>& nums) {
9        std::vector<int> rearranged(nums.size()); // Create a new vector for rearranged elements
10        int positiveIndex = 0; // Initialize index for placing positive numbers, starting from position 0
11        int negativeIndex = 1; // Initialize index for placing negative numbers, starting from position 1
12
13        // Iterate over each number in the input array
14        for (int num : nums) {
15            if (num > 0) {
16                // If current number is positive, place it at the next available positive index
17                rearranged[positiveIndex] = num;
18                positiveIndex += 2; // Increment the position by 2 to skip the next negative place
19            } else {
20                // If current number is negative, place it at the next available negative index
21                rearranged[negativeIndex] = num;
22                negativeIndex += 2; // Increment the position by 2 to skip the next positive place
23            }
24        }
25        // Return the rearranged vector
26        return rearranged;
27    }
28};
29

1function rearrangeArray(nums: number[]): number[] {
2    // Initialize an empty array to store the rearranged elements
3    let rearranged = [];
4    // Initialize two pointers to fill positive and negative numbers respectively
5    let positiveIndex = 0,
6        negativeIndex = 1;
7  
8    // Iterate through each number in the input array
9    for (let num of nums) {
10        if (num > 0) {
11            // If the current number is positive, place it at the next available positive index
12            rearranged[positiveIndex] = num;
13            positiveIndex += 2; // Increment the positive index by 2 to maintain alternating positions
14        } else {
15            // If the current number is negative, place it at the next available negative index
16            rearranged[negativeIndex] = num;
17            negativeIndex += 2; // Increment the negative index by 2 to maintain alternating positions
18        }
19    }
20  
21    // Return the rearranged array with alternated positive and negative numbers
22    return rearranged;
23}
24

Time and Space Complexity

The provided Python code aims to rearrange an array such that positive and negative elements are placed alternatively, starting with a positive element. Here's the analysis of its time and space complexity:

Time Complexity:

The code utilizes a single for loop that iterates over the entire list nums, meaning that each element in the original list is looked at exactly once. This results in a linear time complexity relative to the size of the input list. Therefore, the time complexity is O(n), where n is the length of the list nums.

Space Complexity:

The space complexity involves analyzing both the input space and the additional space used by the algorithm excluding the input and output. The space taken by the list nums is not considered extra space as it is the input.

The code uses ans, an auxiliary list of the same length as nums, to store the rearranged elements. No additional data structures that grow with the input size are used; therefore, the extra space used by the code is proportional to the input size. Hence, the space complexity for the auxiliary space is O(n).

In some cases, the output space is not considered in space complexity analysis. If the output space is not to be considered, only a constant amount of extra space is used for the variables i and j. This would make the space complexity O(1). However, if the output space is included, then the total space complexity, accounting for both the input and the created returned list ans, would indeed be O(n).

The choice of whether to consider the output space depends on the context or the specific definitions followed.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know