1649. Create Sorted Array through Instructions

Approach 1: Fenwick Tree

• Time: $O(n\log\max(\texttt{instructions}))$
• Space: $O(\max(\texttt{instructions}))$

C++

class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void add(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

 private:
  vector<int> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  int createSortedArray(vector<int>& instructions) {
    constexpr int kMod = 1'000'000'007;
    const int mx = ranges::max(instructions);
    int ans = 0;
    FenwickTree tree(mx);

    for (int i = 0; i < instructions.size(); ++i) {
      ans += min(tree.get(instructions[i] - 1), i - tree.get(instructions[i]));
      ans %= kMod;
      tree.add(instructions[i], 1);
    }

    return ans;
  }
};

Approach 2: Segment Tree w/ tree array

• Time: $O(n\log\max(\texttt{instructions}))$
• Space: $O(\max(\texttt{instructions}))$

C++

template <typename NodeType, typename ValueType>
class SegmentTree {
 public:
  explicit SegmentTree(const int n, const NodeType& defaultNode)
      : n(n), defaultNode(defaultNode), tree(4 * n) {}

  // Adds nums[i] to val equivalently.
  void add(int i, ValueType val) {
    add(0, 0, n - 1, i, val);
  }

  // Returns the result of the range query from nums[i..j].
  NodeType query(int i, int j) const {
    return query(0, 0, n - 1, i, j);
  }

 protected:
  // Merges the result of the left node and the right node.
  virtual NodeType merge(const NodeType& a, const NodeType& b) const = 0;
  virtual NodeType makeLeafNode(ValueType val) const = 0;

 private:
  const int n;                 // the size of the input array
  const NodeType defaultNode;  // default node value for non-overlapping queries
  vector<NodeType> tree;       // the segment tree

  void add(int treeIndex, int lo, int hi, int i, ValueType val) {
    if (lo == hi) {
      tree[treeIndex] += makeLeafNode(val);
      return;
    }
    const int mid = (lo + hi) / 2;
    if (i <= mid)
      add(left(treeIndex), lo, mid, i, val);
    else
      add(right(treeIndex), mid + 1, hi, i, val);
    tree[treeIndex] = merge(tree[left(treeIndex)], tree[right(treeIndex)]);
  }

  NodeType query(int treeIndex, int lo, int hi, int i, int j) const {
    if (i <= lo && hi <= j)  // [lo, hi] lies completely inside [i, j].
      return tree[treeIndex];
    if (j < lo || hi < i)  // [lo, hi] lies completely outside [i, j].
      return defaultNode;
    const int mid = (lo + hi) / 2;
    return merge(query(left(treeIndex), lo, mid, i, j),
                 query(right(treeIndex), mid + 1, hi, i, j));
  }

  int left(int treeIndex) const {
    return 2 * treeIndex + 1;
  }

  int right(int treeIndex) const {
    return 2 * treeIndex + 2;
  }
};

class SumSegmentTree : public SegmentTree<int, int> {
 public:
  explicit SumSegmentTree(int n) : SegmentTree(n, 0) {}

 protected:
  int merge(const int& a, const int& b) const override {
    return a + b;
  }

  int makeLeafNode(int val) const override {
    return val;
  }
};

class Solution {
 public:
  int createSortedArray(vector<int>& instructions) {
    constexpr int kMod = 1'000'000'007;
    const int mx = ranges::max(instructions);
    int ans = 0;
    SumSegmentTree tree(mx + 1);

    for (const int i : instructions) {
      ans += min(tree.query(0, i - 1), tree.query(i + 1, mx));
      ans %= kMod;
      tree.add(i, 1);
    }

    return ans;
  }
};

Approach 3: Merge Sort

• Time: $O(n\log n)$
• Space: $O(n\log n)$

C++

struct Item {
  int num;
  int index;
};

class Solution {
 public:
  int createSortedArray(vector<int>& instructions) {
    constexpr int kMod = 1'000'000'007;
    const int n = instructions.size();
    int ans = 0;
    vector<Item> items;
    // lesser[i] := the number of numbers < instructions[i]
    vector<int> lesser(n);
    // greater[i] := the number of numbers > instructions[i]
    vector<int> greater(n);

    for (int i = 0; i < n; ++i)
      items.push_back({instructions[i], i});

    mergeSort(items, 0, n - 1, lesser, greater);

    for (int i = 0; i < n; ++i) {
      ans += min(lesser[i], greater[i]);
      ans %= kMod;
    }

    return ans;
  }

 private:
  void mergeSort(vector<Item>& items, int l, int r, vector<int>& lesser,
                 vector<int>& greater) {
    if (l >= r)
      return;

    const int m = (l + r) / 2;
    mergeSort(items, l, m, lesser, greater);
    mergeSort(items, m + 1, r, lesser, greater);
    merge(items, l, m, r, lesser, greater);
  }

  void merge(vector<Item>& items, int l, int m, int r, vector<int>& lesser,
             vector<int>& greater) {
    int lo = l;  // the first index s.t. items[lo].num >= items[i].num
    int hi = l;  // the first index s.t. items[hi].num > items[i].num

    for (int i = m + 1; i <= r; ++i) {
      while (lo <= m && items[lo].num < items[i].num)
        ++lo;
      while (hi <= m && items[hi].num <= items[i].num)
        ++hi;
      lesser[items[i].index] += lo - l;
      greater[items[i].index] += m - hi + 1;
    }

    vector<Item> sorted(r - l + 1);
    int k = 0;      // sorted's index
    int i = l;      // left's index
    int j = m + 1;  // right's index

    while (i <= m && j <= r)
      if (items[i].num < items[j].num)
        sorted[k++] = items[i++];
      else
        sorted[k++] = items[j++];

    // Put the possible remaining left part into the sorted array.
    while (i <= m)
      sorted[k++] = items[i++];

    // Put the possible remaining right part into the sorted array.
    while (j <= r)
      sorted[k++] = items[j++];

    copy(sorted.begin(), sorted.end(), items.begin() + l);
  }
};