LeetCode Practice: Day 2

The problems today are Construct the Lexicographically Largest Valid Sequence¹, Make Sum Divisible by P², Find the Winner of an Array Game³, Valid Permutations for DI Sequence⁴ and Closest Subsequence Sum⁵.

The solution scripts are pushed on my Github repository: A, B, C, D and E.

A. Construct the Lexicographically Largest Valid Sequence⌗

Commentary⌗

Suppose that $n = 5$ in our example. Initially there is an array of nine empty entries and none of the numbers are used.

The largest unused number that can be filled on the first entry is 5. Let's fill it into the first (and the sixth due to constraints):

The unused numbers are $\{1, 2, 3, 4\}$. The largest unused number that fits on the second entry is 3. Note that 4 is not feasible because the sixth entry is already filled.

We then can fit 4 and 1 to the third and the fourth entries, respectively:

However, the only unused number is 2 and it does not fit to the remaining entries. Hence, we will backtrack to the previous state.

The only number that fits to the fourth entry is 1. Since we have already tested it, there are no solutions and the previous state is further backtracked.

From above, putting 4 into the third entry yields no valid solutions. We will put the next possible number, which is 1. Filling in the remaining entries we have the lexigraphically largest sequence.

Timeline⌗

• [2021.06.17 22:33] Start
• [2021.06.17 22:47] First attempt (AC)

B. Make Sum Divisible by P⌗

Commentary⌗

We are given an array of $1 \leq n \leq 10^5$ elements $a_1, a_2, ..., a_n$. The objective is to remove the shortest subarray such that the sum of the remaining entries is divisible by a given modulo $p$.

My approach is to compute two partial sums, $L_k$ and $R_k$ for $k = 0, 1, ..., n$:

\[L_k = \left(+\sum_{i=1}^k a_i\right)\ \text{mod}\ p, \qquad R_k = \left(-\sum_{i=k+1}^n a_i\right)\ \text{mod}\ p.\]

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        n = len(nums)

        left_partial_sums  = [0 for _ in range(n+1)]
        right_partial_sums = [0 for _ in range(n+1)]
        
        for i in range(n):
            left_partial_sums[i+1] = (left_partial_sums[i] + nums[i]) % p

        for i in range(n, 0, -1):
            right_partial_sums[i-1] = (right_partial_sums[i] - nums[i-1]) % p
        
        # Omitted. Let's cover that later.

# Example 1 from the Problem

nums = [3, 1, 4, 2]
p    = 6

left_partial_sums  = [0, 3, 4, 2, 4] # before modulo: [  0,  3,  4,  8, 10]
right_partial_sums = [4, 5, 0, 4, 0] # before modulo: [-10, -7, -6, -2,  0]

What are the partial sums for? Let's make a claim:

Proof. The below operations are taken under modulo $p$.

\[\begin{aligned} & (a_1 + a_2 + ... + a_m) + (a_{m+k+1} + a_{m+k+2} + ... + a_n) \\ \equiv\ & \sum_{i=1}^m a_i + \sum_{i=m+k+1}^{n} a_{i} \\ \equiv\ & \sum_{i=1}^m a_i - \left(-\sum_{i=m+k+1}^{n} a_{i}\right) \\ \equiv\ & L_m - R_{m+k} \\ \equiv\ & 0 \end{aligned}\]

From the above claim, we can remove either one of the following subarray to achieve our goal:

1. $a_1, a_2$ (the remaining entries are 4 and 2, which sums to 6);
2. $a_1, a_2, a_3, a_4$ (this should be rejected because all entries are removed);
3. $a_3$ (the remaining entries are 3, 1 and 2).

We could remove only one element to make the sum divisible by 6.

One careless mistake⌗

I received a TLE while solving this. The below code is extracted from the attempt:

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        # Omitted...

        for i in range(n+1):
            lhs[left_partial_sums[i]] = lhs.get(left_partial_sums[i], []) + [i]
            rhs[right_partial_sums[i]] = rhs.get(right_partial_sums[i], []) + [i]
      
        # Omitted...

I initially thought that the time complexity for the above snippet is $\mathcal{O}(n)$. It is instead $\mathcal{O}(n^2)$ because we need to copy the slice every time it is referred. I used append to improve the time complexity.

class Solution:
    def minSubarray(self, nums: List[int], p: int) -> int:
        # Omitted...

        for i in range(n+1):
            lhs[left_partial_sums[i]] = lhs.get(left_partial_sums[i], [])
            lhs[left_partial_sums[i]].append(i)
            rhs[right_partial_sums[i]] = rhs.get(right_partial_sums[i], [])
            rhs[right_partial_sums[i]].append(i)

        # Omitted...

Timeline⌗

• [2021.06.17 22:47] Start
• [2021.06.17 22:57] Paused
• [2021.06.17 23:28] Resumed
• [2021.06.17 23:50] First attempt (WA: 132/142)
  • Reason: Computed an incorrect index.
• [2021.06.18 23:54] Second attempt (TLE: 139/142)
  • Reason: As stated above.
• [2021.06.18 00:00] Third attempt (AC)

C. Find the Winner of an Array Game⌗

Timeline⌗

• [2021.06.17 22:57] Start
• [2021.06.17 23:07] First attempt (AC)

D. Valid Permutations for DI Sequence⌗

Timeline⌗

• [2021.06.17 23:07] Start
• [2021.06.17 23:11] Paused
• [2021.06.18 00:00] Resumed
• [2021.06.18 00:10] Hinted
• [2021.06.18 00:37] First attempt (AC)

E. Closest Subsequence Sum⌗

Timeline⌗

• [2021.06.17 23:11] Start
• [2021.06.17 23:21] First attempt (WA: 0/73)
  • Reason: I misclicked submit during testing...
• [2021.06.17 23:28] Second attempt (AC)

Postmortem⌗

Surprisingly, I was used to solve dynamic programming problems effectively when I was in ACM-ICPC team. However it took far more time for me to figure out that D was a DP problem. On the other hand, I received less incorrect attempts. Does it mean that I am more careful than yesterday?