1713. Minimum operations to make a subsequence

link

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.
In one operation, you can insert any integer at any position in arr. For example, if arr = [1,4,1,2], you can add 3 in the middle and make it [1,4,3,1,2]. Note that you can insert the integer at the very beginning or end of the array.
Return the minimum number of operations needed to make target a subsequence of arr.
A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.

1. Attempt 1

Notice numbers in arr does not matter unless it is contained in target. Example

target = [5,1,3], arr = [9,4,2,3,4]

can be simplified to

target = [5,1,3], arr = [3]

So this is an edit distance question with only insertion enabled. See the next subsection for a review of editing distance.

Follow the editing distance way of thinking, define state = dp[i,j] as operations to make target[0,i] be a sub-sequence of arr[0,j]

When target[i] == target[j]: dp[i,j] = dp[i-1,j-1]

When target[i] == target[j]:

1. Option 1: do insertion:

   target = [5,7,3], i = 2
   arr = [1,5,7], j = 2
   

   insert 3 to arr. This means dp[i,j] = dp[i-1,j]+1
2. Option 2: do nothing:

   target = [1,5,7], i = 2
   arr = [5,7,3], j = 2;
   

Ignore the 3 at arr[j]. This means dp[i,j] = dp[i, j-1]

Thus

dp[i,j] = 
    dp[i-1,j-1]                      when target[i] == target[j]; OR
    Math.min(dp[i,j-1], dp[i-1,j]+1) when target[i] != target[j].

Complexity O(mn), O(min(m, n)). TLE.

class Solution {
    private static record State(int i, int j){};
    public int minOperations(int[] target, int[] arr) {
        return helper(target.length-1, arr.length-1, 
                      new HashMap<>(), target, arr);
    }

    private int helper(int i, int j, 
                       Map<State, Integer> mem, 
                       int[] target, int[] arr) {
        if(i == -1) return 0;
        if(j == -1) return i+1;
        if(mem.containsKey(state)) return mem.get(new State(i,j));
        int res = 0;
        if(target[i] == arr[j]) res = helper(i-1, j-1, mem, target, arr);
        else res = Math.min(helper(i-1, j, mem, target, arr) + 1, 
                            helper(i, j-1, mem, target, arr));
        mem.put(new State(i,j), res);
        return res;
    }
}

1.1 Editing distance:

Try to make str1 same as str2. Define state
dp[i,j] as the editing distance between str1.substring[0,i] and str2.substring[0,j]:

When str1[i] == str2[j]:

dp[i,j] = dp[i-1,j-1] + 1. simple enough.

When str1[i] != str2[j]:

Example:

1. Option 1: replace:

   str1 = "abc", i = 2
   str2 = "abd", j = 2
   

   replace c with d, then dp[i,j] = dp[i-1,j-1] + 1
2. Option 2: delete

   str1 = "abc", i = 2
   str2 = "aab", j = 2
   

   delete c. then dp[i,j] = dp[i-1, j] + 1
3. Option 3: insertion

   str1 = "caa", i = 2
   str2 = "aab", j = 2
   

   insert a b at the end of str1. so dp[i,j] = dp[i, j-1] + 1
   Thus
   dp[i,j] = min(dp[i-1,j-1], dp[i,j-1], dp[i-1,j]) + 1

2. Attempt 2

Hint 1: The problem can be reduced to computing Longest Common Subsequence between both arrays.

Minimum insertions = target.length() - longest common subsequence(target, arr)
So it simplified to LCS. LCS state transfer equation:

dp[i, j] = 
  dp[i-1, j-1] + 1, if target[i] == arr[j]; OR
  Math.max(dp[i-1, j], dp[i, j-1]), if target[i] != arr[j]

same complexity. still TLE.

3. Attempt 3

question says:

You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.

Thus hint 2

Since one of the arrays has distinct elements, we can consider that these elements describe an arrangement of numbers, and we can replace each element in the other array with the index it appeared at in the first array.
Then the problem is converted to finding Longest Increasing Subsequence in the second array, which can be done in O(n log n).

LIS. LIS of an array.
A simple O(n^2) solution

dp[i] = Math.max(dp[k]) + 1, where arr[k] < arr[i] and k < i. 
edge: if no such k. then set dp[i] = 0

3.1 LIS using sequence building method: O(n^2)

See approach 2.

Given [5,7,9,8,2,3,4,8,1] LIS can be built as

1. Get 5, put it in result sequence [5]
2. Get 7, larger than result sequence largest. Update result to [5,7]
3. Get 9, update to [5,7,9]
4. Get 8, smaller than result sequence largest, but if update 9 to 8 opens up some possibilities. Thus update result to [5,7,8]
5. Get 2, better than 5, so update result to [2,7,8]
6. Get 3, replace 7 with 3, result [2,3,8]
7. Get 4, replace 8 with 4, result [2,3,4]
8. Get 8, append to end. result [2,3,4,8]
9. Get 1, replace 2 with 1. result [1,3,4,8]

This way we find the LIS has to be length 4.

Note This method does not guarantee the result sequence is a valid sequence. Only length is correct. The result [1,3,4,8] is not a valid sequence.

This method is basically saying we build a monotonically increasing result array. Each incoming element, find the first one that is equal or larger than self, replace self with that element.

3.2 Optimized LIS using sequence building and binary search: O(nlogn)

Method 3.1 has that monotonically increasing sequence. So finding the first one that is equal or larger can be done via binary search. Algorithm can be further simplified to O(nlogn).

Now going back to the original 1713 question, this question can thus be solved in O(nlogn).

Dungeon game

Leetcode link.

I tried three methods:
First, this really looks like max path sum problem. But soon I realized the short coming of using max path sum, that is, max path sum cannot guarantee that hero's health is always positive (In the following analysis, I assume the health can reach 0. To get the correct output I only need to increment my result by 1).
The sub-problem of max path sum problem is "max value one can at location matrix[i][j]  starting from matrix[0][0]", a similar sub-problem is constructed for this problem, that is:

minimum starting health required to get to location matrix[i][j].

This sub problem requires one to record cumulative health along the way, for example, if the path is -2 -3 3 1 -5, then the minimum starting health sequence is 2 5 5 5 6. To generate this sequence, one need to record cumulative health.
But this method fails too when I encounter this test case:

1     -3     3

0     -2     0

-3    -3     -3

The minimum starting health required to get to matrix[1][2] is 2, and minimum starting health required to get to matrix[2][1] is 5. Thus by my sub problem analysis, one would pick path

1, down, 0, right -2, right, 0, down, -3.

But this path needs a minimum starting health of 4, while path

1, right -3, right, 3, down, 0, down, -3

only needs 2 starting health.
Now we have a problem, sub-problem matrix[2][2] does not come from sub-problem matrix[1][2] or sub-problem matrix[2][1]. This DP structure is not applicable anymore.

I am really frustrated until this problem is reviewed again: problem statement:

minimum initial health to get to the right-down-most cell.

My second method constructs sub-problem from the "fixed-starting-point" POV, if one use "fixed-ending-point" POV, one can construct sub-problem:

minimum health starting from current location to get to the right-down-most cell.

If method 2 (wrong method) is used, one needs two memoization matrices. Further thinking reveals one memoization matrix is enough is method 3 is used. And code length is minimized.

int calculateMinimumHP(vector<vector<int> > &dungeon) {
    if (!dungeon.size() || !dungeon[0].size()) return 1;
    int rowcount(dungeon.size()), colcount(dungeon[0].size());

    vector<int> mi(colcount, 0);
    mi[colcount - 1] = max(0, -dungeon[rowcount - 1][colcount - 1]);
    for (int row = rowcount - 1; row >= 0; --row) {
        for (int col = colcount - 1; col >= 0; --col) {
            if (row == rowcount - 1 && col == colcount - 1) continue;
            int candright(INT_MAX), canddown(INT_MAX);
            if (col != colcount - 1) candright = max(0, -dungeon[row][col] + mi[col + 1]);
            if (row != rowcount - 1) canddown = max(0, -dungeon[row][col] + mi[col]);
            mi[col] = min(candright, canddown);
        }
    }
    return mi[0] + 1;
}

Now it's time to think why method 3 works but not method 2? Leetcode says local minimum cannot guarantee global minimum, but that is just a result, not a formal proof.

Convert sorted list to binary search tree

Leetcode link.

The way I handle this question is I first count how many nodes there are in the list, and construct an empty binary search tree, then use morris traversal/recursive inorder traversal to fill the whole tree with list value. Time complexity is O(n) with space complexity O(n).

But geekforgeek provided another brilliant solution. I am still pondering on why this works, and my bet is on the similarity between dfs and inorder traversal. But here is the code and some comments:

TreeNode* helper(ListNode* &head, int low, int high) {
    if(low == high) {
        TreeNode* ret = new TreeNode(head->val);
        head = head->next;
        return ret;
    }
    else if(low > high) return NULL;
    int mid = low + ((high-low)>>1);
    TreeNode* left = helper(head, low, mid-1);
    TreeNode* ret = new TreeNode(head->val);
    ret->left = left;
    head = head->next;
    ret->right = helper(head, mid+1, high);
    return ret;
}

TreeNode *sortedListToBST(ListNode *head) {
    if(!head) return NULL;
    ListNode* walker = head;
    int count = 0;
    while(walker) {
        ++count;
        walker = walker->next;
    }
    return helper(head, 0, count-1);
} 

That low and high index is quite confusing, they actually only represents how many nodes there are in this section. For each valid loop (\( low <= high \)) we need to make sure the list pointer moves to the next section once the root node for this section is handled, such that when we reaches line 13 list pointer is at the start of this section.
Anyway, this is the first time I see code that build a tree from leaf nodes. Very brilliant idea.

PS: geekforgeeks' code is actually even better than mine since the case when \(low == high\) is integrated in the ensuing code.

Divide Two Integers

Medium difficulty question with all kinds of corner cases, which bump the difficulty to hard.
Leetcode link.

Q: Divide two integers without using multiplication, division and mod operator.

A:
I managed to crack it by myself the first time I fought through leetcode, but not this time. I had to go back and check what I had done. :( shame

The idea is simple. Shifting operation is your friend. Test case \( \frac{700}{51} \): \[ 700 = 2^3 \cdot 51 + 292 \\ 292 = 2^2 \cdot 51 + 88 \\ 88 = 2^0 \cdot 51 + 37 \] We stop at 37 because \( 37 < 51 \).
All right that's it. Answer is \( 2^3+2^2+2^0 = 13 \).

Corner cases' time!

1. Dividend / Divisor == 0?
2. Dividient or Divisor is negative? or both are negative?
3. This is about integer, so what do you consider? Overflow! \(Dividend/divisor == INT\_MIN/INT\_MAX\) or \(-INT\_MIN/-INT\_MAX ?\)

First one is easy to handle. Notice when divisor is 0, throwing an exception is what you should do. But OJ says you can simply return 0. All right then.
Second one is tricky to handle. Judge the sign! Then use \( abs \) function to do it! Yeah, you'll see there is one loose end soon...
Third one? I cheated... I used long long type to handle everything. If I don't, the loose end in second question will reveal: The devil \( abs(INT\_MIN) \) !  ideone says \( abs(INT\_MIN) == INT\_MIN \), someone on leetcode forum reports \( abs(-2147483647) = -2147483644 \) or something like that. Anyway, I cheated...

My code is as follow. Not the best code though. Feel free to play it here.

pair<long long, long long> decompose(long long a, long long b) {        // DONT MAKE a < b
    int k = 0;                                  // decompose a/b = 2^k + d, d < 2^k
    while (b < a) {
        b <<= 1;
        k++;
    }
    if (b == a) return make_pair(k, 0);
    return make_pair(--k, a - (b>>1));
}

int divide(int dvd, int dvs) {
    if (dvs == 0) throw overflow_error("Divide by zero exception");
    if (dvd == 0) return 0;

    long long ldvd, ldvs;
    ldvd = abs((long long)dvd); ldvs = abs((long long)dvs);
    if (ldvd < ldvs) return 0;

    long long ret = 0;
    pair<long long, long long> kb;
    do{
        kb = decompose(ldvd, ldvs);
        ret += 1 << kb.first;
        ldvd = kb.second;
    } while (kb.second >= ldvs);
    return ((dvd>>31) == (dvs>>31)) ? ret : (~ret + 1);
}

Container with most water

Leetcode link:
Q:
Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container. 


A:
Given line i and line j, one can easily come up with: \[ Area[i][j] = min(height[i], height[j]) * (j-i) \]
So an \( O(n^2) \) solution is fairly easy to get.


To decrease the time complexity, tricks and pruning are all what you need. Suppose we found an solution from i to j \( (i<j) \), and we assume \( height[i] < height[j] \). Then \( height[i] \) is dominant, which means if we decrease j, there will be no area larger than \( Area[i][j] \). This should be very easy to verify.


With this pruning, in order to investigate all possible i and j combinations, we start with \( i = 0 \) and \( j = height.size()-1 \) and shrink i and j inward, resulting the following simple code:

int maxArea(vector<int> &height) {
    if(height.size() <= 1) return 0;
    // idea of this program: If found one candidate [A[i], A[j]], 
    // if A[i] < A[j] then A[i] is dominate. all [A[i], A[j-k]] (k>0) 
    // will not generate area larger than [A[i], A[j]]. The only 
    // candidates can be achieved by moving j.
    int low, high;
    low = 0;
    high = height.size()-1;
    int maxarea = min(height[high], height[low]) * (high-low);
    while(low != high) {
        maxarea = max(maxarea, min(height[high], height[low]) * (high-low));
        if(height[low] < height[high]) low++;
        else high--;
    }
    return maxarea;
}

[Learning note]: Consistent hashing

This is a fun note. Original link here(Chinese), and here, here, here. (Update: it seems Amazon also use this stuff.)

So in the last post, I scratched the surface of amortized analysis. Amortize analysis shows that insertion in dynamic array is O(1) time complexity and so does insertion and deletion in hash map. But average analysis will have trouble in real world implementation. Consider the case below:

Problem statement

Map one object to \(N\) cache server can be done by a simple hash function \(hashkey(object)%N\). For uniformly distributed hashkey this algorithm is good.

Suppose we have 10 servers labeled as server 0 to server 9. Objects have hash key 11, 12 and 13. Then they will be mapped to server 1, server 2 and server 3.

What if:

1. One server (server 9) is down. Now the hash function changes to \(hashkey(object)%(N-1)\).
   
   In this case, objects have to be moved to server 2, server 3 and server 4. All objects have to be moved.
2. New server added. Now the hash function changes to \(hashkey(object)%(N+1)\).
   
   In this case, objects have to be moved to server 0, server 1 and server 2.

For large cache servers the cost of the above two cases are not tolerable. Consistent hashing is designed to minimize the compact of cache serve changes by minimizing key moves when new server is introduced or old server is removed from the system. Using our previous dynamic array example, when resizing or shrinking happens, consistent hashing is designed to minimize the resulting compact by reusing as many old keys as possible. As other posts, this post will mainly focus on the application side. More details can be found in this paper.

Algorithm Design

So as stated in Wikipedia and the reference link, circular hash space is used to represent a common modulo-based hash function. I will not redraw all the graphs this time, all figures credit to sparkliang.

If unsigned 32-bit integer value is used as hash key, then the whole hash space can be referred to as a circular space based on modulo property. We represent it as the left figure below.

Given 4 objects with 4 different keys, the figure above shows their placement in the hash space. Up until here we are still using the classical hash design method.

The innovative part of consistent hashing is, not only put object into hash space, cache server is also placed into the hash space. Suppose we have 3 servers. Using certain function, we map them two three different hash key Key A, Key B and Key C. Now place them to hash space:

Now we have object keys and server keys all in the hash space. The next question comes naturally: how to map objects to servers? You might have guessed it right already:

for each object we search clockwise (or counter-clockwise as long as you keep the direction consistent in your program design) and group it to the first cache server we find.

That's it. After grouping, the above figure is now:

Why is this consistent hashing method superior to the naive hashing method?

Let's revisit the two questions raised above and first discuss what happens when one server is down:

Suppose server B is down. Now based on the algorithm above, we have:

It is easy to see that only the segment between cache A and cache B needs to be processed. Comparing with the naive hashing method, removing a cache server causes relatively smaller impact.

Adding a cache server is similar. Suppose a new cache server Cache D is added with Key D, we now have:

It is easy to see that only the segment between cache A and cache B needs to be processed, which brings better performance than naive hashing method.

Virtual cache server in hash space

Consider the following case (derived from cache deletion case):

In this case three objects are grouped to cache C while only one object is grouped to cache A. This balancing issue usually happens when we do not have too many cache server. To avoid this balancing issue, virtual servers are added to the hashing space such that we can mimic the behavior or many servers even though we have only a few servers.

The implementation is quite clever. For each server we make several replica. For example, for the case above, we make one shadow copy for each server and put the shadow copy back to the hashing space. Now we have:

And we can see the hashing space is balanced.

A simple simulation program has been written to verify that if different servers have different weight, for example a new server can take more work than an old server, replica number can be directly related to server weight. In the case of hash table resizing this technique is also applicable. Test link here.

[Learning note] Amortized analysis case: Dynamic array insertion complexity

Amortized analysis is sometimes used in algorithm analysis when average time complexity is more concerned than individual operations. I stumble upon this today when I am reviewing hash map implementation and find it fun.

Case 1: Dynamic array insertion

Consider a dynamic array of size N. When insertion is performed, if the dynamic array still has vacant locations, insertion will take O(1) time. But if the dynamic array is full (all almost full depends on the implementation), we will reallocate an array of size 2N and move original elements to this new array along with the newly added element. This single operation will cost about O(2N) time. (2N time to allocate the new array, at least constant time to delete the original array, N time to move the element, constant time to add the newly inserted element). So we will have a timeline similar to:

When amortized, resizing cost is distributed to all N insertions, leaving an average complexity of nearly O(1).

Case 2: Hash table resizing

With dynamic array insertion in mind, hash table resizing is quite similar. Consider a size N hashmap containing M elements. Its load factor is \( \frac{N}{M} \). The resizing scheme is as follow: If the load balance exceeds 1, we will double hash table size. If load balance is less than \( \frac{1}{4} \), hash table size is halve.

Use the same analyzing scheme, the amortized cost for insertion is calculated as: (Figure redrawn from here.)

When amortized, the average cost is still O(1).

As to shrinking hash table, we start with \( N = \frac{M}{2} \) since this is what remains after one last shrinking operation. We need to perform at least \( \frac{M}{4} \) deletion operations before another shrinking is needed. This shrinking will have time cost of O( \( \frac{M}{2}\) ). Distribute this time to all \( \frac{M}{4} \) deletion operations. The amortized time complexity is still O(1).