[Leetcode]: 2536. Increment Submatrices by One

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.

You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation:

Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). That is, add 1 to mat[x][y] for for all row1i <= x <= row2i and col1i <= y <= col2i.

Return the matrix mat after performing every query.

Constraints:

1 <= n <= 500

1 <= queries.length <= 10^4

0 <= row1i <= row2i < n

0 <= col1i <= col2i < n

Analysis:

This question looks very straightforward: for each query, we can just update all the elements in the block by adding 1. But the overall time complexity is O(10^4 * n * n) ~ O (25 x 10^6), which cannot pass the large cases in the OJ.

So how can we improve it?

One way is to lower the dimension: from 2D to 1D. Then for the 1D problem, we can solve it using scanning line algorithm. The key observation is that, for each update (or query), we just need to adjust the staring and the ending of the range (for example, the beginning is +1, and the ending is -1), and we do not need to do the updates for every element between the starting and ending. Then we can run a one-time accumulation from left to right to get the actual updates for all the elements.

So similarly, for 2D we can add a labeling for the changes in a block by just update the four corners of the block: 

1. the top left corner: +1;

2. the top right corner: -1;

3. the bottom left corner: -1;

4. the bottom right corner: +1.

How do we rationalize this?

1 is for the staring of the change; 2 and 3 means the end of the changes in horizontal and vertical directions, respectively; then what is 4 for?

The reason is simple: by ending the change in 2 and 3, we have double the changing in range staring with 4. But we just need one change. So we need to set it back by adding 1.

After the labeling, we can get the updated values for every elements by performing accumulations like the case in 1D.

The 2D accumulation formula is:

1: res[i][j] +=  changes[i][j]

2. res[i][j] += res[i-1][j];

3. res[i][j] += res[i][j-1];

4. res[i][j] -= res[i-1][j-1].

res[i][j] is the accumulated sum (like a prefix sum) of the block starting from top left corner (0, 0) to bottom right corner (i, j).

The changes[i][j] is for the changes at the (i, j).

The sum of the block except the element at (i, j) is: res[i-1][j] + res[i[j-1] - res[i-1][j-1]. (why?)

Thus the formula is:

res[i][j] = changes[i][j] + res[i-1][j] + res[i][j-1] - res[i-1][j-1]

which is the sum of the above formula from 1 to 4.

For easier coding, we set the change matrix with one more row and column than that of the element matrix.

See the code below:

class Solution {
public:
    vector<vector<int>> rangeAddQueries(int n, vector<vector<int>>& queries) {
        vector<vector<int>> res(n, vector<int>(n, 0)), diff(n+1, vector<int>(n+1, 0));
        for(auto &a : queries) {
            int x1 = a[0], y1 = a[1], x2 = a[2], y2 = a[3];
            ++diff[x1][y1];
            --diff[x1][y2+1];
            --diff[x2+1][y1];
            ++diff[x2+1][y2+1];
        }
        for(int i=0; i<n; ++i) {
            for(int j=0; j<n; ++j) {
                res[i][j] += diff[i][j];
                if(i>0) res[i][j] += res[i-1][j];
                if(j>0) res[i][j] += res[i][j-1];
                if(i>0 && j>0) res[i][j] -= res[i-1][j-1];
            }
        }
        return res;
    }
};

[Leetcode] 2296. Design a Text Editor

2296. Design a Text Editor

Design a text editor with a cursor that can do the following:

Add text to where the cursor is.

Delete text from where the cursor is (simulating the backspace key).

Move the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that 0 <= cursor.position <= currentText.length always holds.

Implement the TextEditor class:

TextEditor() Initializes the object with empty text.

void addText(string text) Appends text to where the cursor is. The cursor ends to the right of text.

int deleteText(int k) Deletes k characters to the left of the cursor. Returns the number of characters actually deleted.

string cursorLeft(int k) Moves the cursor to the left k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

string cursorRight(int k) Moves the cursor to the right k times. Returns the last min(10, len) characters to the left of the cursor, where len is the number of characters to the left of the cursor.

Constraints:

1 <= text.length, k <= 40

text consists of lowercase English letters.

At most 2 * 10^4 calls in total will be made to addText, deleteText, cursorLeft and cursorRight.

Analysis:

This question is labeled as hard in Leetcode, but the logic is quick straightforward. The only problem is the efficiency. 

If we use a string and an index for the cursor position, then we will see TLE or MLE.

One neat method is to use two stacks, one is the left stack and the other is right stack. 

For add, we just push the new string into left stack;

for delete, we just pop up the chars from the left stack;

for leftMove, we just pop out k or less (if less than k elements remains) chars from left stack, and push in right stack; then return 10 or less(if less than 10 elements remains) from the left stack;

for rightMore we just need to do the reversed operation as that for the leftMove.

See the code below

class TextEditor {
public:
    TextEditor() {
    }
    
    void addText(string text) {
        for(auto &a : text) lt.push(a);
    }
    
    int deleteText(int k) {
        int res = 0;
        while (lt.size() && k > 0) {
            lt.pop();
            ++res;
            --k;
        }
        // cout << "delet" << endl;
        return res;
    }
    
    string cursorLeft(int k) {
        while(lt.size() && k > 0) {
            auto t = lt.top();
            lt.pop();
            rt.push(t);
            --k;
        }
        return f(lt, 10);
    }
    
    string cursorRight(int k) {
         while(rt.size() && k > 0) {
            auto t = rt.top();
            rt.pop();
            lt.push(t);
            --k;
        }
        return f(lt, 10);
    }
private:
    stack<int> lt, rt;
    string f(stack<int> &sk, int k) {
        string res;
        while(sk.size() && k > 0) {
            res.push_back(sk.top());
            sk.pop();
            --k;
        }
        reverse(res.begin(), res.end());
        for(auto &a : res) sk.push(a);
        return res;
    }
};

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor* obj = new TextEditor();
 * obj->addText(text);
 * int param_2 = obj->deleteText(k);
 * string param_3 = obj->cursorLeft(k);
 * string param_4 = obj->cursorRight(k);
 */

[Leetcode] 2293. Min Max Game

2293. Min Max Game

You are given a 0-indexed integer array nums whose length is a power of 2.

Apply the following algorithm on nums:

Let n be the length of nums. If n == 1, end the process. Otherwise, create a new 0-indexed integer array newNums of length n / 2.

For every even index i where 0 <= i < n / 2, assign the value of newNums[i] as min(nums[2 * i], nums[2 * i + 1]).

For every odd index i where 0 <= i < n / 2, assign the value of newNums[i] as max(nums[2 * i], nums[2 * i + 1]).

Replace the array nums with newNums.

Repeat the entire process starting from step 1.

Return the last number that remains in nums after applying the algorithm.

Constraints:

1 <= nums.length <= 1024

1 <= nums[i] <= 10^9

nums.length is a power of 2.

Analysis

This question can be resolved by the classic Divide and Conquer algorithm.

The only extra thing is we need a flag to indicate whether it is the first half or the second half.

when flag == 0, we choose the min;

when flag == 1, we choose the max.

See the code below:

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        return f(nums, 0, nums.size(), 0);
    }
private:
    int f(vector<int>&ns, int left, int right, int flag) {
        if(left+1 == right) return ns[left];
        int mid = left + (right - left)/2;
        int x = f(ns, left, mid, 0), y = f(ns, mid, right, 1);
        return flag ? max(x, y) : min(x, y);
    }
};

[Leetcode] 2145. Count the Hidden Sequences

2262. Total Appeal of A String

The appeal of a string is the number of distinct characters found in the string.

For example, the appeal of "abbca" is 3 because it has 3 distinct characters: 'a', 'b', and 'c'.

Given a string s, return the total appeal of all of its substrings.

A substring is a contiguous sequence of characters within a string.

Constraints:

1 <= s.length <= 10^5

s consists of lowercase English letters.

Analysis:

This question is quite straightforward if we do not care about the time complexity.

The upper bound is O(n^2), where n is the total number of chars in the string, since we only have O(n^2) substrings in total. (If we count the number of unique chars while expanding, the time complexity is O(n^2); if count after the expanding, the time complexity is O(n^3)).

But O(n^2) is not the optimal solution, which cannot pass the OJ since n could be 10^5.

One way to think about this question is that: when we add a new char [C] into account and the index of the new char is idx, then we will have (idx + 1) new substrings ending with C.

For all the (id+1) substrings, we have calculated (or known) the total unique chars before the last char, or the new char C.

Since we only care about the unique chars, we just need to know when the char C appears last time, or we just need to know the index of the previous char C, prev_idx. Before this position, the new char is not considered as a unique one. After this position, the new char will contribute 1 to the count. For all the (idx + 1) new substrings ending with the new char C, the total delta to total count is (idx - prev_idx) due to the new char C, or

delta = idx - prev_idx

If we have memorize the total count of the unique chars for the (id+1) new substrings excluding the new char C as prev_count, then we can update this to (prev_count + delta), or

cur_count = prev + delta

This is the total increase in count by taking the new char C into account.

So we just need to sum up all of these for each char in the string.

A tiny trick can be used with a vector of size ~ 26 to record the previous index of each char.

The time complexity is O(n), and space complexity is O(26), where n is the number of elements.

See the code below:

class Solution {
public:
    long long appealSum(string s) {
        long long res = 0, n = s.size(), prev_count = 0;
        vector<long long> cts(26, -1);
        for(int i=0; i<n; ++i) {
            int id = s[i] - 'a';
            int delta = i - cts[id];
            int cur_count = prev_count + delta;
            res += cur_count;
            // update
            prev_count = cur_count;
            cts[id] = i;
        }
        return res;
    }
};

[Leetcode] 2145. Count the Hidden Sequences

2145. Count the Hidden Sequences

You are given a 0-indexed array of n integers differences, which describes the differences between each pair of consecutive integers of a hidden sequence of length (n + 1). More formally, call the hidden sequence hidden, then we have that differences[i] = hidden[i + 1] - hidden[i].

You are further given two integers lower and upper that describe the inclusive range of values [lower, upper] that the hidden sequence can contain.

For example, given differences = [1, -3, 4], lower = 1, upper = 6, the hidden sequence is a sequence of length 4 whose elements are in between 1 and 6 (inclusive).

[3, 4, 1, 5] and [4, 5, 2, 6] are possible hidden sequences.

[5, 6, 3, 7] is not possible since it contains an element greater than 6.

[1, 2, 3, 4] is not possible since the differences are not correct.

Return the number of possible hidden sequences there are. If there are no possible sequences, return 0.

Constraints:

n == differences.length

1 <= n <= 10^5

-10^5 <= differences[i] <= 10^5

-10^5 <= lower <= upper <= 10^5 

Analysis:

This question is quick interesting, which needs some derivations. 

If check the first example carefully, this question is equivalent to ask for the total number of valid first element A0.

Since the values of all the elements should be in some range, then we just need to take care of the minimum and maximum of the elements. Or if the minimum and maximum elements valid, then all the rest should be valid as well.

So we can write down some equations first:

lower <= A0 <= upper        (1)

lower <= Amin <= upper    (2)

lower <= Amax <= upper    (3)

How to find the Amin and Amax?

The only thing we know is the diffs. So we can get the (Amin - A0) and (Amax - A0) by cumulating the diffs from the first one.

Once we get these two values, Dmin and Dmax, we can modify the equations above a little bit:

Amin - A0 = Dmin   =>  Amin = A0 + Dmin

Amax - A0 = Dmax  =>  Amax = A0 + Dmax

Then we can re-write (2) and (3)

lower <= A0 + Dmin <= upper    => lower - Dmin <= A0 <= upper - Dmin    (4)

lower <= A0 + Dmax <= upper   => lower - Dmax <= A0 <= upper - Dmax   (5)

Putting (1), (4) and (5) together, we can derive the valid range of A0,

max(lower, lower - Dmin, lower - Dmax)  <= A0 <= min(upper, upper - Dmin, upper - Dmax)

Since (lower - Dmin) is always no larger than (lower - Dmax), and (upper - Dmin) <= (upper - Dmax), the above range can be re-written as

max(lower, lower - Dmin) <= A0 <= min(upper, upper - Dmax).

The time complexity is O(n), and space complexity is O(1), where n is the number of elements.

See the code below:

class Solution {
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        long sum = 0, mn = differences[0], mx = mn;
        for(auto &a : differences) {
            sum += a;
            mn = min(mn, sum);
            mx = max(mx, sum);
        }
        // d0: the first element
        // d_min: the min element exclude d0
        // d_max: the max element exclude d0
        // d_min - d0 = mn ---> d_min = d0 + mn
        // d_max - d0 = mx ---> d_max = d0 + mx
        // lower(L) <= di <= upper(R) for all i, so
        // (1) L <= d0 + mn <= R ---> L - mn <= d0 <= R - mn
        // (2) L <= d0 + mx <= R ---> L - mx <= d0 <= R - mx
        // (3) L <= d0 <= R
        // combine (1) - (3)
        // max(L-mn, L) <= d0 <= min(R, R - mx)
        // so question becomes: how many valid d0?
        long l = max((long)lower, lower - mn), r = min((long)upper, upper - mx);
        return r >= l ? r - l + 1 : 0;
    }
};

[Leetcode] 813. Largest Sum of Averages

813. Largest Sum of Averages

You are given an integer array nums and an integer k. You can partition the array into at most k non-empty adjacent subarrays. The score of a partition is the sum of the averages of each subarray.

Note that the partition must use every integer in nums, and that the score is not necessarily an integer.

Return the maximum score you can achieve of all the possible partitions. Answers within 10-6 of the actual answer will be accepted.

Constraints:

1 <= nums.length <= 100

1 <= nums[i] <= 10^4

1 <= k <= nums.length

Analysis:

This question asks for the an maximum value, so we usually can consider dp first.

As it is known, the key for dp is to find the transition formula. Or find the key parameters than describe an "intermediate state" completely.

The intermediate state here represents a similar question but with a smaller size.

For this question, we can try to define the state as dp[i][k], where i is the index of the elements and k is the number of subarrays.

The meaning of dp[i][k] is the maximum of average sum ending with the ith element with at most k subarrays.

Then the next step is to derive the formula to calculate the value of dp[i][k] using the previous dp with smaller values of i and k.

dp[i][k] = max(dp[x][k-1] + sum(num[x+1] to nums[i])/(i-x)), where x from 0 to i-1.

With the meaning of dp[x][k-1], the above formula is not hard to understand:

The right-hand side (rhs) enumerates all the possible ways to calculate dp[i][k], so we just need to pick up the maximum of it.

In the implementation, the boundary conditions are tricky. The thumb rule is to make sure the dp[i][k] is valid. For example, dp[i>0][0] is not valid, since there is no such case that we have non-zero elements in 0 subarray.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        // dp[i][j]: the max, ending at i, up to j subarray;
        // dp[i][j] = max(dp[d][j-1] + sum(nums[d+1], ..., nums[i])/(i-d))
        // where d from j-1 to i-1.
        double res = 0;
        int n = nums.size();
        vector<double> sums(n+1, 0);
        for(int i=0; i<n; ++i) sums[i+1] = sums[i] + nums[i];
        vector<vector<double>> dp(n+1, vector<double>(k+1, 0));
        for(int i=1; i<=n; ++i) {
            for(int j=min(i, k); j>=1; --j) {
                for(int d=max(j-1, 1); d<=i; ++d) {
                    double v = (j==1&&d>1) ? 0 : (dp[d-1][j-1] + (sums[i]-sums[d-1])/(i-d+1));
                    dp[i][j] = max(dp[i][j], v);
                }
            }
        }
        return dp[n][k];
    }
};

If do not like the boundary conditions of the above dp solution, we can try dfs + memoization.

We can start from the beginning of the array, and stop to make a subarray at any possible places.

See the code below:

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<double>> memo(n, vector<double>(k, -1));
        return dfs(nums, 0, k-1, memo);
    }
private:
    double dfs(vector<int>& ns, int id, int k, vector<vector<double>>& memo) {
        // invalid ending since we cannot have more than k subarrays
        if(k<0 && id<ns.size()) return -2;
        if(id==ns.size()) return 0;
        if(memo[id][k] != -1) return memo[id][k];
        double t = 0, sum = 0;
        for(int i=id; i<ns.size(); ++i) {
            sum += ns[i];
            double v = dfs(ns, i+1, k-1, memo);
            if(v>-2) t = max(t, sum/(i-id+1) + v);
        }
        return memo[id][k] = t;
    }
};

  

[Leetcode] 2104. Sum of Subarray Ranges

2104. Sum of Subarray Ranges

You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

Constraints:

1 <= nums.length <= 1000

-10^9 <= nums[i] <= 10^9

 

Follow-up: Could you find a solution with O(n) time complexity? 

Analysis:

First of all, we can use a two-layer for loop to solve this problem, since the maximum length is 10^3, so O(N^2) is acceptable for the online OJ.

For any array with N elements, there are N*(N+1)/2 sub-arrays. So we just need to get the min and max of each sub-array, and sum the diffs together.

See the code below:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long res = 0, n = nums.size();
        for(int i=0; i<n; ++i) {
            int mx = nums[i], mi = mx;
            for(int j=i+1; j<n; ++j) {
                mx = max(nums[j], mx);
                mi = min(nums[j], mi);
                res += (long)mx - (long)mi;
            }
        }
        return res;
    }
};

As asked in the follow up, can we do better?

(Please be noted: the following logic is quite non-intuitive, and requires at least 10 min to read.)

The answer is yes. For example, with a stack, the time complexity can be decreased to O(N).

Think about one classical question about stack: In an integer array with size of N, for each element, what is the first element larger than it?

 One observation is that: if we maintain a monotonically increasing stack, then we can derive many useful information. For example, we can derive the answers to the above question for every elements in a time complexity of O(N), or just in one scan for every element. 

At the same time, we can get the number of the elements larger than every element on its right side continuously!

For example, say we have one array [6, 9, 3, 5, 10, 1, 4, 7], and we will use a stack to scan through the array from left to right.

One trick here is to use the index instead of value (recording index is obvious better than value with an array, since once we know the index, we know the value as well; but not the reverse)

At step 1, we have [0];

            2,                [0, 1]

At step 3, the index is 2 and the value is 3, and 3 < arr[1] == 9 (which is the top of the stack), we need to pop out the top element in the stack, so we get the number of elements larger than arr[1] continuously is (2 - 1 - 1) = 1. So res[1] = 0;

We will continue the comparison between the new top of the stack and arr[2]. Now the top is 0. and arr[0] == 6 > arr[2] == 3, so we need to pop it as well. So res[0] = 2 - 0  - 1= 1.

The stack becomes empty, so we just put 2 into it.

So far, we have obtained res[0] = 1 and res[1] = 0. Are they correct? 

It is straightforward that the answer is yes. For arr[0], there is one which is arr[1]; for arr[1], there is none.

Let continue the scan.

At step 4, index = 3, we have [2, 3];

             5,             4,                [2, 3, 4];

At step 6,              5, and we need to pop out elements again, since arr[5] < top of the stack

In this way, we can get all answers for every elements in a single scan!

The take-home message here is:

With a stack, we can get the number of the elements larger than every element on its right side continuously in one single scan!

Similarly, if we change the scanning direction, we can get the number of the elements larger than every element on its left side continuously in one scan as well.

After having these two values, we can calculate the number of sub-arrays with the current element as the minimum.

If the larger elements on the right side continuously is fr[i] and on the left side continuously is fl[i], then there are (fr[i] + 1) * (fl[i] + 1) sub-arrays with arr[i] as the minimum.

One corner case is when the array have elements with the same values. For example, the array is [5, 5, 5]. In this case, we can use a tiny trick: on the right side, we can calculate the number of elements no-smaller than the current element continuously; on the left side, we just calculate the number of elements strictly larger than the current element continuously.

For the [5, 5, 5] array, the fr array is [2, 1, 0], the fl array is [0, 0, 0].

So the number of the subarray with arr[0] as the minimum is: (2+1)*(0+1) = 3;

So the number of the subarray with arr[1] as the minimum is: (1+1)*(0+1) = 2;

So the number of the subarray with arr[2] as the minimum is: (0+1)*(0+1) = 1;

Similarly, we can count the number of the subarray with arr[i] as the maximum in O(N) as well (with a monotonically decreasing stack).

Once we figure out the frequency of the maximum elements and minimum elements, we can calculate the difference of all of them. (The order does not matter. Or we do not need to figure out the maximum and minimum of each subarray).

See the code below:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long res = 0;
        int n = nums.size();
        stack<int> sk1;
        vector<int> dp1(n, 0), dp2(n, 0), dp3(n, 0), dp4(n, 0);
        for(int i=0; i<n; ++i) {
            while(sk1.size() && nums[sk1.top()] > nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp1[id] = i - id;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp1[id] = n - id;
        }
        for(int i=n-1; i>=0; --i) {
            while(sk1.size() && nums[sk1.top()] >= nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp2[id] = id - i;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp2[id] = id + 1;
        }
        for(int i=0; i<n; ++i) {
            while(sk1.size() && nums[sk1.top()] < nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp3[id] = i - id;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp3[id] = n - id;
        }
        for(int i=n-1; i>=0; --i) {
            while(sk1.size() && nums[sk1.top()] <= nums[i]) {
                int id = sk1.top();
                sk1.pop();
                dp4[id] = id - i;
            }
            sk1.push(i);
        }
        while(sk1.size()) {
            int id = sk1.top();
            sk1.pop();
            dp4[id] = id + 1;
        }
        for(int i=0; i<n; ++i) {
            // cout<<dp1[i]<<" "<<dp2[i]<<" "<<dp3[i]<<" "<<dp4[i]<<endl;
            res += (long)nums[i] * ((dp3[i]) * (dp4[i]) - (dp1[i]) * (dp2[i]));
        }
        return res;
    }
};

We can make the code much more concise. 

With a monotonically non-decreasing stack, when we pop out one element, we can calculate the number of (strictly) larger elements on the left side continuously as well. To get this, we just need to compare the index popped out with the current top of the stack, or left boundary if stack if empty. (Why?)

See the code below:

class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        long long res = 0, n = nums.size();
        stack<int> sk;
        for(int i=0; i<=n; ++i) {
            while(sk.size() && (i==n || nums[sk.top()] > nums[i])) {
                int id = sk.top();
                sk.pop();
                int fr = i - id;
                int fl = sk.empty() ? id + 1 : id - sk.top();
                res -= (long long)nums[id]*fr*fl;
            }
            if(i<n) sk.push(i);
        }
        for(int i=0; i<=n; ++i) {
            while(sk.size() && (i==n || nums[sk.top()] < nums[i])) {
                int id = sk.top();
                sk.pop();
                int fr = i - id;
                int fl = sk.empty() ? id + 1 : id - sk.top();
                res += (long long)nums[id]*fr*fl;
            }
            if(i<n) sk.push(i);
        }
        return res;
    }
};