Rearrange Array Elements by Sign solution and explanation
Google
Infosys
9 more videos on this problem
Rearrange Array Elements by Sign | 2 Varieties of same Problemtake U forward · 21:37 · 526K views
Rearrange Array Elements by Sign - Leetcode 2149 - PythonNeetCodeIO · 10:25 · 14K views
2149. Rearrange Array Elements by Sign | 3 Ways | 2Pointers | In-place Swap LogicAryan Mittal · 19:54 · 3K views
Leetcode | 2149. Rearrange Array Elements by Sign | Medium | Java SolutionDeveloper Docs · 4:58 · 1K views
2149. Rearrange Array Elements by Sign (Leetcode Medium)Programming Live with Larry · 2:57 · 586 views
HOW TO Rearrange Array Elements by Sign - Leetcode 2149Lit Code · 5:35 · 312 views
LeetCode 2149 - Rearrange Array Elements by Sign - JavaScript - [MEDIUM]NoviceJS · 9:09 · 185 views
Solving LeetCode 2149 Rearrange Array Elements by Sign | Two Pointer | Amazon | Apple | AdobeCode Harmony · 9:38 · 110 views
Rearrange Array Elements by Sign - LeetCode 2149 - Java Solutionalgobest - Computer Science · 3:33 · 66 views
Leetcode 2149: Rearrange Array Elements by SignAlgorithms Casts · 8:04 · 63 views
The problem
You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers.
You should return the array of nums such that the the array follows the given conditions:
- Every consecutive pair of integers have opposite signs.
- For all integers with the same sign, the order in which they were present in
numsis preserved. - The rearranged array begins with a positive integer.
Return the modified array after rearranging the elements to satisfy the aforementioned conditions.
Example 1:
Input: nums = [3,1,-2,-5,2,-4] Output: [3,-2,1,-5,2,-4] Explanation: The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4]. The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4]. Other ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.
Example 2:
Input: nums = [-1,1] Output: [1,-1] Explanation: 1 is the only positive integer and -1 the only negative integer in nums. So nums is rearranged to [1,-1].
Constraints:
2 <= nums.length <= 2 * 105nums.lengthis even1 <= |nums[i]| <= 105numsconsists of equal number of positive and negative integers.
Approach overview
Problem Overview: You are given an array with equal numbers of positive and negative integers. Rearrange the elements so positives and negatives appear alternately, starting with a positive number, while preserving the relative order of elements.
Approach 1: Two Lists Approach (O(n) time, O(n) space)
Split the array into two separate lists: one for positive numbers and one for negative numbers. Iterate through the original array once and push values into the corresponding list. Then construct the result by alternating elements from both lists: positive at even indices and negative at odd indices. Since the problem guarantees equal counts of positives and negatives, both lists will be exhausted at the same time. This approach is straightforward and preserves relative order naturally because elements are appended in the order they appear. It’s commonly used when solving array rearrangement problems where stability matters.
Approach 2: In-place Rearrangement (O(n) time, O(1) extra space)
Instead of maintaining two auxiliary lists, place elements directly into their correct positions using index pointers. Maintain two indices: one pointing to the next even index (for positives) and another pointing to the next odd index (for negatives). Iterate through the array and place each value in the correct index based on its sign. After placing a number, move the corresponding pointer by two positions. The key insight is that positives must occupy even indices (0,2,4...) while negatives occupy odd indices (1,3,5...). This keeps the alternating pattern intact without storing intermediate lists. The technique resembles a controlled placement strategy often used with two pointers and simple simulation logic.
Both strategies run in linear time because each element is processed once. The difference is memory usage: the two-list solution trades space for clarity, while the in-place strategy minimizes auxiliary storage.
Recommended for interviews: The two lists approach is usually the first solution candidates implement because it clearly demonstrates understanding of the alternating constraint and order preservation. Interviewers often expect the O(n) time complexity solution quickly. After that, discussing the in-place rearrangement shows deeper optimization skills and awareness of space complexity tradeoffs.
Approach 1: Two Lists Approach
This approach involves creating two separate lists to store positive and negative numbers. After separating, we iterate through both lists simultaneously, placing elements alternatively from each into a new result list. This ensures that conditions for alternating signs and preserving order are met.
def rearrange_array(nums):
pos, neg = [], []
for num in nums:
if num > 0:
pos.append(num)
else:
neg.append(num)
result = []
for p, n in zip(pos, neg):
result.extend([p, n])
return result
nums = [3, 1, -2, -5, 2, -4]
print(rearrange_array(nums))import java.util.ArrayList;
import java.util.List;
public class RearrangeArray {
public static int[] rearrangeArray(int[] nums) {
List<Integer> pos = new ArrayList<>();
List<Integer> neg = new ArrayList<>();
for (int num : nums) {
if (num > 0) pos.add(num);
else neg.add(num);
}
int[] result = new int[nums.length];
int posIndex = 0, negIndex = 0;
for (int i = 0; i < nums.length; i += 2) {
result[i] = pos.get(posIndex++);
result[i + 1] = neg.get(negIndex++);
}
return result;
}
public static void main(String[] args) {
int[] nums = {3, 1, -2, -5, 2, -4};
int[] result = rearrangeArray(nums);
for (int num : result) System.out.print(num + " ");
}
}#include <iostream>
#include <vector>
using namespace std;
vector<int> rearrangeArray(vector<int>& nums) {
vector<int> pos, neg, result(nums.size());
for (int num : nums) {
if (num > 0) pos.push_back(num);
else neg.push_back(num);
}
int posIndex = 0, negIndex = 0;
for (int i = 0; i < nums.size(); i += 2) {
result[i] = pos[posIndex++];
result[i + 1] = neg[negIndex++];
}
return result;
}
int main() {
vector<int> nums = {3, 1, -2, -5, 2, -4};
vector<int> result = rearrangeArray(nums);
for (int num : result) cout << num << " ";
return 0;
}function rearrangeArray(nums) {
const pos = [];
const neg = [];
for (let num of nums) {
if (num > 0) pos.push(num);
else neg.push(num);
}
const result = [];
for (let i = 0; i < pos.length; i++) {
result.push(pos[i]);
result.push(neg[i]);
}
return result;
}
const nums = [3, 1, -2, -5, 2, -4];
console.log(rearrangeArray(nums));#include <stdio.h>
void rearrange(int* nums, int numsSize, int* result) {
int posIndex = 0, negIndex = 0;
int pos[numsSize/2], neg[numsSize/2];
for (int i = 0; i < numsSize; i++) {
if (nums[i] > 0) pos[posIndex++] = nums[i];
else neg[negIndex++] = nums[i];
}
posIndex = negIndex = 0;
for (int i = 0; i < numsSize; i += 2) {
result[i] = pos[posIndex++];
result[i + 1] = neg[negIndex++];
}
}
int main() {
int nums[] = {3, 1, -2, -5, 2, -4};
int result[6];
rearrange(nums, 6, result);
for(int i = 0; i < 6; i++) printf("%d ", result[i]);
return 0;
}using System;
using System.Collections.Generic;
class RearrangeArray {
public static int[] Rearrange(int[] nums) {
List<int> pos = new List<int>();
List<int> neg = new List<int>();
foreach (int num in nums) {
if (num > 0) pos.Add(num);
else neg.Add(num);
}
int[] result = new int[nums.Length];
int posIndex = 0, negIndex = 0;
for (int i = 0; i < nums.Length; i += 2) {
result[i] = pos[posIndex++];
result[i + 1] = neg[negIndex++];
}
return result;
}
static void Main() {
int[] nums = {3, 1, -2, -5, 2, -4};
int[] result = Rearrange(nums);
Console.WriteLine(string.Join(" ", result));
}
}This Python solution uses two lists to separate positive and negative numbers, then interleaves them in the result list.
Time Complexity: O(n); Space Complexity: O(n).
Approach 2: In-place Rearrangement
This approach attempts to rearrange the array in-place with the help of two pointers: one for the next positive element and one for the next negative. Starting with the assumption that the first element should be positive, iterate over the array and swap elements to their correct positions as needed.
def rearrange_array(nums):
pos, neg = 0, 1
while pos < len(nums) and neg < len(nums):
if nums[pos] > 0:
pos += 2
elif nums[neg] < 0:
neg += 2
else:
nums[pos], nums[neg] = nums[neg], nums[pos]
return nums
nums = [3, 1, -2, -5, 2, -4]
print(rearrange_array(nums))import java.util.Arrays;
public class RearrangeArray {
public static void rearrangeArray(int[] nums) {
int pos = 0, neg = 1;
while (pos < nums.length && neg < nums.length) {
if (nums[pos] > 0) pos += 2;
else if (nums[neg] < 0) neg += 2;
else {
int temp = nums[pos];
nums[pos] = nums[neg];
nums[neg] = temp;
}
}
}
public static void main(String[] args) {
int[] nums = {3, 1, -2, -5, 2, -4};
rearrangeArray(nums);
System.out.println(Arrays.toString(nums));
}
}#include <iostream>
#include <vector>
using namespace std;
void rearrangeArray(vector<int>& nums) {
int pos = 0, neg = 1;
while (pos < nums.size() && neg < nums.size()) {
if (nums[pos] > 0) pos += 2;
else if (nums[neg] < 0) neg += 2;
else swap(nums[pos], nums[neg]);
}
}
int main() {
vector<int> nums = {3, 1, -2, -5, 2, -4};
rearrangeArray(nums);
for (int num : nums) cout << num << " ";
return 0;
}function rearrangeArray(nums) {
let pos = 0, neg = 1;
while (pos < nums.length && neg < nums.length) {
if (nums[pos] > 0) {
pos += 2;
} else if (nums[neg] < 0) {
neg += 2;
} else {
[nums[pos], nums[neg]] = [nums[neg], nums[pos]]; // Swap
}
}
return nums;
}
const nums = [3, 1, -2, -5, 2, -4];
console.log(rearrangeArray(nums));#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void rearrange(int* nums, int numsSize) {
int pos = 0, neg = 1;
while (pos < numsSize && neg < numsSize) {
if (nums[pos] > 0) pos += 2;
else if (nums[neg] < 0) neg += 2;
else swap(&nums[pos], &nums[neg]);
}
}
int main() {
int nums[] = {3, 1, -2, -5, 2, -4};
int numsSize = 6;
rearrange(nums, numsSize);
for (int i = 0; i < numsSize; i++) printf("%d ", nums[i]);
return 0;
}using System;
class RearrangeArray {
public static void Rearrange(int[] nums) {
int pos = 0, neg = 1;
while (pos < nums.Length && neg < nums.Length) {
if (nums[pos] > 0) pos += 2;
else if (nums[neg] < 0) neg += 2;
else {
int temp = nums[pos];
nums[pos] = nums[neg];
nums[neg] = temp;
}
}
}
static void Main() {
int[] nums = {3, 1, -2, -5, 2, -4};
Rearrange(nums);
Console.WriteLine(string.Join(" ", nums));
}
}By treating the input list as a single array, this Python approach rearranges elements in-place using two alternating pointers, ensuring no extra space is used.
Time Complexity: O(n); Space Complexity: O(1).
Approach 3: Two Pointers
First, we create an array ans of length n. Then, we use two pointers i and j to point to the even and odd indices of ans, respectively, with initial values i = 0, j = 1.
We iterate through the array nums. If the current element x is a positive integer, then we place x into ans[i] and increase i by 2; otherwise, we place x into ans[j] and increase j by 2.
Finally, we return ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
function rearrangeArray(nums: number[]): number[] {
const ans: number[] = Array(nums.length);
let [i, j] = [0, 1];
for (const x of nums) {
if (x > 0) {
ans[i] = x;
i += 2;
} else {
ans[j] = x;
j += 2;
}
}
return ans;
}func rearrangeArray(nums []int) []int {
ans := make([]int, len(nums))
i, j := 0, 1
for _, x := range nums {
if x > 0 {
ans[i] = x
i += 2
} else {
ans[j] = x
j += 2
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Lists Approach | Time Complexity: O(n); Space Complexity: O(n). |
| In-place Rearrangement | Time Complexity: O(n); Space Complexity: O(1). |
| Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Lists Approach | O(n) | O(n) | Best for clarity and quick implementation when extra memory is acceptable. |
| In-place Rearrangement | O(n) | O(1) | Useful when memory is constrained or when interviewers ask for optimized space usage. |
| Two-Pointer Placement with Result Array | O(n) | O(n) | Good balance of simplicity and speed when directly filling even and odd indices. |
Frequently asked questions
Is Rearrange Array Elements by Sign easy or hard?
The problem is rated Medium but behaves closer to an easy-medium array manipulation task. The logic is straightforward once you recognize the alternating index pattern, but the requirement to preserve relative order makes it slightly more involved than a simple partition problem.
Rearrange Array Elements by Sign Python/Java solution
In Python or Java, iterate through the array and push positive values into one list and negative values into another. Then build the result by alternating elements from both lists. This produces an O(n) solution that preserves the original ordering of numbers.
How to solve Rearrange Array Elements by Sign in O(n)?
Traverse the array once and place each positive number at the next available even index and each negative number at the next odd index. Maintain two pointers that move by two positions after each placement. Every element is processed exactly once, giving O(n) time complexity.
What is the best approach for Rearrange Array Elements by Sign?
The most practical approach uses two lists to collect positive and negative numbers separately, then alternates them in the result array. This method runs in O(n) time and preserves the relative order of elements. It is simple to implement and is the approach most candidates write first during interviews.
Is Rearrange Array Elements by Sign asked at Google/Amazon/Meta?
Array rearrangement and alternating placement patterns appear frequently in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying techniques such as two pointers, index placement, and stable ordering are common interview topics.
What data structure is used in Rearrange Array Elements by Sign?
The problem primarily uses arrays and sometimes auxiliary lists (dynamic arrays) to store positive and negative values. The optimized solution relies on pointer indices within the array rather than additional data structures.
What is the time complexity of Rearrange Array Elements by Sign?
The optimal solutions run in O(n) time because the array is traversed once to separate or place elements and once to construct the final arrangement. Space complexity is either O(n) when using auxiliary lists or O(1) when using an in-place placement strategy.