1
class Solution {
2
// Uncomment/comment the below two lines for logs
3
// #define ENABLE_LOG(...) __VA_ARGS__
4
#define ENABLE_LOG(...)
5

6
 public:
7
  vector<int> rearrangeArray(vector<int> &nums) {
8
    const int chunk_size = (int)(sqrt(nums.size())) / 2 * 2 + 2; // make it always an even number
9
    const int original_n = nums.size();
10
    constexpr int kPadPositive = 100006;
11
    constexpr int kPadNegative = -100006;
12
    // Pad the array to have size of a multiple of 4 * chunk_size
13
    for (int i = 0; i < nums.size() % (4 * chunk_size); ++i) {
14
      nums.push_back(i % 2 == 0 ? kPadPositive : kPadNegative);
15
    }
16
    ENABLE_LOG(cout << "chunk_size: " << chunk_size << endl;
17

18
               cout << "padded array: "; for (int v : nums) cout << v << " "; cout << endl;)
19
    // Denotion:
20
    // the i-th positive number in original array: P_i.
21
    // the i-th negative number in original array: N_i
22

23
    // Step 1: Sort each chunk stably so that positive numbers appear before
24
    // negative numbers
25
    vector<int> chunk_buffer(chunk_size); // stores sorted result
26
    for (int i = 0; i < nums.size(); i += chunk_size) {
27
      chunk_buffer.clear();
28
      for (int j = i; j < i + chunk_size; ++j)
29
        if (nums[j] > 0) chunk_buffer.push_back(nums[j]);
30
      for (int j = i; j < i + chunk_size; ++j)
31
        if (nums[j] < 0) chunk_buffer.push_back(nums[j]);
32
      // Copy chunk_buffer back to nums[i:i+chunk_size]
33
      copy_n(chunk_buffer.cbegin(), chunk_size, nums.begin() + i);
34
    }
35
    ENABLE_LOG(cout << "chunk-sorted array: "; for (int v : nums) cout << v << " "; cout << endl;)
36

37
    // Step 2: Merge every two chunks so that each chunk are either all positive
38
    // numbers or all negative numbers
39
    //
40
    // This is based on the observation that:
41
    // assuming chunk A having m positives followed by n negatives,
42
    // chunk B having p positives followed by q negatives,
43
    // a) if m+p >= chunk_size, we extract chunk_size positives into an
44
    // all-positive chunk and put the remaining (m+p-chunk_size positives and
45
    // n+q negatives) into the "buffer" chunk b) if n+q >= chunk_size, we
46
    // extract chunk_size negatives into an all-negative chunk and make the
47
    // remaining (m+p positives and n+q-chunk_size negatives) the "buffer" chunk
48
    // Note that in either of the above two cases, the relative order for
49
    // positive/negative numbers are unchanged
50

51
    chunk_buffer = vector<int>{nums.begin(), nums.begin() + chunk_size};
52
    for (int i = chunk_size; i < nums.size(); i += chunk_size) {
53
      const int m =
54
          find_if(chunk_buffer.cbegin(), chunk_buffer.cend(), [](int v) { return v < 0; }) -
55
          chunk_buffer.cbegin();
56
      const int n = chunk_size - m;
57
      const int p =
58
          find_if(nums.cbegin() + i, nums.cbegin() + i + chunk_size, [](int v) { return v < 0; }) -
59
          (nums.cbegin() + i);
60
      const int q = chunk_size - p;
61

62
      if (m + p >= chunk_size) {
63
        // Copy positives to the previous chunk
64
        copy_n(chunk_buffer.cbegin(), m, nums.begin() + i - chunk_size);
65
        copy_n(nums.cbegin() + i, chunk_size - m, nums.begin() + i - chunk_size + m);
66
        vector<int> new_buffer;
67
        // the remaining positives (m+p-chunk_size) from this chunk
68
        copy_n(nums.cbegin() + i + (chunk_size - m), p - (chunk_size - m),
69
               back_inserter(new_buffer));
70
        // the remaining negatives in buffer
71
        copy_n(chunk_buffer.cbegin() + m, n, back_inserter(new_buffer));
72
        // the remaining negatives in this chunk
73
        copy_n(nums.cbegin() + i + p, q, back_inserter(new_buffer));
74
        chunk_buffer = move(new_buffer);
75
      } else {
76
        // Copy negatives to the previous chunk
77
        copy_n(chunk_buffer.cbegin() + m, n, nums.begin() + i - chunk_size);
78
        copy_n(nums.cbegin() + i + p, chunk_size - n, nums.begin() + i - chunk_size + n);
79
        vector<int> new_buffer;
80
        // the remaining positives in buffer
81
        copy_n(chunk_buffer.cbegin(), m, back_inserter(new_buffer));
82
        // the remaining positives in this chunk
83
        copy_n(nums.cbegin() + i, p, back_inserter(new_buffer));
84
        // the remaining negatives from this chunk
85
        copy_n(nums.cbegin() + i + p + chunk_size - n, q - (chunk_size - n),
86
               back_inserter(new_buffer));
87
        chunk_buffer = move(new_buffer);
88
      }
89
    }
90
    copy_n(chunk_buffer.cbegin(), chunk_size, nums.begin() + nums.size() - chunk_size);
91

92
    ENABLE_LOG(cout << "homonegeous array: "; for (int v : nums) cout << v << " "; cout << endl;)
93

94
    // Step 3:
95
    // After the above step, we will have sqrt(N) / 2 all-positive chunks and
96
    // sqrt(N) / 2 all-negative chunks. Their initial chunk location is at (0,
97
    // 1, 2, ..., sqrt(N)) We want them to interleave each other, i.e., Positive
98
    // Chunk1, Negative Chunk 1, Positive Chunk 2, Negative Chunk 2 which could
99
    // be achieved via cyclic permutation using an additional array tracking the
100
    // target location of each chunk
101

102
    // due to above padding, chunk_cnt is always a multiple of 4
103
    const int chunk_cnt = nums.size() / chunk_size;
104

105
    vector<int> target(chunk_cnt); // O(sqrt(N))
106
    int positive_chunks = 0, negative_chunks = 0;
107
    for (int i = 0; i < chunk_cnt; ++i) {
108
      if (nums[i * chunk_size] > 0)
109
        target[i] = (positive_chunks++) * 2;
110
      else
111
        target[i] = (negative_chunks++) * 2 + 1;
112
    }
113
    for (int i = 0; i < chunk_cnt; ++i) {
114
      while (target[i] != i) {
115
        swap_ranges(nums.begin() + i * chunk_size, nums.begin() + i * chunk_size + chunk_size,
116
                    nums.begin() + target[i] * chunk_size);
117
        swap(target[target[i]], target[i]);
118
      }
119
    }
120
    ENABLE_LOG(cout << "sorted array: "; for (int v : nums) cout << v << " "; cout << endl;)
121

122
    // Step 4:
123
    // Now we get Positive Chunk1, Negative Chunk 1, Positive Chunk 2, Negative
124
    // Chunk 2, ... For each pair of adjacent (positive, negative) chunks, we
125
    // can reorder the elements inside to make positive and negative numbers
126
    // interleave each other
127
    vector<int> two_chunk_elements_interleaved; // O(2 * chunk_size) = O(sqrt(N))
128
    for (int i = 0; i < nums.size(); i += 2 * chunk_size) {
129
      two_chunk_elements_interleaved.clear();
130
      for (int j = 0; j < chunk_size; ++j) {
131
        two_chunk_elements_interleaved.push_back(nums[i + j]);
132
        two_chunk_elements_interleaved.push_back(nums[i + chunk_size + j]);
133
      }
134
      copy_n(two_chunk_elements_interleaved.cbegin(), 2 * chunk_size, nums.begin() + i);
135
    }
136
    // Remove paddings
137
    nums.resize(original_n);
138
    return nums;
139
  }
140
};