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="circle"] 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="circle"] "0a"[label="0"] "1a"[label="1"] "2a"[label="2"] "3a"[label="3"] "4a"[label="4"] "5a"[label="5"] "0b"[label="0"] "1b"[label="1"] "2b"[label="2"] "3b"[label="3"] "4b"[label="4"] "5b"[label="5"] subgraph cluster1 { style="filled" color="#55555c" label="Tree with root node = 2" labelloc=t "2a" -- "1a" "2a" -- "3a" "1a" -- "0a" "3a" -- "4a" "1a" -- "5a" } subgraph cluster2 { style="filled" color="#55555c" label="Tree with root node = 5" labelloc=t "5b" -- "1b" "1b" -- "0b" "1b" -- "2b" "2b" -- "3b" "3b" -- "4b" } }
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)
  1. LeetCode "Minimum Height Trees"
    https://leetcode.com/problems/minimum-height-trees/ ↩
  2. LeetCode "Beautiful Array"
    https://leetcode.com/problems/beautiful-array/ ↩
  3. LeetCode "Wiggle Sort II"
    https://leetcode.com/problems/wiggle-sort-ii/ ↩
  4. LeetCode "Checking Existence of Edge Length Limited Paths"
    https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/ ↩
  5. LeetCode "Sliding Puzzle"
    https://leetcode.com/problems/sliding-puzzle/ ↩