Recently I am motivated to solve some algorithmic problems. I will be picking five challenges from LeetCode everyday, including three medium and two hard challenges. I expect that I will be spending two hours per day on solving those challenges.

There are some objectives that I want to achieve:

• To think algorithmically again
• To not rely on the test cases for debugging, nor the hints
• To write more self-explanatory code
• To learn (or re-learn) more algorithms
• To prove my approach is valid if it seems unsound

Additionally, I'll write blogposts on the problems I dealt. I'll keep them casual.

The problems today are Minimum Height Trees1, Beautiful Array2, Wiggle Sort II3, Checking Existence of Edge Length Limited Paths4 and Sliding Puzzle5.

gantt dateFormat YYYY-MM-DD HH:mm axisFormat %H:%M section Problem A A :2021-06-16 22:13, 24m section Problem B B :2021-06-16 22:38, 20m B :2021-06-16 23:45, 4m section Problem C C :2021-06-16 22:58, 24m C :2021-06-16 23:49, 12m section Problem D D :2021-06-16 23:22, 7m D :2021-06-17 00:03, 45m section Problem E E :2021-06-16 23:29, 14m

## A. Minimum Height Trees⌗

### Commentary⌗

For simplicity, I assume that $d$ is even in this section. Of course we need to handle the case when $d$ is odd...

Claim. Traverse the tree twice to obtain the longest path of length $d$. The nodes with distance $d/2$ (from one-end of the longest path) form a minimum height tree (MHT).

Unfortunately, the above claim does not work (received one WA from that). Let's take a look of the below example:

graph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;circle&#34;] rankdir=LR 0 -- 1 1 -- 2 2 -- 3 3 -- 4 1 -- 5 }

In the above case, the length of the longest path is 4. Suppose that node 0 is the reference node. The solution would be 2 and 5 because $\text{dist}(0, 2) = \text{dist}(0, 5) = 2$. However, node 5 is not a root node of the MHTs. From below, we can see that when node 2 is the root node, the height is 2. This is not the case when node 5 is the root node:

graph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;circle&#34;] &#34;0a&#34;[label=&#34;0&#34;] &#34;1a&#34;[label=&#34;1&#34;] &#34;2a&#34;[label=&#34;2&#34;] &#34;3a&#34;[label=&#34;3&#34;] &#34;4a&#34;[label=&#34;4&#34;] &#34;5a&#34;[label=&#34;5&#34;] &#34;0b&#34;[label=&#34;0&#34;] &#34;1b&#34;[label=&#34;1&#34;] &#34;2b&#34;[label=&#34;2&#34;] &#34;3b&#34;[label=&#34;3&#34;] &#34;4b&#34;[label=&#34;4&#34;] &#34;5b&#34;[label=&#34;5&#34;] subgraph cluster1 { style=&#34;filled&#34; color=&#34;#55555c&#34; label=&#34;Tree with root node = 2&#34; labelloc=t &#34;2a&#34; -- &#34;1a&#34; &#34;2a&#34; -- &#34;3a&#34; &#34;1a&#34; -- &#34;0a&#34; &#34;3a&#34; -- &#34;4a&#34; &#34;1a&#34; -- &#34;5a&#34; } subgraph cluster2 { style=&#34;filled&#34; color=&#34;#55555c&#34; label=&#34;Tree with root node = 5&#34; labelloc=t &#34;5b&#34; -- &#34;1b&#34; &#34;1b&#34; -- &#34;0b&#34; &#34;1b&#34; -- &#34;2b&#34; &#34;2b&#34; -- &#34;3b&#34; &#34;3b&#34; -- &#34;4b&#34; } }
Claim 2. Suppose that nodes $u$ and $v$ forms a longest path with length $d$. Then all nodes $w$ such that $\text{dist}(u, w) = \text{dist}(v, w) = d/2$ are the root nodes for MHTs.

I should be checking both ends of the longest path. For the tree above, a longest path would be 0 -- 1 -- 2 -- 3 -- 4. Then node $k$ is a root node for minimum height tree if and only if $\text{dist}(0, k) = \text{dist}(4, k) = 4/2$.

After-thought. There is a simpler approach: Mark all the leaf nodes as $d = 0$ and do BFS. The nodes mark with the largest distance are the root nodes for the MHTs.

### Timeline⌗

• [2021.06.16 22:13] Start
• [2021.06.16 22:26] First attempt (WA: 19/68)
• Reason: Wrong claim
• [2021.06.16 22:36] Second attempt (WA: 12/68)
• Reason: Careless mistake
• [2021.06.16 22:37] Third attempt (AC)

## B. Beautiful Array⌗

### Commentary⌗

This looks unsound! Although I have an intuition that divide-and-conquer works, I am not fully convinced on why the below approach worked.

I have a short solution that use divide-and-conquer.

class Solution:
def subbeautifulArray(self, arr: List[int]) -> List[int]:
n = len(arr)
if n <= 1: return arr[:]
return self.subbeautifulArray(arr[0::2]) + self.subbeautifulArray(arr[1::2])

def beautifulArray(self, n: int) -> List[int]:
return self.subbeautifulArray(list(range(1, n+1)))

### Timeline⌗

• [2021.06.16 22:38] Start
• [2021.06.16 22:43] First attempt (WA: 5/38)
• Reason: The claim does not even correct...
• [2021.06.16 22:58] Paused
• [2021.06.16 23:45] Resumed & Hinted
• [2021.06.16 23:49] Second attempt (AC)

## C. Wiggle Sort II⌗

### Commentary⌗

Suppose that there are $2n$ numbers. My approach initially is to rearrange the numbers in the below order:

1  n+1  2  n+2  3  n+3  ...  n  2n

However, the test case [1, 3, 3, 7] does not work because it will be rearranged to [1, 3, 3, 7], which is not wiggled. A possible wigged array could be [3, 7, 1, 3].

n+1  1  n+2  2  n+3  3  ...  2n  n

Although it looked more or less same, the minimum difference between consecutive entries is $n$ (it was $n-1$). This actually tells us that we are able to find a solution even if there are $n$ identical entries.

This looks unsound! How can we guaranteed that there are no solutions when there are $n+1$ identical entries?

### Timeline⌗

• [2021.06.16 22:58] Start
• [2021.06.16 23:14] First attempt (WA: 44/47)
• Reason: As stated above.
• [2021.06.16 23:22] Paused
• [2021.06.16 23:49] Resumed
• [2021.06.17 00:00] Second attempt (RE: 3/47)
• Reason: Got an IndexError for odd array lengths.
• [2021.06.17 00:01] Third attempt (AC)

## D. Checking Existence of Edge Length Limited Paths⌗

Idea. Sort and answer the queries by ascending limits. Merge the disjoint sets in between.

### Timeline⌗

• [2021.06.16 23:22] Start
• [2021.06.16 23:29] Paused
• [2021.06.17 00:03] Resumed & Hinted
• [2021.06.17 00:13] First attempt (TLE: 17/23)
• Reason: The DisjointSet implementation is slow.
• [2021.06.17 00:19] Second attempt (WA: 5/23)
• Reason: The DisjointSet implementation is incorrect.
• [2021.06.17 00:34] Third attempt (WA: 6/23)
• Reason: The DisjointSet implementation is incorrect.
• [2021.06.17 00:48] Fourth attempt (AC)

## E. Sliding Puzzle⌗

### Commentary⌗

Since the board is only $2\times 3$, there are only $6! = 720$ states. We can build a state diagram and perform a BFS.

graph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;a123450&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a123405&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a120453&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a123045&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a103425&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a102453&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;more1&#34; [label=&#34;...&#34;, shape=&#34;plaintext&#34;, fillcolor=&#34;transparent&#34;] &#34;more2&#34; [label=&#34;...&#34;, shape=&#34;plaintext&#34;, fillcolor=&#34;transparent&#34;] &#34;more3&#34; [label=&#34;...&#34;, shape=&#34;plaintext&#34;, fillcolor=&#34;transparent&#34;] &#34;a123450&#34; -- &#34;a123405&#34; &#34;a123450&#34; -- &#34;a120453&#34; &#34;a123405&#34; -- &#34;a123045&#34; &#34;a123405&#34; -- &#34;a103425&#34; &#34;a120453&#34; -- &#34;a102453&#34; &#34;a123045&#34; -- &#34;more1&#34; &#34;a103425&#34; -- &#34;more2&#34; &#34;a102453&#34; -- &#34;more3&#34; }

From the above graph, we can see that there are two states having distance 1.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;a123405&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a120453&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

Further, there are three states with distance 2.

digraph { graph [bgcolor="transparent"] node [color="#ffe4e1", fontcolor="#ffe4e1", fillcolor="#33333c", style="filled"] edge [color="#ffe4e1", fontcolor="#ffe4e1"] node [shape=&#34;rect&#34;] &#34;a123045&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a103425&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] &#34;a102453&#34; [label=&lt; &lt;TABLE border=&#34;0&#34; cellspacing=&#34;5&#34; cellpadding=&#34;10&#34;&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;1&lt;/TD&gt; &lt;TD border=&#34;0&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;&amp;nbsp;&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;2&lt;/TD&gt; &lt;/TR&gt; &lt;TR&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;4&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;5&lt;/TD&gt; &lt;TD border=&#34;3&#34; width=&#34;40&#34; height=&#34;40&#34;&gt;3&lt;/TD&gt; &lt;/TR&gt; &lt;/TABLE&gt;&gt;] }

By building the entire state tree, we are able to find the minimum number of steps to recover the sliding puzzle, or assure that the state is not solvable.

### Timeline⌗

• [2021.06.16 23:29] Start
• [2021.06.16 23:43] First attempt (AC)