[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] 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;
    }
};

Leetcode 907: Sum of Subarray Minimums

https://leetcode.com/problems/sum-of-subarray-minimums/description/

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

1. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

Notes:

Since the size of the array is very large, the naive O(N^2) method cannot pass the OJ.

The optimal solution can be O(N), by using a stack.

One of keys to this question is to find the minimum element and also its range.

Let say there is one local minimum arr[i], and the smaller first element on the left side is at index j, and the first smaller element on the right side is at index k. Then there are (i - j) * (k - i) subarrays with arr[i] as the minimum. So the contribution to the final results is arr[i]*(i-j)*(k-j).

And we need to do this for every element. A stack can be used to find j and k for each arr[i] by one pass.

The key is to maintain a monotonically increasing stack.

Since we need to figure out the distance, the stack will store index instead of values.

When meet with a smaller element (< stack.top()), the first smaller element on the right side of the arr[stack.top()] element can be found directly;

After popping out all the larger ones, the remaining are smaller or equal ones. So the current stack.top() is the left boundary of arr[i]. (The equal situation can also be included correctly.)

In order to easy code, element 0 has been placed before and after the array. In this way, all the elements in the original array can be popped out at the end of the code.

See the code below:

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = 0, mod = 1e9+7;
        A.insert(A.begin(), 0);
        A.push_back(0);
        vector<int> L_idx(A.size(), -1), R_idx(A.size(), -1);
        stack<int> sk;
        for(int i=0; i<A.size(); ++i) {
            while(sk.size() && A[sk.top()] > A[i]) {
                int t = sk.top();
                sk.pop();
                R_idx[t] = i;
                long dis1 = t - L_idx[t], dis2 = R_idx[t] - t, val = A[t];
                res = (res + (dis1 * dis2 * val) % mod) % mod;
            }
            if(sk.size()) L_idx[i] = sk.top();
            sk.push(i);
        }
        A.erase(A.begin());
        A.pop_back();
        return res;
    }
};