HackerRank‐Arrays - a920604a/leetcode GitHub Wiki

int hourglassSum(vector<vector<int>> arr) {
    int n  = arr.size(), m = arr[0].size();
    int ret=INT_MIN;
    for(int i=1;i<n-1;++i){
        for(int j=1;j<m-1;++j){
            int count = 0;
            count+=arr[i-1][j-1];
            count+=arr[i-1][j];
            count+=arr[i-1][j+1];
            count+=arr[i][j];
            count+=arr[i+1][j-1];
            count+=arr[i+1][j];
            count+=arr[i+1][j+1];
            ret = max(ret, count);
        }
    }
    return ret;
}

vector<int> rotLeft(vector<int> a, int d) {
    int n = a.size();
    d = d%n;
    vector<int> ret;
    for(int i=d;i<d+n;++i){
        ret.push_back(a[i%n]);
    }
    return ret;
}

void minimumBribes(vector<int> q) {
    int n = q.size();
    int cnt = 0;
    for(int i=n-1;i>-1;i--){
        if(q[i] != (i+1)){
            if( ((i-1)>=0) && (q[i-1] == (i+1) ) ){
                cnt++;
                swap(q[i], q[i-1]);
            }
            else if( ((i-2)>=0) &&( q[i-2] == (i+1))  ){
                cnt+=2;
                q[i-2] = q[i-1];
                q[i-1] = q[i];
                q[i] = i+1;
            }
            else{
                cout<<"Too chaotic"<<endl;
                return;
            }
        }
    }
    cout<<cnt<<endl;
}

// Complete the minimumSwaps function below.
int minimumSwaps(vector<int> arr) {
    int n = arr.size(), count=0;
    vector<int> vec(n+1,0);
    for(int i=0;i<n;++i) vec[arr[i]]=i;
    for(int i=0; i<n;++i){
        if(arr[i] !=  (i+1) ){
            count++;
            int t = arr[i];
            int idx = vec[i+1];
            swap(arr[i], arr[idx]);
            // swap  ,
            swap(vec[t], vec[i+1]);
        }
    }
    return count;
}

long arrayManipulation(int n, vector<vector<int>> queries) {
    //prefix sum 
    //  0   100 0 -100   0   0
    //  0   100 100 -100 0  0 
    //  0   100 100 0       -100
    //  0   100 200 200 200 100
    vector<long> prefix(n+1,0);
    for(vector<int> q:queries){
        prefix[q[0]]+=q[2];
        if(q[1]+1< n+1) prefix[q[1]+1]-=q[2];
    }
    long mx= 0;
    long cur_sum = 0;
    for(int i=1;i<n+1;++i){
        cur_sum+= prefix[i];
        mx = max(cur_sum, mx);
    }
    return mx;
}