Biweekly Contest 16

5134. Replace Elements with Greatest Element on Right Side

class Solution {
public:
    vector<int> replaceElements(vector<int>& arr) {
        int curmax = arr[arr.size()-1];
        vector<int> ret(arr.size(), 0);
        ret[arr.size()-1] = -1;
        for(int i=arr.size()-2; i>=0; i--){
            ret[i] = curmax;
            if(arr[i] > curmax) curmax = arr[i];
        }
        return ret;
    }
};

5135. Sum of Mutated Array Closest to Target

class Solution {
public:
    int check(vector<int>& arr, int mid){
        int sum = 0;
        for(int i=0; i<arr.size(); i++){
            if(arr[i] > mid)
                sum += mid;
            else 
                sum += arr[i];
        }
        return sum;
    }
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int l = 0;
        int r = arr[arr.size()-1];
        while(l < r){
            int mid = (l+r)>>1;
            if(check(arr, mid) >= target){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        int l1 = check(arr, l);
        int l2 = check(arr, l-1);
        if(abs(l1-target) < abs(l2-target)){
            return l;
        }else {
            return l-1;
        }
    }
};

1302. Deepest Leaves Sum

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxD = 0;
    int sum = 0;
    void getMD(TreeNode* root, int cur){
        if(!root) return;
        if(!root->left && !root->right){
            maxD = maxD > cur ? maxD: cur;
            return;
        }
        if(root->left) getMD(root->left, cur+1);
        if(root->right) getMD(root->right, cur+1);
    }
    void getSum(TreeNode* root, int cur){
        if(cur == maxD) {
            sum += root->val; return;
        }
        if(!root){
            return;
        }
        if(root->left) getSum(root->left, cur+1);
        if(root->right) getSum(root->right, cur+1);
    }
    int deepestLeavesSum(TreeNode* root) {
        getMD(root, 0);
        getSum(root, 0);
        return sum;
    }
};

1301. Number of Paths with Max Score

typedef long long ll;
const ll MOD = 1e9+7; 
const ll inf = 1e6;

class Solution {
    int n, m;
    int maze[110][110];
    pair<ll, ll> dp[110][110];
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        n = board.size();
        m = board[0].size();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(board[i][j] >= '0' && board[i][j] <= '9') maze[i][j] = board[i][j]-'0';
                else if(board[i][j] == 'S' || board[i][j] == 'E') maze[i][j] = 0;
                else  maze[i][j] = -inf;
            }
        }
        for(int i=0; i<=n; i++){
            for(int j=0; j<=m; j++)
                dp[i][j] = {-inf, 0};
        }
        dp[n-1][m-1] = {0, 1};
        for(int i=n-1; i>=0; i--){
            for(int j=m-1; j>=0; j--){
                if(i == n-1 && j == m-1) continue;
                dp[i][j].first = max({dp[i+1][j].first, dp[i][j+1].first, dp[i+1][j+1].first});
                dp[i][j].second = 0;
                if(dp[i+1][j].first == dp[i][j].first){
                    dp[i][j].second += dp[i+1][j].second;
                    dp[i][j].second %= MOD;
                }
                if(dp[i][j+1].first == dp[i][j].first){
                    dp[i][j].second += dp[i][j+1].second;
                    dp[i][j].second %= MOD;
                }
                if(dp[i+1][j+1].first == dp[i][j].first){
                    dp[i][j].second += dp[i+1][j+1].second;
                    dp[i][j].second %= MOD;
                }
                dp[i][j].first += maze[i][j];
                dp[i][j].first = max(-inf, dp[i][j].first);
            }
        }
        if(dp[0][0].first<0 || dp[0][0].second == 0) return {0,0};
        return {dp[0][0].first, dp[0][0].second};
    }
};