LeetCode - Weekly Contest 273 Editorial

## [Q1: A Number After a Double Reversal](https://leetcode.com/problems/a-number-after-a-double-reversal/) If you just do what it says, here's the code. ```cpp class Solution { public: bool isSameAfterReversals(int num) { if (num == 0) return 1; string s = to_string(num); int n = s.size(), j = 0; while (s[n - 1 - j] == '0') j++; string t = s.substr(0, n - j); return s == t; } }; ``` However, a better way to solve this is to check if there is any trailing zero. No matter how many zeros at the end, after removing them all, it won't be same if you reverse it. The only exceptional case is $num = 0$. ``` class Solution { public: bool isSameAfterReversals(int num) { return num == 0 || num % 10; } }; ``` ## [Q2: Execution of All Suffix Instructions Staying in a Grid](https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/) We can just simulate the whole process. For each $i-th$ instruction, we have max $ s.size() - i $ steps assuming $ i $ starts from $ 0 $. We keep updating the position $(x, y)$ and check if it is out of bound. If not, keep inceasing $cnt$ by 1. If there is no further move we can make, we can break the loop and push the result $cnt$ to $ans$. ``` class Solution { public: vector executeInstructions(int n, vector& startPos, string s) { int m = s.size(); vector ans; for (int i = 0; i < m; i++) { int x = startPos[0]; int y = startPos[1]; int cnt = 0; for (int j = i; j < m; j++) { if (s[j] == 'L') y--; if (s[j] == 'R') y++; if (s[j] == 'U') x--; if (s[j] == 'D') x++; if (0 <= x && x < n && 0 <= y && y < n) cnt++; else break; } ans.push_back(cnt); } return ans; } }; ``` However, the above brute-force solution gives $O(m^2)$ complexity. It works because $m$ is just limited to $1000$. There's a $O(m)$ solution. ``` class Solution { public: vector executeInstructions(int n, vector& startPos, string s) { int m = s.size(), h = m + n, v = m + n; vector hor((m + n) * 2, m), ver((m + n) * 2, m), ans(m); for (int i = m - 1; i >= 0; i--) { hor[h] = ver[v] = i; if (s[i] == 'L') h++; if (s[i] == 'R') h--; if (s[i] == 'U') v++; if (s[i] == 'D') v--; ans[i] = min({ m, hor[h - startPos[1] - 1], hor[h - startPos[1] + n], ver[v - startPos[0] - 1], ver[v + startPos[0] * -1 + n] }) - i; } return ans; } }; ``` ## [Intervals Between Identical Elements](intervals-between-identical-elements) First we need to know the indices for each number. We can easily construct it using ``unordered_map<int, vector<int>>``. Then it comes to the math part. Our goal is to calculate the absolute difference for numbers smaller than and greater than or equal to $k$ in linear time. Let's say the list is [1, 3, 5, 7, 9] and let $k$ be $7$. The absolute difference for numbers smaller than or equal to $7$ is $(7 - 1) + (7 - 3) + (7 - 5) - (7 - 7)$. We can arrange it to $ 7 * 4 - (1 - 3 - 5 - 7)$ which is same as $k * (i + 1) - pre[i + 1]$. Similarly, let $k$ be $3$ and we want to find out the absolute difference for numbers greater than or equal to $3$. $(3 - 3) + (3 - 5) + (3 - 7) + (3 - 9)$. We can arrange it to $3 * 4 - (3 + 5 + 7 + 9)$, which is same as $(pre[n] - pre[i]) - k * (n - i)$. Therefore, $ans[k]$ would be the sum of the left part and the right part. Prefix sum can be calculated as ``` for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + v[i]; } ``` ``` class Solution { public: vector<long long> getDistances(vector& arr) { unordered_map<int, vector<int>> m; vector<long long> ans(arr.size()); int n = arr.size(); for (int i = 0; i < n; i++) { m[arr[i]].push_back(i); } for (auto x : m) { vector v = x.second; int n = v.size(); vector<long long> pre(n + 1); for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + v[i]; } for (int i = 0; i < n; i++) { long long k = v[i]; ans[k] = (k * (i + 1) - pre[i + 1]) + (pre[n] - pre[i] - k * (n - i)); } } return ans; } }; ``` ## [Recover the Original Array](https://leetcode.com/problems/recover-the-original-array/) In short, we just need to try all possible $k$. If we sort $nums$, the smallest elelment must be in the lower array. It is easy to see $k$ can be $(nums[i] - nums[0]) / 2$. We try each $k$ to see if we can match all the pairs. If the size of lower array is same as that of higher array, then the ans would be $ans[j] = (l[j] + r[j]) / 2$. ``` class Solution { public: vector recoverArray(vector& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { unordered_map<int, int> m; int d = nums[i] - nums.front(); if (d == 0 || d & 1) { continue; } vector l, r; for (int j = 0; j < n; j++) { if (m.count(nums[j] - d)) { r.push_back(nums[j]); if (--m[nums[j] - d] == 0) { m.erase(nums[j] - d); } } else { l.push_back(nums[j]); m[nums[j]]++; } } if (l.size() == r.size()) { vector ans; for (int j = 0; j < n / 2; j++) { ans.push_back((l[j] + r[j]) / 2); } return ans; } } return {}; } }; ```