Math

Notes and typical questions for Math related questions

Notes

• When the order of a list does NOT matter, how do you remove an element in $O(1)$? Override that element using the last element first and then remove the last element of the array.

Typical Questions

General Math Questions

• ⚪ LC 9. Palindrome Number

  • Optimal Answer. TC: $O(log_{10}{n})$, SC: $O(1)$

• ⚪ LC 13. Roman to Integer

  • Optimal Answer.

    • TC: $O(1)$, this is because the input Roman number has an upper limit of 3999 which is a constant

    • SC: $O(1)$

• LC 12. Integer to Roman

  • I feel my answer is better than the LeetCode editorial because it has fewer hardcoded values.

  • Optimal Answer. TC: $O(1)$, SC: $O(1)$

• 🟠 LC 7. Reverse Integer

  • Integer.MAX_VALUE = $2^{31}-1 = 2147483647$

  • Integer.MIN_VALUE = $-2^{31} = -2147483648$

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• 🟠 LC 31. Next Permutation

  • This can also be categorized as 2 pointers or greedy.

  • Ideas

    • To make the permutation larger, we need to swap a leftNum with a rightNum and leftNum < rightNum

    • To make the smallest larger permutation

      • Find rightmost valid leftNum, keep checking the pair of two successive numbers from the end of the array. The sequence starting from "leftNum index + 1" to the end of the array must be in descending order.

      • Find the rightmost valid rightNum, and keep checking numbers from "leftNum index + 1" to the end of the array

      • After the swap, Reverse the sequence starting from "leftNum index + 1" to the end of the array because it's in descending order, and reversing it can make the final valid answer smaller.

  • Optimal Answer. TC: $O(n)$, SC: $O(1)$

• 🟠 LC 50. Pow(x, n)

  • Its implementation is more complicated than I thought...

  • Optimal Answer. TC: $O(logn)$, SC: $O(1)$

• ⚪ LC 202. Happy Number

  • It's easy to overlook the solution with constant space complexity.

  • Explanation: https://leetcode.com/problems/happy-number/description/comments/1566928/

  • Optimal Answer

    • TC: $O(logn)$, it's very difficult to get this number. Check the analysis in the LC editorial.

      • great explanation! For approach 1, I will add a little bit of my own explanation because it may help a little. For the time complexity, the way we reach O(log N) is as so: first we follow this link (https://stackoverflow.com/a/50262470) to understand why summing the digits of a number is O(log N), where N is the number itself. So for our time complexity analysis, we will take this fact for granted (that the getNext() method is O(logN). The time complexity analysis is broken up into two steps:

        [based off of the insight that once a number reaches the <=243 threshold, it cannot get above it again]

        1. the amount of time it takes for a number to reach 243

        2. once a number reaches the <=243 threshold, the amount of type it takes to either a. discover a cycle or b. get to 1

        For step 1) we argue that the number of time to reach 243 is O(log N) + O(log log N) + ..., but we disregard the terms after O(log N) because they are insignificant compared with O(log N). So the time for step 1 is O(log N)

        For step 2) we argue that once a number reaches the <= 243 threshold, it will take at absolute worst case, 243 more getNext() calls before we a. reach cycle or b. get to 1. so each getNext call is O(log N) or O(d), where d is number of digits, this is the equivalent statement. so each getNext call here is O(3), or just 3. And we know that at absolute MOST we will have 243 more getNext calls, so 243 * 3 is the time complexity here.

        Adding the two steps together we get O(log N) + O(243 * 3), and in Big O constants drop out so we get O(log N) as our time complexity.

        Wrote this a bit quick, so excuse the grammar errors and poor structure lol. Hope this helps!

    • SC: $O(1)$

• 🔴 LC 843. Guess the Word

  • Optimal Answer. TC: $O(n)$, SC: $O(n)$

• ⚪ LC 380. Insert Delete GetRandom O(1)

  • Learned how to delete a specific item in ArrayList in TC $O(1)$.

  • Optimal Answer.

    • TC: For all functions, $O(1)$

      • SC: $O(n)$

• 🟠 LC 2013. Detect Squares

  • Optimal Answer.

    • Let $N$ be the number of points

    • add(...) : TC $O(1)$

    • count(...) : TC $O(N)$

    • SC: $O(N)$

• ⚪ LC 2364. Count Number of Bad Pairs

  • I used a very convoluted approach with TC $O(n)$ to solve this problem, but that's not ideal. The problem should be cleverly solved by using the given equation in the problem statement and making transformations.

  • Optimal Answer. TC: $O(n)$, SC: $O(n)$

• ⚪ LC 2965. Find Missing and Repeated Values

  • Optimal Answer. TC: $O(n^2)$, SC: $O(n^2)$

• ⚪ LC 66. Plus One

  • Optimal Answer. TC: $O(n)$, SC: $O(n)$

• 🟠 LC 172. Factorial Trailing Zeroes

  • Optimal Answer. TC: $O(logn)$, SC: $O(1)$

• ⚪ LC 149. Max Points on a Line

  • Optimal Answer. TC: $O(n^2)$, SC: $O(n)$

• 🟠 LC 273. Integer to English Words

  • English Number Grouping Rule: English uses a base-1000 grouping system when reading and writing large numbers. Digits are grouped every three places: thousand (10³), million (10⁶), billion (10⁹), trillion (10¹²). This differs from Chinese, which groups numbers by 10,000 (万). For example, 10,000 is read as ten thousand in English, and 100,000,000 (一亿) is one hundred million.

  • Optimal Answer. TC: $O(log_{10}n)$, SC: $O(1)$

Enumeration / Brute Force

• LC 2048. Next Greater Numerically Balanced Number

  • Optimal Answer.

    • Let $C=1224444$ be the largest possible numerically balanced number based on the given constraints.

    • TC: $O(C−n)$.

    • SC: $O(1)$.

Geometry

• 🟠 LC 939. Minimum Area Rectangle

  • Optimal Answer. TC: $O(n^2)$, SC: $O(n)$

• 🔴 LC 963. Minimum Area Rectangle II

  • How do you know if 4 points can form a rectangle?

    • Notice that a necessary and sufficient condition to form a rectangle with two opposite pairs of points is that the points must have the same center and radius.

  • Optimal Answer. TC: $O(n^2*log{n})$, SC: $O(n^2)$

• LC 3195. Find the Minimum Area to Cover All Ones I

  • Optimal Answer. TC: $O(m*n)$, SC: $O(1)$

• 🔴 LC 3197. Find the Minimum Area to Cover All Ones II

  • Core ideas

    • Firstly, think about how many ways there are to split an entire matrix into 3 rectangles.

    • Secondly, for each way, think about what you need to do for each rectangle.

  • Optimal Answer. TC: $O(m^2*n^2)$, SC: $O(m*n)$

• 🟠 LC 3025. Find the Number of Ways to Place People I

  • Optimal Answer. TC: $O(n^2)$, SC: $O(logn)$