Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Arrays

Rearrange Array by Sign

Medium · Arrays · Asked at Amazon, Microsoft

The array has an equal number of positive and negative integers (no zeros). Rearrange it so signs alternate, starting with a positive, keeping the original relative order of positives and of negatives.

Input

First line: n. Second line: n space-separated integers.

Output

The rearranged array, space-separated.

Constraints

Example 1

Input

6
3 1 -2 -5 2 -4

Output

3 -2 1 -5 2 -4

Example 2

Input

2
-1 1

Output

1 -1

Hints

  1. The answer has positives at even indices (0, 2, 4…) and negatives at odd ones.
  2. Use two write pointers, pos = 0 and neg = 1, each jumping by 2.

Approach

Make a result array. Scan the input in order: put a positive number at result[pos] and move pos forward by 2; put a negative at result[neg] and move neg forward by 2. Each sign group keeps its original order, and the result starts with a positive.

Complexity: O(n) time · O(n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> res(n);
    int pos = 0, neg = 1;
    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;
        if (x > 0) { res[pos] = x; pos += 2; }
        else { res[neg] = x; neg += 2; }
    }
    for (int i = 0; i < n; i++) cout << res[i] << (i + 1 < n ? " " : "\n");
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n, a = data[0], data[1 : data[0] + 1]
res = [0] * n
res[0::2] = [x for x in a if x > 0]
res[1::2] = [x for x in a if x < 0]
print(*res)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] res = new long[n];
        int pos = 0, neg = 1;
        for (int i = 0; i < n; i++) {
            long x = sc.nextLong();
            if (x > 0) { res[pos] = x; pos += 2; }
            else { res[neg] = x; neg += 2; }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(i > 0 ? " " : "").append(res[i]);
        System.out.println(sb);
    }
}

Solve Rearrange Array by Sign online · All practice problems