Prefix and Suffix Aggregates

Minimum range to sort to get a fully sorted array in O(n) and O(1)

Link: https://leetcode.com/problems/shortest-unsorted-continuous-subarray/

Note that you can also use the “boundaries” approach here. Boundary = where prefix max ⇐ suffix min.

int findUnsortedSubarray(vector<int>& nums) {
    // observation
    // starting from right, try to go as far as you can left
    // such that max in prefix to left < nums[i]
    // similarly starting from left try to go as far to right
    // such that min in suffix to right > nums[i]
    // this is then basically prefix and suffix min/max
    // which is trivial
 
    // can I do no space?
    // try to move in the direction of "accumulation"
    // so for finding the right boundary, try to find an inversion
    // i,j such that i<j and nums[j]<nums[i], nums[i] can be max in the prefix then
    // for each j, this is the range you absolutely must sort
    const int INF = (int)1e9;
    int n = (int)nums.size();
    int end = -1, pref_max = nums[0];
    for (int i = 1; i < n; i++) {
        if (nums[i] < pref_max) end = i;
        pref_max = max(pref_max, nums[i]);
    }
    int start = -1, suff_min = nums.back();
    for (int i = n - 1; i >= 0; i--) {
        if (nums[i] > suff_min) start = i;
        suff_min = min(suff_min, nums[i]);
    }
    assert(end != -1 && start != -1 || end == -1 && start == -1);
    if (end == -1) return 0;
    return end - start + 1;
}

For tuples (i,j), pairs where both are larger

int numberOfWeakCharacters(vector<vector<int>>& v) {
    // observation
    // this is the usual two property check type of problems
    // since the numbers are small for attack(i)
    // make an array for it and then find the suffix maximums
 
    // bucket sort trick
 
    int n = v.size();
    const int N = (int)1e5 + 5;
    vector<int> def_for_atk(N);
    for (int i = 0; i < n; i++) {
        int atk = v[i][0], def = v[i][1];
        def_for_atk[atk] = max(def_for_atk[atk], def);
    }
 
    for (int i = N - 2; i >= 0; i--) {
        def_for_atk[i] = max(def_for_atk[i + 1], def_for_atk[i]);
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int atk = v[i][0], def = v[i][1];
        int mx_def_after = def_for_atk[atk + 1];
        if (mx_def_after > def) ans++;
    }
 
    return ans;
}