Leetcode Summary

• Time \(O(\log(\min(m, n)))\)
• Space \(O(1)\)

A very genius algorithm is detailed in this post Very concise O(log(min(M,N))) iterative solution with detailed explanation. We could generalize that algorithm to find the \(k\)th element of two sorted arrays in \(O(\log(\min(m,n,k)))\) time.

Let's assume \(k\) is 0-based.

• For one sorted array A of length \(n\), the \(k\)th element is A[k], which divides the original array into two parts: A[0..k-1] and A[k..n-1], i.e., there are exactly \(k\) element on the left of \(k\)th element no greater than A[k].

• For two sorted array A of length \(n\), B of length \(m\), and \(n \geq m\), if we could find positions p, q in A and B respectively such that

  1. p \(+\) q \(= k\)
  2. A[p-1] \(\leq\) A[p] and A[p-1] \(\leq\) B[p]
  3. B[p-1] \(\leq\) B[p] and B[p-1] \(\leq\) A[p]

  Then we say z = min(A[p], B[p]) will be the \(k\)th element since there are \(k\) element no greater than z. Note that this formulation applies to arrays with duplicates.

  Since p and q can be determined from each other, we could do a binary search in the shorter array B. The C++ code is available gongzhitaao/oj.

\(k\) is the length of longest common prefix.

• Time \(O(nk)\)
• Space \(O(1)\)

• Time \(O(n^2)\)
• Space \(O(1)\)

Sort the array first, then use two loops:

• outer one i ranges [0, n-3)
• inner one j starts from i, k starts from the end,
  • if sum is greater than expected, move k left,
  • if sum is less than expected, move j right,
  • otherwise move j right and k left
  • until they meet

• Time \(O(\log n)\)
• Space \(O(1)\)

See the C++ std implementation of upper_bound or lower_bound.

• Time Uncertain
• Space Uncertain

Not sure about the complexity of the problem. It is rather intricate to determine in general. The idea is simple, i.e., brutal force with DFS, trying every possible combination. Note that the problem states that the provides candidates is a set, so you do not have to worry about duplicates.

• Time \(O(n)\)
• Space \(O(1)\)

• Time \(O(n)\)
• Space \(O(1)\)

• Time \(O(n^2)\)
• Space \(O(1)\)

• Time \(O(n)\)
• Space \(O(1)\)

Same as Leetcode 106.

Time \(O(n^2)\) space \(O(1)\) or Time \(O(n)\) space \(O(n)\)

• The last one in post-order traverse is the parent.
• Find the position of the parent in the in-order traverse.
• Recursively construct the left and right children.

If we store in a hash map all the values' position in the in-order traverse, it runs in \(O(n)\) at the expense of \(O(n)\) space, otherwise it runs in \(O(n^2)\).

• Time \(O(E+V)\)
• Space \(O(V)\)

BFS is more space expansive up to a constant factor.

• Time \(O(mn)\) where m is length of s, n length of t.
• Space \(O(mn)\)

Naive divide-and-conquer search fails due to time limit. This could be solved with DP.

Suppose \(d[i][j]\) holds the number of solution for t[0..i-1] and s[0..j-1], then d[n][m] is the final solution.

State transition: \[d[i][j] = \begin{cases} d[i][j-1] + d[i-1][j-1], & \text{if}\ \text{T}[i-1] = \text{S}[j-1] \\ 1, & \text{otherwise} \end{cases}\]

• Time \(O(E+V)\)
• Space \(O(1)\)

Two loops:

• i iterates "row"
• j iterates each level and connects each node's children.

• Time \(O(E+V)\)
• Space \(O(1)\)

Similar to Leetcode 116, but in addition, we need to keep track of each level's starting node.

• Time \(O(n^2)\)
• Space \(O(n)\)

Dynamic programming. The sum holds current sum, then the state transition for sum[i] is sum[i] = min(sum[i-1], sum[i]) + triangle[i]. Be careful to

1. backup sum[i-1].
2. initialize sum to be all maximum integer value except for the first one, which is initialized to 0.

• Time \(O(n)\)
• Space \(O(1)\)

Use slow and fast pointer.

• Time \(O(n)\)
• Space \(O(1)\)

Just iterate through the array. Watch out for edge cases, like empty array, boundary values.

• Time uncertain
• Space uncertain

Just perform long division. As for repeating fraction detection, if we come across the same remainder, then we have a repeating fraction from where remainder occurs first.

Edge cases: negative case, no negative sign when numerator is 0, no decimal point when no fraction part.

• Time \(O(E+V)\)
• Space \(O(V)\)

Search the tree following BFS or DFS.

• BFS, record the last element at every level.
• DFS, right-to-left in-order traverse, record the element whenever level increases.

• Time \(O(mn)\)
• Space \(O(mn)\)

Similar to Leetcode 305, we can use disjoint-set. Or we could do a BFS on each land position.

• Time \(O(n\log n)\)
• Space \(O(n)\)

Naive solution is to create skyline for each building and merge them one by one, which runs in \(O(n^2)\) when all buildings are disjoint.

Improved version is to use merge-sort idea, split the problem into two half problem and merge the solutions. How to merge sub-skylines? Similar to merge-sort, start from the first elements of two skylines, compare the X coordinates, pick the smaller one, height is maximum of current heights from both skylines. If the new height is the same as old one, do not insert it as it will result in a consecutive horizontal lines of equal height.

• Time \(O(n^2)\)
• Space \(O(1)\)

Similar to Leetcode 015, we keep two pointer lo and hi in the inner loop. The critical observation is if nums[i] + nums[lo] + nums[hi] < target, then any hi in the range (lo, hi] satisfies the condition.

• Time \(O(n)\)
• Space \(O(1)\)

Let's suppose we are at position k, array A[0..k] are wiggle-sorted already.

Case 1 k is odd

If A[k+1] <= A[K], no change needed. If A[k+1] > A[k], after swapping A[k+1] with A[k], we have A[k-1] <= A[k] > A[k+1]. So A[0..k+1] is wiggle-sorted.

Case 2 k is even

Argument similar to the above.

So just sweep through the array, swap any two element that does not satisfy the wiggle condition.

• Time \(O(mn)\)
• Space \(O(mn)\)

Start from each gate, do a BFS or DFS to update the distance for each room.

• Time initialization \(O(n)\), query \(O(1)\)
• Space \(O(n)\)

The question is straightforward, however, beware of the definition of "being unique", i.e., either the word itself does not exist in the dictionary or its key does not exist if it is in the dictionary.

• Time \(O(k\log mn)\) actually this is the query time, not including the initialization time, which is \(O(mn)\).
• Space \(O(mn)\)

Simple application of disjoint-set. For each new land, first we make itself a set, then union with its neighbors, if any.

The initial count is 0, for each new land, first we make a set of its own, increment the count. Then whenever we successfully union it with one of its neighbors, decrement the count.

• Time \(O(\log n)\) for update and sum
• Space \(O(n^2)\)

2D binary index tree (Fenwick tree).

• Time \(O(n^2)\)
• Space \(O(n)\)

Adpated from @GWTW solution. For day k, there are four states.

1. Have stock, do nothing
2. Have stock, sell the stock
3. Have no stock, do nothing
4. Have no stock, buy the stock

Let a[k], b[k], c[k], d[k] denote the maximum profit on day k ending in each of the four states respectively, P[k] the stock price on day k. The final solution is max(b[n], c[n]).

State transition:

1. a[k + 1] = max(a[k], d[k])
2. b[k + 1] = max(a[k], d[k]) + P[k + 1] - P[k]
3. c[k + 1] = max(b[k], c[k])
4. d[k + 1] = max(c - P[k + 1])

Iterate from day 0 and initial values are all zeros.

• Time \(O(n^3)\)
• Space \(O(n^2)\)

If we divide the problem by first explosion position, the subproblems are not independent. However if we divide the problem by last explosion position, then the subproblems are independent. Let v[i][j] denote the max coin required in range (i,j) where i and j are off-bound. The state transition function is

\[v[i][j] = \max_k(v[i][j], v[i][k]+v[k][j]+nums[i]\times nums[k]\times nums[j])\]

where, \(i < k < j\).

Similar to Floyd-Warshall algorithms we need three nested loops to update the value matrix v and v[0][n+1] is the final result.

And as a side note, based on the state transition function, we could see that v[i][j] depends on values below and left.

Let's forget about the binary index tree for now. The basic idea is simple.

1. We maintain a counter array count[] which stores the count of each element.
2. Sort a copy of the original array to Get each element's position after being sorted, stored in a hash map h[].
3. Then traverse the original list in reverse order.
   1. For each element e, we increment by 1 its counter count[h[e]].
   2. Sum all the numbers in the range count[0...h[e]-1] gives the number of smaller elements after e.

Now this is a classic binary indexed tree problem, update and query. In the actual implementation, we may not need the counter array at all. We only need the binary indexed array.

This is problem looks similar to Leetcode 280. However the algorithm is drastically different.

• Leetcode 280, nums[0] <= nums[1] >= nums[2] <= nums[3]....
• Leetcode 324, nums[0] < nums[1] > nums[2] < nums[3]...

In other words, for Leetcode 280, there are always solutions, while it's not true for this problem. For example, [2,2,2,4,3] and [2,3,2,4,3]. Both satisfy the wiggle sort condition, but only the latter satisfy the wiggle sort II condition.

Assume the problem is always solvable, we need to find the median of the array, and whatever smaller than the median goes to even positions and the rest goes to odd positions.

• Time uncertain, it seems between \(O(n)\) and \(O(n^2)\).
• Space \(O(n)\)

Iterate through the array A with two pointers, i and j. And hashmap[j] contains the count of each character that appears in the longest substring ending at j.

1. If A[j+1] is in the hash map, increment the corresponding count.
2. If A[j+1] is not in the hash map, insert it into the hash map with count 1, and if the total size of the hash map is larger than k, then increment i until the size of hash map is no larger than k.

• Time \(O(\log n)\)
• Space \(O(1)\)

The input limits to 32-bit integer, therefore,

• the running time is actually constant.
• be careful about overflow.

First sort the array in ascending order. Let v[i] denote the largest divisible subset ending with nums[i], the state transition function is

\[v[i] = \max_{v[i].length} \left\{v[i]\bigcup v[j] \,\middle|\, \forall\, nums[i] \equiv 0 \bmod{nums[j]}\right\}\]

• Time \(O(n)\)
• Space \(O(n)\)

The string is actually the output of DFS traversal of the directory tree. The \n delimits the end of an item (directory/file) name, while \t gives the current level of the item. Just simulate the DFS traversal, store the current path length (not counting the directory delimiter /) at each node. When ever we reach a file, i.e., a leaf node, update the current max length.

Time and space are uncertain.

Expand the string in a DFS fashion, i.e., expand the inner most repeater first.

• Time \(O(n^2)\)
• Space \(O(n)\)

Wherever we insert a shorter person has no influence on taller people. Therefor, sort the people by height in non-ascending order, breaking ties by k-value in ascending order. And we will have a independent subproblem. Suppose we have already have the first k persons in a proper order, for the k+1 person with n people in front of him, just insert it in position n.

• Time \(O(31n) = O(n)\)
• Space \(O(n)\)

The XOR has a property: if \(c = a\oplus b\), then \(b = c\oplus a\). This is widely used in swapping two numbers, i.e., \(x = x \oplus y, y = x \oplus y, x = x \oplus y\).

We construct the solution, \(s\), from most significant bit to the least, bit by bit. Let \(a_k = a \gg (31 - k)\) denote the \(k\) (0-based) most significant bits for the number \(a\). Suppose we have already determined \(s_k\), now we want to determine the \(s_{k+1}\).

• First \(s_{k+1} = s_{k} \ll 1\), i.e., appending 0 to the solution, and change it to 1 if we can using the following steps.
• For each element \(a\) in the array, store \(a_{k+1}\) in a hash table.
• For each element \(a\) in the hash table, if \(s_{k+1}\oplus 1\oplus a\) is also in the hash table, then we could set the current bit to 1, i.e., \(s_{k+1} = s_{k+1}\oplus 1\).