LeetCode Practice: Day 3

The problems today are Largest Magic Square¹, Spiral Matrix II², Find Kth Bit in Nth Binary String³, Reachable Nodes In Subdivided Graph⁴ and Subarrays with K Different Integers⁵. I am motivated today and decided to solve two more problems: Maximum Side Length of a Square with Sum Less than or Equal to Threshold⁶ and Jump Game V⁷.

The solution scripts are available: A, B, C, D, E, F and G.

gantt dateFormat YYYY-MM-DD HH:mm axisFormat %H:%M section Problem A A :2021-06-18 22:04, 13m section Problem B B :2021-06-18 22:17, 7m section Problem C C :2021-06-18 22:24, 14m section Problem D D :2021-06-18 22:38, 4m D :2021-06-18 23:22, 28m section Problem E E :2021-06-18 22:42, 40m section Problem F F :2021-06-18 23:52, 11m section Problem G G :2021-06-19 00:06, 12m

A. Largest Magic Square⌗

Idea. Just exhaust the squares $\mathcal{O}(mn\cdot\text{min}\{m, n\})$ and check if it is a magic square with $\mathcal{O}(k^2)$.

Timeline⌗

[2021.06.18 22:04] Start
[2021.06.18 22:17] First attempt (AC)

B. Spiral Matrix II⌗

Idea. Simple simulation.

Timeline⌗

[2021.06.18 22:17] Start
[2021.06.18 22:24] First attempt (AC)

C. Find Kth Bit in Nth Binary String⌗

Commentary⌗

There is a naive solution that computes all the bits of $S_n$ and take the $k$-th. I decided to use recursion that solves the problem with $\mathcal{O}(\text{log}\ k)$. Although it is an overkill, I practised.

The recursion is simple. Suppose that $B_k$ is the $k$-th bit of the sequence (one-indexed):

[Base Case] $B_k = 0$ if $k = 1$.
[Base Case] $B_k = 1$ if $k = 2^b$ for some integer $b > 0$.
[Transition] $B_k = 1 - B_{2^b - r}$ if $k = 2^b + r$ for some integers $b > 0$ and $0 < r < 2^b$.

Timeline⌗

[2021.06.18 22:24] Start
[2021.06.18 22:36] First attempt (RE: 4/63)
- Reason: Caused a stack overflow because I mishandled the second base case.
[2021.06.18 22:38] Second attempt (AC)

D. Reachable Nodes In Subdivided Graph⌗

Idea. Use Dijkstra’s algorithm to compute the distance from node 0 to the other nodes. Then for each edge in the original graph, count the number of new nodes those are reachable. Count also the nodes in the original graph those are reachable too.

Timeline⌗

[2021.06.18 22:36] Start
[2021.06.18 22:42] Paused
[2021.06.18 23:22] Resumed
[2021.06.18 23:43] First attempt (WA: 28/47)
- Reason: Heaps are sorted incorrectly.
[2021.06.18 23:50] Second attempt (AC)

E. Subarrays with K Different Integers⌗

Idea. For each $0 \leq l < n$, find the minimum value of $r$ such that $a_l, a_{l+1}, …, a_r$ has $k$ distinct elements. It can be computed in $\mathcal{O}(n)$ using sliding window. Similarly, find $r'$ such that $a_l, a_{l+1}, …, a_{r'}$ has $k+1$ distinct elements. Then the answer would be $\sum (r' - r)$.

Timeline⌗

[2021.06.18 22:42] Start
[2021.06.18 23:22] First attempt (AC)

F. Maximum Side Length of a Square with Sum Less than or Equal to Threshold⌗

Idea. Similar to A: exhaust the squares $\mathcal{O}(mn\cdot\text{min}\{m, n\})$. Compute the sum of the square with linear time from precomputation.

Timeline⌗

[2021.06.18 23:52] Start
[2021.06.19 00:03] First attempt (AC)

G. Jump Game V⌗

Idea. The goal is to find the length of a longest path of the given DAG.

Timeline⌗

[2021.06.19 00:06] Start
[2021.06.19 00:22] First attempt (AC)

LeetCode "Largest Magic Square"
https://leetcode.com/problems/largest-magic-square/ ↩
LeetCode "Spiral Matrix I"
https://leetcode.com/problems/spiral-matrix-ii/ ↩
LeetCode "Find Kth Bit in Nth Binary String"
https://leetcode.com/problems/find-kth-bit-in-nth-binary-string/ ↩
LeetCode "Reachable Nodes In Subdivided Graph"
https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/ ↩
LeetCode "Subarrays with K Different Integers"
https://leetcode.com/problems/subarrays-with-k-different-integers/ ↩
LeetCode "Maximum Side Length of a Square with Sum Less than or Equal to Threshold"
https://leetcode.com/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/ ↩
LeetCode "Jump Game V"
https://leetcode.com/problems/jump-game-v/ ↩