@shawngao This is DP solution, somehow similar to buy/sell stock. Nice one!
votrubac
@votrubac
Posts made by votrubac

RE: Java solution, left max and right min.

C++ 7 lines, O (n * log n) / O(n)
Same as Max Chunks To Make Sorted (ver. 1). We just need to normalize the input array so it contains the indexes. We use the sorting for the normalization, and one trick here is to have a stable sort, so that if we have the same value, the index will be lowest for the value appearing first.
int maxChunksToSorted(vector<int>& v) { vector<int> arr(v.size()); iota(arr.begin(), arr.end(), 0); sort(arr.begin(), arr.end(), [&v](int i1, int i2) {return v[i1] == v[i2] ? i1 < i2 : v[i1] < v[i2]; }); for (auto i = 0, max_i = 0, ch = 0; i <= arr.size(); ++i) { if (i == arr.size()) return ch; max_i = max(max_i, arr[i]); if (max_i == i) ++ch; } }

C++ 4 lines O(n) / O(1)
Similiar to 763. Partition Labels.
int maxChunksToSorted(vector<int>& arr) { for (auto i = 0, max_i = 0, ch = 0; i <= arr.size(); ++i) { if (i == arr.size()) return ch; max_i = max(max_i, arr[i]); if (max_i == i) ++ch; } }

RE: Python O(n)
@votrubac said in Naïve solution accepted (with a proof)... wrong difficulty?:
@alexander It looks like the search and swap is the optimal solution and there is no missing test cases.
We can have three cases:
 Pairs like [0, 0] and [1, 1], no swaps required. The solution covers that.
 Pairs like [0, 1] and [0, 1], one swap is required to complete two pairs. The solution covers that.
 Pairs like [0, 1], [1, 2] and [0, 2], two swaps is required to complete two pairs. The solution covers that.
A generalization of step 3: pairs like [0, 1], [1, 2], ... [N  2, N  1], [N  1, 0]. We need to do a swap for each pair except the last one. So, we will need total N  1 swaps to complete N pairs. This can be easily proven by the induction.
Since the naive solution gives the correct result for all three cases, it is optimal.

RE: Naïve solution accepted (with a proof)... wrong difficulty?
@moksh that was my problem as well. When the input is constrained like that in LeetCode, that typically indicate that the solution needs to analyze multiple permutations.

[Monster Style] C++ O(n) unordered_map
The intuition for this solution came after I solved this problem using C++ O(n) unordered_multimap.
For each unmatched pair [k, v], we add it to the hash map using the lower number as the key. If the hash map already contains a pair [k, v'] with that key, we need to form a new pair [v, v'], where v < v'. We continue the process recursively until either v == v' (matched pair that can be skipped), or there is no existing pair with that key.
In the end, the number of elements in the hash map is the number of swaps required to match all pairs.
void insert_helper(unordered_map<int, int>& m, int v1, int v2) { auto k = min(v1, v2), v = max(v1, v2); if (k != v) { // it's a right couple, no need to track. if (m.count(k) > 0) insert_helper(m, m[k], v); else m[k] = v; } } int minSwapsCouples(vector<int>& row) { unordered_map<int, int> m; for (auto i = 0; i < row.size(); i += 2) insert_helper(m, row[i] / 2, row[i + 1] / 2); return m.size(); }

RE: C++ 6 lines O(n) / O(1)  two simple passes
@lailianqi thanks for noticing, that was my original solution as well, but I wanted to save one line :)
Apparently, it is not justifiable as it created a bug and impacted the readability. I've changed my solution back to the original state. 
C++ O(n) unordered_multimap
This solution is optimized for pair lookup. Initially, we fill the multimap with pairs (smaller value is the key). Then, we iterate through 0..N1. If for a number i there are two pairs, that means we need a swap. We add a new pair using values from these two pairs (smaller value is the key). Note that the key of the added pair will be greater than i, so it will be always processed.
Also note that we do not need to remove existing pair as we won't touch i again.
int minSwapsCouples(vector<int>& row) { unordered_multimap<int, int> m; for (auto i = 0; i < row.size(); i += 2) m.insert({ min(row[i] / 2, row[i + 1] / 2), max(row[i] / 2, row[i + 1] / 2) }); for (auto i = 0, res = 0; i <= row.size() / 2; ++i) { if (i == row.size() / 2) return res; auto it = m.equal_range(i); if (next(it.first) != it.second) { ++res; m.insert({ min(it.first>second, next(it.first)>second), max(it.first>second, next(it.first)>second) }); } } }