3 LeetCode One-Liners That Look Easy (But Can Make One P*ss Their Pants In A Tech Interview)

LeetCode One-liner Array Questions That Look Easy At First Glance But Are Tricky Enough To Crash A Tech Interview

Generated with DALL-E 3

Here are 3 LeetCode one-liner array questions that look easy at first glance but are tricky enough to crash a tech interview.

#1: Convert A Non-negative Integer To Its English Word Representation

The question sounds simple but has a tricky solution.

Given a number (num), write a function that converts it into its corresponding English word representation (string).

For example, for 1234567, its English representation is One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven.

Let’s implement it.

We start with writing out a base case for zero.

if num == 0:
    return "Zero"

Next, we create some predefined word lists that map numbers into words.

less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
    "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", 
    "Eighteen", "Nineteen"]

tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]

thousands = ["", "Thousand", "Million", "Billion"]

After this, we define a helper function called words that helps us convert a number n that is less than 1000 into its word representation, recursively.

def words(n):
    if n == 0:
        return ""

    elif n < 20:
        return less_than_20[n] + " "

    elif n < 100:
        return tens[n//10] + " " + words(n % 10)

    else: 
        return less_than_20[n // 100] + " Hundred " + words(n % 100)

Finally, we iterate through each group of 3 digits (thousands) in the given number and convert each group into words, appending the appropriate thousands unit.

result = ""

for i, thousand in enumerate(thousands):
    if num == 0:
        break
    
    num, remainder = divmod(num, 1000)

    if remainder > 0:
        result = words(remainder) + thousand + " " + result

We then return this result.

return result.strip()

Here’s the complete function.

def numberToWords(num):
    if num == 0:
        return "Zero"
    
    less_than_20 = ["", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
                    "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", 
                    "Eighteen", "Nineteen"]

    tens = ["", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"]

    thousands = ["", "Thousand", "Million", "Billion"]

    def words(n):
        if n == 0:
            return ""
        elif n < 20:
            return less_than_20[n] + " "
        elif n < 100:
            return tens[n // 10] + " " + words(n % 10)
        else:
            return less_than_20[n // 100] + " Hundred " + words(n % 100)

    result = ""

    for i, thousand in enumerate(thousands):
        if num == 0:
            break

        num, remainder = divmod(num, 1000)

        if remainder > 0:
            result = words(remainder) + thousand + " " + result

    return result.strip()

---

#2: Given An Integer, Count The Total Number Of Digit '1' Appearing In All Non-negative Integers Less Than Or Equal To It

The question wants us to find all ‘1’s in the range till the given number n.

For example, for the number 10, there are two ‘1’s appearing in the non-negative numbers less than or equal to 10 as shown below —

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

I started with a naive solution to this problem as follows:

def countDigitOne(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n == 0:
        return 0

    count = 0
    
    for i in range(1, n + 1):
        for j in str(i):
            if j == "1":
                count += 1
                
    return count

This function works by iterating through each number in the given range up to the number n, converting each number to a string.

It then checks each character of the string for ‘1’.

If a ‘1’ is encountered, it increments the count variable.

This variable is finally returned at the end.

Unfortunately, the solution did not work for large numbers since the algorithm used a lot of memory.

Here’s a better approach.

Let’s write the base case first, which returns 0 because there are no positive numbers less than 1 and hence no 1s to count.

if n < 1:
  return 0

Next, we create two variables called count = 0 and factor = 1 that keep track of the 1s count and the current digit’s position (units, tens, hundreds etc.), respectively.

We write a while loop that lets us examine each digit in the number from the least to the most significant one.

The current digit, the digits to the left, and the digits to the right are stored in separate variables.

while factor <= n:
  current_digit = (n // factor) % 10
  digits_to_left = n // (factor * 10)
  digits_to_right = n % factor

Next, comes the main logic of our code.

  count += digits_to_left * factor
  
  if current_digit == 1:
      count += digits_to_right + 1

  elif current_digit > 1:
      count += factor

Finally, we move to the next more significant digit by increasing the factor by 10.

  factor *= 10

Here’s the complete code.

def countDigitOne(n):
    # Base case
    if n < 1: 
        return 0
        
    count = 0
    factor = 1 # This is the current digit's position (units, tens, etc.)
    
    while factor <= n:
        current_digit = (n // factor) % 10
        digits_to_left = n // (factor * 10)
        digits_to_right = n % factor
        
        # Main logic
        count += digits_to_left * factor
        
        if current_digit == 1:
            count += digits_to_right + 1

        elif current_digit > 1:
            count += factor
         
        factor *= 10 # Incrementing to more significant digit
    
    return count

---

#3: Given An Unsorted Integer Array, Return The Smallest Positive Integer That Is Not Present In It

The question goes like this.

For a given integer array, let’s says nums = [-10, 0, 5, 2], we need to find the smallest positive integer that is not a part of it i.e. 1 here.

There’s also a constraint — We must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Let’s code up the solution.

The first step is to ignore the negative numbers, zeros and numbers greater than the length of the array (since they cannot be the smallest missing positive integer).

n = len(nums)

for i in range(n):
  if nums[i] <= 0 or nums[i] > n:
    nums[i] = n + 1

In the next step, we iterate over the array and use the absolute value of each number to find an index. If the number is in the range between 1 to the length of the array n, we mark the corresponding index as negative.

This step marks that the integer represented by that index is present in the array.

for i in range(n):
    num = abs(nums[i]) 

    if 1 <= num <= n:
        idx = num - 1 

        if nums[idx] > 0: 
            nums[idx] = -nums[idx]

The first unmarked or positive value index represents the missing number.
Also, if all indices are marked, the missing number is n + 1.

for i in range(n):
    if nums[i] > 0:  
        return i + 1

return n + 1

Here’s the complete code.

def firstMissingPositive(nums):
    n = len(nums)

    # Step 1: Remove unnecessary values
    for i in range(n):
        if nums[i] <= 0 or nums[i] > n:
            nums[i] = n + 1

    # Step 2: Index marking
    for i in range(n):
        num = abs(nums[i]) 
 
        if 1 <= num <= n:
            idx = num - 1 

            if nums[idx] > 0:  
                nums[idx] = -nums[idx]

    # Step 3: Find the smallest missing positive integer
    for i in range(n):
        if nums[i] > 0:  # The first positive index + 1 is the missing number
            return i + 1

    # If no missing number in the range 1 to n, the missing number is n + 1
    return n + 1