Questionable LeetCode Solutions

LeetCode Solutions that I believe to be sub-optimal.

Minimum Amount of Time to Collect Garbage

✅ Accepted as official solution

• LeetCode link
• My solution
• LeetCode Repo Issue

My approach

No need for extra space or modifying the array input in-place. Just loop backward.

Sudoku Solver

✅ Accepted as official solution

• LeetCode link
• My solution
• LeetCode Repo Issue

My approach

Bitmasking instead of hash set. Hash set consumes 9 times more space than bitmasking ($O(n^2)$ versus $O(n)$).

Longest Ideal Subsequence

✅ Accepted as official solution

• LeetCode link
• My solution
• LeetCode Repo Issue

My approach

There are several redundancies in the solution. Looping through all 26 characters is unnecessary.

Maximal Score After Applying K Operations

✅ Accepted as official solution

• LeetCode link
• My solution
• LeetCode Repo Issue

My approach

You only need to gather the largest $k$ elements for the heap. Time complexity reduced to $O(klogk + nlogn)$, space complexity reduced to $O(k)$

Count number of nodes in a complete Binary Tree

• LeetCode link
• My solution

My approach

After getting the depth of the tree d, we want to know where the incomplete subtree starts from. For this, we check if the left subtree is "complete". If it is complete, we check for the left subtree of the right subtree. Else, we check for the left subtree of the left subtree.

Though my solution is still $O(log^2(n))$ with space $O(1)$, the total runtime time is actually cut in half since we decrease the depth each time we perform a subtree check.

Perfect squares

• LeetCode link
• My solution

My approach

Similar to the official solution, but there's no need to loop from $\lfloor\sqrt{n}\rfloor$ to $1$ to check if the number can be decomposed into sum of two squares. Instead we only need to loop from $\lfloor\sqrt{n}\rfloor$ to $\lfloor\sqrt{0.5n}\rfloor$.

3Sum Smaller

• LeetCode link
• My solution

My approach

Instead of checking the pairs of $(j,k)$ one by one, for every pair of $(i,j)$ we decrement $k$ from len(nums) - 1. If nums[i] + nums[j] + nums[k] < target, we break the while loop and increment the total number of pairs by $k-j$.

Grumpy Bookstore Owner

• LeetCode link
• My solution

My approach

One less for loop compared to the official solution.

24 Game

• LeetCode link
• My solution

My approach

The code is a lot faster if we set base case to be array size equal to $2$ instead of $1$.

Set Matrix Zeroes

• LeetCode link
• My solution

My approach

One less for loop compared to the official solution.

K-th Smallest in Lexicographical Order

• LeetCode link
• My solution

My approach

Using the formula for geometric series instead of a while loop significantly improves the speed of counting the number of steps.

Rationale: Think of this as a permutation problem. For any number between $1$ to $n$, there are $(1 + 10 + 10^2 + \dotsm 10^j) - \max((i + 1) \times 10^j - n - 1 , 0)$ possible numbers starting with $i$, where $j$ is the largest number such that $i\times10^j \leq n$.