GeeksForGeeks - POTD | GFG POTD Answer

public:
    int minimizeDifference(int n, int k, vector<int> &arr) {
        vector<int> post_max(n), post_min(n);
        post_max[n - 1] = post_min[n - 1] = arr[n - 1];
        
        for(int i = n - 2; i >= 0; i--) {
            post_max[i] = max(arr[i], post_max[i + 1]);
            post_min[i] = min(arr[i], post_min[i + 1]);
        }
        
        int mini = arr[0], maxi = arr[0], res = post_max[k] - post_min[k];
        
        for(int i = 1; i < n - k; i++) {
            res = min(res, max(maxi, post_max[i + k]) - min(mini, post_min[i + k]));
            mini = min(mini, arr[i]);
            maxi = max(maxi, arr[i]);
        }
        
        res = min(res, maxi - mini);
        
        return res;
    }
};

class Solution {
  public:
    vector<int> countElements(vector<int> &a, vector<int> &b, int n, vector<int> &query,
                              int q) {
        vector<int> ans;        
        sort(b.begin(), b.end());        
        for(int i=0; i<q; i++)
        {
            int count=upper_bound(b.begin(), b.end(), a[query[i]]) - b.begin();
            ans.push_back(count);
        }
        
        return ans;
    }
};

class Solution {
  public:
    void printArr(int n, int arr[]) {
        for(int i = 0; i < n; i++)
            cout << arr[i] << " ";
            
        cout << endl;
    }

    void setToZero(int n, int arr[]) {
        for(int i = 0; i < n; i++)
            arr[i] = 0;
    }

    void xor1ToN(int n, int arr[]) {
        for(int i = 0; i < n; i++)
            arr[i] ^= i;
    }
};

class Solution {
  public:
    long long reversedBits(long long x) {
       
        long long ans = 0;
        for(int i=0; i<32; i++)
        {
            long long bit = (x>>i)&1;
            ans = ans | (bit<<(31-i));
        }
        return ans;
}
};

class Solution {
  public:
    long long pairAndSum(int n, long long arr[]) {
        long long ans = 0;

        for(int i = 0;i < 32; i++) {
            long long count = 0;
            for(int j = 0;j < n; j++) {
                if(arr[j] & (1<<i))
                    count++;
            }

            ans += 1ll*(count*(count-1)/2)*(1ll<<i);
        }

        return ans;
    }
};

class Solution{
    public:
    int grayToBinary( int g ) {
    int b{};
    do b ^= g;
    while ( g /= 2 );
    return b;
    }
};

class Solution{
    public:
    int findSingle(int n, int arr[]){
    int xor1 = 0;
    for(int i=0; i<n; i++) xor1 = xor1 ^ arr[i];
    return xor1;
    }
};

class Solution{
public:
    int minPoints(int m, int n, vector<vector<int>>& points) {
        vector<vector<int>> dp(m, vector<int>(n, 0));
        dp[m - 1][n - 1] = points[m - 1][n - 1] > 0 ? 1 : abs(points[m - 1][n - 1]) + 1;
        
        // Fill the last column
        for (int i = m - 2; i >= 0; --i) {
            dp[i][n - 1] = max(1, dp[i + 1][n - 1] - points[i][n - 1]);
        }
        
        // Fill the last row
        for (int j = n - 2; j >= 0; --j) {
            dp[m - 1][j] = max(1, dp[m - 1][j + 1] - points[m - 1][j]);
        }
        
        // Fill the rest of the grid
        for (int i = m - 2; i >= 0; --i) {
            for (int j = n - 2; j >= 0; --j) {
                int min_points_on_exit = min(dp[i + 1][j], dp[i][j + 1]);
                dp[i][j] = max(1, min_points_on_exit - points[i][j]);
            }
        }
        
        return dp[0][0];
    }
};