Approach
Sorting and greedy selection
For Distribute Elements Into Two Arrays II, the implementation first exposes a useful order, then scans that order while making locally justified choices.
- Choose the key that reveals the greedy or grouping structure.
- Sort the relevant records by that key.
- Scan in order, maintaining the invariant that makes each local choice safe.
Code notes
- 74 lines of C++ from the credited upstream file 3072.cpp.
- The implementation visibly relies on sequence storage, hash lookup, ordered lookup.
- 4 loop blocks detected.
Complexity
Sorting is typically the dominant term unless the subsequent scan uses a more expensive nested operation.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
1class FenwickTree {2 public:3 FenwickTree(int n) : sums(n + 1) {}4 5 void add(int i, int delta) {6 while (i < sums.size()) {7 sums[i] += delta;8 i += lowbit(i);9 }10 }11 12 int get(int i) const {13 int sum = 0;14 while (i > 0) {15 sum += sums[i];16 i -= lowbit(i);17 }18 return sum;19 }20 21 private:22 vector<int> sums;23 24 static inline int lowbit(int i) {25 return i & -i;26 }27};28 29class Solution {30 public:31 vector<int> resultArray(vector<int>& nums) {32 vector<int> arr1;33 vector<int> arr2;34 const unordered_map<int, int> ranks = getRanks(nums);35 FenwickTree tree1(ranks.size());36 FenwickTree tree2(ranks.size());37 38 add(nums[0], arr1, tree1, ranks);39 add(nums[1], arr2, tree2, ranks);40 41 for (int i = 2; i < nums.size(); ++i) {42 const int greaterCount1 = arr1.size() - tree1.get(ranks.at(nums[i]));43 const int greaterCount2 = arr2.size() - tree2.get(ranks.at(nums[i]));44 if (greaterCount1 > greaterCount2)45 add(nums[i], arr1, tree1, ranks);46 else if (greaterCount1 < greaterCount2)47 add(nums[i], arr2, tree2, ranks);48 else if (arr1.size() > arr2.size())49 add(nums[i], arr2, tree2, ranks);50 else51 add(nums[i], arr1, tree1, ranks);52 }53 54 arr1.insert(arr1.end(), arr2.begin(), arr2.end());55 return arr1;56 }57 58 private:59 unordered_map<int, int> getRanks(const vector<int>& nums) {60 unordered_map<int, int> ranks;61 set<int> sorted(nums.begin(), nums.end());62 int rank = 0;63 for (const int num : sorted)64 ranks[num] = ++rank;65 return ranks;66 }67 68 void add(int num, vector<int>& arr, FenwickTree& tree,69 const unordered_map<int, int>& ranks) {70 arr.push_back(num);71 tree.add(ranks.at(num), 1);72 };73};74