LeetCode in 1 month

Preface

I decided to take on the challenge of solving LeetCode problems every day for the month of January 2026. The main goal was to refresh my knowledge of algorithms and data structures, as well as to improve my problem-solving skills. I used Python as my primary language, and I'm following the LeetCode Programming Skills study plan.

Solutions

Here are the solutions I came up with for a few notable problems I encountered throughout the month.

Problem 389: Find the Difference

You are given two strings s and t. String t is generated by random shuffling string s and then add one more letter at a random position. Return the letter that was added to t.

Initially, I thought of converting the strings to sets and finding the difference between them using the bitwise XOR operator ^. You can find more information regarding bitwise operations supported by Python in the docs.

def findTheDifference(self, s: str, t: str) -> str:
    return (set(s) ^ set(t)).pop()

However, this approach fails when there are duplicate characters in the strings. For example, this will work with s = "abcd" and t = "abcde", returning e. However, if s = "aa" and t = "a", it will return None.

To handle this case, we can use the difference between the sum of the ASCII values of the characters in the strings.

def findTheDifference(self, s: str, t: str) -> str:
    return chr(abs(sum(ord(i) for i in s) - sum(ord(j) for j in t)))

We simply sum the ASCII values of the characters in the strings (via the ord() function) and take the absolute difference. Then, we convert the result back to a character using the chr() function. This works for this particular problem, because we are guaranteed that there is only one character that is different between the two strings.

Problem 459: Repeated Substring Pattern

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

For this problem, I thought of using the length of the string (n) to determine the possible lengths of the substrings. If the length of the string is divisible (div) by the length of the substring (n // div), then we can check if the substring is repeated. To do that, we can use the modulo operator % and check if the remainder is zero, i.e. not n % div. Then, we can check if the substring is repeated div times by comparing it to the original string. If it is, then we return True. Otherwise, we increment div and repeat the process until we reach the middle of the string. Because, if the string is repeated, then the substring must be repeated at least twice.

On top of that, we have two edge cases to consider. First, if the length of the string is less than 2, then it cannot be constructed by taking a substring of it and appending multiple copies of the substring together since it is not divisible by any number except itself. Second, if all the characters in the string are the same, then it can be constructed by taking a substring of it and appending multiple copies of the substring together. In this case, we can just check if the length of the set of characters in the string is equal to 1 since there is only one unique character - len(set(s)) == 1.

def repeatedSubstringPattern(self, s: str) -> bool:
    n = len(s)
    if n < 2:
        return False

    if len(set(s)) == 1:
        return True

    div = 2
    while div <= n // 2:
        if not n % div:
            if s[: n // div] * div == s:
                return True
        div += 1
    return False

This approach works, but is a bit unintuitive. After checking the proposed solutions, I came upon this much simpler and elegant implementation. We can use the fact that if a string is repeated, then it must be a substring of itself. Therefore, we can check if the string is a substring of itself after duplicating it, and removing the first and last characters to account for trivial matches. If it is, then we return True. Otherwise, we return False. In this case, the solution is as follows:

def repeatedSubstringPattern(self, s: str) -> bool:
    return s in (s + s)[1:-1]

Problem 283: Move Zeroes

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.

At first, I came up with the following solution:

def moveZeroes(self, nums: list[int]) -> None:
    n = len(nums) - 1
    fast = n - 1
    while fast >= 0:
        if nums[fast] == 0:
            slow = fast + 1
            while nums[slow] != 0:
                nums[slow - 1] = nums[slow]
                nums[slow] = 0
                slow += 1
                if slow > n:
                    break
            slow = fast
        fast -= 1

As you can see, this solution is quite complex and involves multiple pointers and nested loops. However, it is a valid solution and works as expected. The issue lies in its (time) complexity, which is $O(n^2)$ in the worst case. This is because for each element, we may need to shift all subsequent elements to the right, resulting in a quadratic time complexity. It's also unintuitive and difficult to understand - we start from the end of the array and move towards the beginning, shifting elements to the right as we encounter zeros.

A much simpler and elegant solution is to use two pointers and swap elements in-place. We can use a fast pointer to iterate through the array and a slow pointer to keep track of the position where the next non-zero element should be placed. Whenever we encounter a non-zero element, we swap it with the element at the slow pointer and increment the slow pointer. This way, the time complexity becomes $O(n)$. Rewriting this solution using two pointers, we get:

def moveZeroes(self, nums: list[int]) -> None:
    n = len(nums)
    slow = 0
    for fast in range(n):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1
    return nums

Problem 1523: Count Odd Numbers in an Interval Range

Given two non-negative integers low and high. Return the count of odd numbers between low and high (inclusive).

The initial solution that came to mind was to iterate through the range from low to high and count the odd numbers using a generator expression. However, this approach has a time complexity of $O(n)$, which is not optimal for very large ranges, as it requires iterating through each number in the range.

sum(i % 2 != 0 for i in range(low, high + 1))

A more efficient approach is to calculate the total length of the range and determine how many odd numbers are present based on whether the length is even or odd, and whether the starting number low is odd or even. This approach has a time complexity of $O(1)$. If the length of the range is even, half of the numbers will be odd. If the length is odd, then we need to check if low is odd or even to determine if there is an extra odd number in the range. That is because if low is odd, then the range will have one more odd number than even numbers. Let's illustrate this with some examples.

For the range from 2 to 6 (inclusive), we have the numbers 2, 3, 4, 5, and 6. The odd numbers in this range are 3 and 5. The length of the range is 5 (which is odd), and since low (2) is even, we have 2 odd numbers.

For the range from 4 to 9 (inclusive), we have the numbers 4, 5, 6, 7, 8, and 9. The odd numbers in this range are 5, 7, and 9. Since the length of the range is 6 (which is even), regardless of whether low is odd or even, we have 3 odd numbers.

For the range from 1 to 5 (inclusive), we have the numbers 1, 2, 3, 4, and 5. The odd numbers in this range are 1, 3, and 5. The length of the range is 5 (which is odd), and since low (1) is odd, we have 3 odd numbers (5 // 2 + 1).

def countOdds(self, low: int, high: int) -> int:
    length = high - low + 1
    count = length // 2
    return count + 1 if length % 2 and low % 2 else count

💡 Tip: In Python, // is the floor division operator, which divides two numbers and rounds down to the nearest integer.

This solution works but is a bit verbose and not very intuitive. After reviewing the proposed solutions, I found a much simpler approach. We can use integer division to calculate the number of odd numbers up to high and subtract the number of odd numbers up to low - 1. This way, we can directly get the count of odd numbers in the range [low, high].

def countOdds(self, low: int, high: int) -> int:
    return (high + 1) // 2 - low // 2

🗒️ Note: We use high + 1 because Python's indexing is zero-based, and we want to include high in our count. Similarly, we use low without subtracting 1 because we want to exclude all the odd numbers below low.

Problem 67: Add Binary

Given two binary strings a and b, return their sum as a binary string.

This problem was the perfect excuse to get a refresher on decimal to binary conversion, and vice-versa.

To convert a decimal to binary, we simply keep dividing by 2, appending a 0 to the left of our resulting array if we get no remainder, 1 otherwise. The resulting string is our binary representation of said decimal. Let's look at the number 12:

12 | 2 (0)
 6 | 2 (0)
 3 | 2 (1)
 1 | 2 (1)
 -----
 1100

The other way around, to convert a binary to decimal, we simply iterate through each digit of the binary string, multiplying it by 2 raised to the power of its position (counting from right to left, starting at 0), and summing the results. Let's look at the binary number 1100:

$1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 = 8 + 4 + 0 + 0 = 12$

The implementation is straightforward. We convert both binary strings to decimal, sum them, and convert the result back to binary.

def addBinary(self, a: str, b: str) -> str:
    if a == b == "0":
        return "0"

    # Binary to decimal
    dec = 0
    for num in [a, b]:
        for n, i in enumerate(num[::-1]):
            if i == "1":
                dec += 2**n

    # Decimal to binary
    res = []
    while dec != 0:
        q, r = dec // 2, dec % 2
        dec = q
        res.insert(0, str(r))

    return "".join(res)

Problem 43: Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

For this particular problem, we must not convert inputs to integer directly. This makes it particularly cumbersome as it would have been very straightforward in Python - just casting each input to an integer and computing their product. I confess I couldn't make up a solution at first and had to look up the proposed solutions. Then it all became very clear. In essence, we simulate the multiplication process as we would do it by hand. We create an array to hold the intermediate results and then iterate through each digit of both numbers, multiplying them and adding the results to the appropriate positions in the array. Finally, we convert the array back to a string, taking care to handle any leading zeros.

def multiply(self, num1: str, num2: str) -> str:
    # Edge case: if either number is "0", the product is "0"
    if num1 == "0" or num2 == "0":
        return "0"

    m, n = len(num1), len(num2)
    result = [0] * (m + n)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            mul = (ord(num1[i]) - ord("0")) * (ord(num2[j]) - ord("0"))
            sum_ = mul + result[i + j + 1]

            result[i + j + 1] = sum_ % 10 # Last digit of the sum
            result[i + j] += sum_ // 10   # Carry over

    return "".join(map(str, result)).lstrip("0")

💡Tip: We use ord(i) - ord("0") to convert a character digit to its integer value, since we cannot use direct integer conversion.

🗒️ Note: We name the variable sum_ with an underscore at the end to avoid shadowing the built-in sum() method in Python.

Let's exemplify this step by step with num1 = "123" and num2 = "45". We initialise a result array of size m + n = 3 + 2 = 5, filled with zeros: [0, 0, 0, 0, 0]. Next, we iterate through each digit of num1 and num2 in reverse order, multiplying them and adding the results to the appropriate positions in the result array. For the first digit of num1 (3), we multiply it with each digit of num2, as follows:

     123
×      5
--------
     615    (123 × 5)

Then, we multiply 3 with 4, making sure to shift the result one position to the left.

     123
×     45
--------
     615    (123 × 5)
    4920    (123 × 4, shifted one position to the left)

Finally, we add the two results together to get the final product:

     123
×     45
--------
     615    (123 × 5)
+   4920    (123 × 4, shifted one position to the left)
--------
    5535

The final result is 5535, which we return as a string. In this case, the result array will be [0, 5, 5, 3, 5], which we convert to the string "5535" after removing any leading zeros, using the lstrip("0") method, and then joining the elements of the array into a single string using "".join(map(str, result)).

Problem 50: Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

For this problem, I had to brush up on my maths, namely, the properties of exponents. The key equations to keep in mind are:

• Zero exponent: $\quad x^0 = 1 \quad \text{for any } x \neq 0$
• Negative exponent: $\quad x^{-n} = \frac{1}{x^n} \quad \text{for any } n > 0$
• Power of an odd exponent: $\quad x^n = x \cdot x^{n-1} \quad \text{if } n \text{ is odd}$
• Power of an even exponent: $\quad x^n = (x^2)^{\frac{n}{2}} \quad \text{if } n \text{ is even}$

Using these properties, we can implement the pow function.

def myPow(self, x, n):
    if n == 0:
        return 1
    if n < 0:
        return 1 / self.myPow(x, -n)
    if n % 2:
        return x * self.myPow(x, n - 1)
    return self.myPow(x * x, n / 2)

Note that the power of an odd and even exponent are both derived from the definition of exponentiation. For odd exponents, we can express x^n as x * x^(n-1), since multiplying by x reduces the exponent by 1, making it even. For even exponents, we can express x^n as (x^2)^(n/2), since squaring x and halving the exponent maintains the same value. Eventually, we reach the base case of n == 0, where we return 1. This is called exponentiation by squaring¹ and is an efficient way to compute powers.

Outro

This was fun and challenging at times. I always enjoy solving these types of problems. It helps me think critically and improves my problem-solving skills. I managed to do 29 days in a row instead of the planned 31, but I'm satisfied with the progress I made. It's not about achieving perfection but about consistent practice and learning. On to the next challenge!