LeetCode - Weekly Contest 273 Editorial

Q1: A Number After a Double Reversal

If you just do what it says, here's the code.

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

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<int> executeInstructions(int n, vector<int>& startPos, string s) {
        int m = s.size();
        vector<int> 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<int> executeInstructions(int n, vector<int>& startPos, string s) {
        int m = s.size(), h = m + n, v = m + n;
        vector<int> 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

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<int>& 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<int> 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

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<int> recoverArray(vector<int>& 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<int> 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<int> ans;
                for (int j = 0; j < n / 2; j++) {
                    ans.push_back((l[j] + r[j]) / 2);
                }
                return ans;
            }
        }
        return {};
    }
};