2025. Maximum Number of Ways to Partition an Array

You are given a 0-indexed integer array nums of length n. The number of ways to partition nums is the number of pivot indices that satisfy both conditions:

• 1 <= pivot < n
• nums[0] + nums[1] + … + nums[pivot - 1] == nums[pivot] + nums[pivot + 1] + … + nums[n - 1]

You are also given an integer k. You can choose to change the value of one element of nums to k, or to leave the array unchanged.

Return the maximum possible number of ways to partition nums to satisfy both conditions after changing at most one element.

• O(n) solution

class Solution {
public:
    int waysToPartition(vector<int>& nums, int k) {
        int n = nums.size(), res = 0;
        vector<long long> psum(n, nums[0]);
        unordered_map<long long,deque<int>> r,l{{nums[0],{0}}};
        vector<int> start(n,0), end(n,0);
        unordered_map<int, int> mp;
        
        for(int i = 1; i < n; i++) {
            psum[i] = psum[i-1] + nums[i];
            r[nums[i]].push_back(i);
        }
        
        for(int i = 0; i < n - 1; i++) {
            long long lreq = psum.back() - 2 * psum[i], rreq = -lreq;
            if(rreq == lreq) res++;
            else {
                if(r.count(k-rreq)) {
                    start[r[k-rreq].front()]++;
                    end[r[k-rreq].back()]--;
                }
                if(l.count(k-lreq)) {
                    start[l[k-lreq].front()]++;
                    end[l[k-lreq].back()]--;
                }
            }
            if(l[nums[i+1]].size() == 2)
                l[nums[i+1]].pop_back();
            
            l[nums[i+1]].push_back(i+1);
            r[nums[i+1]].pop_front();
            
            if(r[nums[i+1]].empty())
                r.erase(nums[i+1]);
        }
        
        for(int i = 0; i < n; i++) {
            mp[nums[i]] += start[i];
            res = max(res, mp[nums[i]]);
            mp[nums[i]] += end[i];
        }
        
        return res;
    }
};

• O(nlogn) solution with kadane algorithm

class Solution {
    int solve(vector<pair<int,int>>& q) {
        sort(begin(q), end(q));
        priority_queue<int, vector<int>, greater<int>> pq;
        int sum = 0, res = 0;
        for(int i = 0; i < q.size(); i++) {
            while(!pq.empty() and pq.top() < q[i].first) {
                sum -= 1;
                pq.pop();
            }
            sum += 1;
            pq.push(q[i].second);
            res = max(res, sum);
            if(sum + q.size() - i - 1 < res) break;
        }
        return res;
    }
public:
    int waysToPartition(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> psum(n, nums[0]);
        unordered_map<long long,deque<int>> r,l{{nums[0],{0}}};
        unordered_map<long long, vector<pair<int,int>>> query;
        for(int i = 1; i < n; i++) {
            psum[i] = psum[i-1] + nums[i];
            r[nums[i]].push_back(i);
        }
        int res = 0;
        for(int i = 0; i < n - 1; i++) {
            long long lreq = psum.back() - psum[i] - psum[i], rreq = -lreq;
            if(rreq == lreq) res++;
            else {
                if(!r[k-rreq].empty()) {
                    query[k-rreq].push_back({r[k-rreq].front(), r[k-rreq].back()});
                }
                if(!l[k-lreq].empty()) {
                    query[k-lreq].push_back({l[k-lreq].front(), l[k-lreq].back()});
                }
            }
            l[nums[i+1]].push_back(i+1);
            r[nums[i+1]].pop_front();
        }
        
        for(auto& [_, q] : query) {
            res = max(res,solve(q));
        }
        
        return res;
    }
};

• o(n^2) solution

class Solution {
public:
    int waysToPartition(vector<int>& nums, int k) {
        int n = nums.size();
        vector<long long> psum(n, nums[0]);
        unordered_map<long long,deque<int>> r,l{{nums[0],{0}}};
        for(int i = 1; i < n; i++) {
            psum[i] = psum[i-1] + nums[i];
            r[nums[i]].push_back(i);
        }
        vector<int> res(n+1,0);
        for(int i = 0; i < n - 1; i++) {
            long long lreq = psum.back() - psum[i] - psum[i], rreq = -lreq;
            if(rreq == lreq) res[n]++;
            else {
                for(auto& ind : r[k-rreq])
                    res[ind]++;
                for(auto& ind : l[k-lreq])
                    res[ind]++;
            }
            l[nums[i+1]].push_back(i+1);
            r[nums[i+1]].pop_front();
        }
        return *max_element(begin(res),end(res));
    }
};