Leetcode 1 - 50

1. Two Sum

Problem

Given array of integers nums and target number
Return indices of two numbers that sum to target

Idea

Time = O(n), Space = O(n)
Iterate array and store current value and index in hashmap.
When iterating if target - current_value is in hashmap, return the indices.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    # Key = "first_num"
    # Value = index of "first_num" in "nums"
    d = {}

    for i in range(len(nums)):
        first_num = nums[i]
        second_num = target - first_num

        if second_num in d:
            first_num_index = i
            second_num_index = d[second_num]
            return [first_num_index, second_num_index]

        d[first_num] = i
    
    return "Not found"

2. Add Two Numbers

link

Problem

Given two linked lists
Each represents a number in reverse order
Sum both the numbers

Idea

Time = O(max(l1.length, l2.length)), Space = O(1)
Iterate through the lists simultaneously

def addTwoNumbers(self, l1: [ListNode], l2: [ListNode]) -> [ListNode]:
    def add_vals(l1, l2, carry):
        # val = carry + l1.val + l2.val
        val = carry
        if l1 is not None:
            val += l1.val
            l1 = l1.next
        if l2 is not None:
            val += l2.val
            l2 = l2.next

        # Handle carry
        if val >= 10:
            val = val - 10
            carry = 1
        else:
            carry = 0

        # Return the modified lists, carry, and a new node with the 'val'
        return l1, l2, carry, ListNode(val)


    l1, l2, carry, root = add_vals(l1, l2, 0)
    head = root

    while (l1 is not None) or (l2 is not None) or (carry != 0):
        l1, l2, carry, node = add_vals(l1, l2, carry)

        head.next = node
        head = head.next

    return root

3. Longest Substring Without Repeating Characters

link

Idea

Time = O(n), Space = O(1) or O(possible chars).
Maintain a hashmap, that stores the last occurrence of a character.
Iterate through the string, and keep updating the last occurrence of the current character to the current index.
There are two cases now
- If the character is not in the hashmap, then it means it is part of substring.
- If the character is in the hashmap, but its last occurrence is before the “start” of the substring, then it is part of the current substring.
- If the character is in the hashmap, and its last occurrence if after the “start” of the current substring, then it means we reached the end of current substring, and need to start the next substring from the last occurrence of that char.

def lengthOfLongestSubstring(self, s: str) -> int:
    substring_start = 0
    max_substring_length = 0
    d = {} # Key = char, Value = last seen index of char

    for i in range(len(s)):
        c = s[i]

        if c not in d:
            max_substring_length = max(max_substring_length, i - substring_start + 1)
        else:
            if d[c] < substring_start:
                max_substring_length = max(max_substring_length, i - substring_start + 1)
            else:
                substring_start = d[c] + 1

        d[c] = i

    return max_substring_length

4. Median of Two Sorted Arrays

link

Idea

Time = O(log(min(m, n))), Space = O(1)

Consider the two arrays

arr1 = x1 x2 x3 x4 x5 x6
arr2 = y1 y2 y3 y4 y5 y6 y7 y8

Make a partition at some position i = 2 in arr1

arr1 = x1 x2 | x3 x4 x5 x6
arr2 = y1 y2 y3 y4 y5 y6 y7 y8

Now there are i = 2 elements on the left in arr1. From this we can infer the position of partition in arr2, as the number of elements on left should be equal to the number of elements on the right.
- Total elements = 6 + 8 = 14 (m + n where m = len(arr1), n = len(arr2))
- Median = 14 // 2 = 7
- So there should be 7 elements on the left of median.
- With i=2 we can find the position of partition in arr2 as median - i i.e. 7 - 2 = 5. And we get the second array as arr2 = y1 y2 y3 y4 y5 | y6 y7 y8.
Checking the above logic for odd length
```
arr1 = 1 2
arr2 = 3 4 5
```
- Total elements = 2 + 3 = 5
- Median = 5 // 2 = 2
- If we make partition at i=1 in arr1, we get arr1 = 1 | 2.
- The partition in arr2 would be at median - i i.e. 2 - 1 = 1. And we get the second array as arr2 = 3 | 4 5.
- If we were to continue with this, then we would get the result as the element to the left of median (too lazy to check by hand).
To handle both odd and even case compute middle of second array as (M + N + 1) // 2 - i.

def findMedianSortedArrays(self, arr1: List[int], arr2: List[int]) -> float:
    if len(arr1) > len(arr2):
        return self.findMedianSortedArrays(arr2, arr1)
    
    low, high = 0, len(arr1)
    while low <= high:
        arr1_mid = (low + high) // 2
        arr2_mid = (len(arr1) + len(arr2) + 1) // 2 - arr1_mid

        # Handle edge cases
        arr1_left_min = -1e9 if arr1_mid == 0 else arr1[arr1_mid - 1]
        arr1_right_max = 1e9 if arr1_mid == len(arr1) else arr1[arr1_mid]

        arr2_left_min = -1e9 if arr2_mid == 0 else arr2[arr2_mid - 1]
        arr2_right_max = 1e9 if arr2_mid == len(arr2) else arr2[arr2_mid]

        # For the median we need to meet the following conditions
        # - arr1_left_min <= arr1_right_max (done, as arr is sorted)
        # - arr1_left_min <= arr2_right_max
        # - arr2_left_min <= arr2_right_max (done, as arr is sorted)
        # - arr2_left_min <= arr2_right_max
        if arr1_left_min <= arr2_right_max and arr2_left_min <= arr1_right_max:
            if (len(arr1) + len(arr2)) % 2 == 0:
                return (max(arr1_left_min, arr2_left_min) + min(arr1_right_max, arr2_right_max)) / 2
            return max(arr1_left_min, arr2_left_min)
        elif arr1_left_min > arr2_right_max:
            high = arr1_mid - 1
        else:
            low = arr1_mid + 1

5. Longest Palindrome Substring

link

Idea

Time = O(n^2), Space = O(1). There are 2n-1 centers, and each center can be expanded to the complete string length of n, so n*(2n-1) gives time complexity.
Find the center of length 2 and length 3 palindromes, and expand the substring from there.

def longestPalindrome(self, s: str) -> str:
    max_length = 1
    max_left, max_right = 0, 0

    # Find all even length palindromes
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            length = 0
            left, right = i, i + 1
            while left >= 0 and right <= len(s) - 1:
                if s[left] == s[right]:
                    length += 2
                    left -= 1
                    right += 1
                else:
                    break
            
            if length > max_length:
                max_length = length
                max_left = max(0, left + 1)
                max_right = min(len(s)-1, right - 1)

    
    # Find all odd length palindromes
    for i in range(len(s)-2):
        if s[i] == s[i+2]:
            length = 1
            left, right = i, i + 2
            while left >= 0 and right <= len(s) - 1:
                if s[left] == s[right]:
                    length += 2
                    left -= 1
                    right += 1
                else:
                    break
            
            if length > max_length:
                max_length = length
                max_left = max(0, left + 1)
                max_right = min(len(s)-1, right - 1)
    
    return s[max_left:max_right+1]

6. Zigzag Conversion

link

Problem - Given a string in zigzag order, print it line by line as shown below

Input = PAYPALISHIRING with numRows = 4

# P     I    N -> +6, +6, +6, +6
# A   L S  I G -> +4, +2, +4, +2
# Y  A  H R    -> +2, +4, +2, +4
# P     I      -> +6, +6, +6, +6

Idea

Time = O(n), Space = O(1)
Observe the pattern in the right side.
For the first row, it is +6, +6 i.e. (numRows - 1) * 2
Then for the next rows it doing -2 to the first jump, and +2 to the second jump (starting from 0)
In the last row, it is again +6, +6.

class Solution:
    def iterate_string(self, jump1, jump2, start_index):
        use_jump1 = True
        i = start_index

        while i < len(self.s):
            self.out += self.s[i]

            if use_jump1:
                i += jump1
                use_jump1 = False
            else:
                i += jump2
                use_jump1 = True
        

    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        self.s = s
        self.out = ''
        val = (numRows - 1) * 2

        # First row
        self.iterate_string(val, val, 0)
        
        # Middle rows with +2, -2
        jump1 = val
        jump2 = 0
        start = 0
        while jump1 != 2:
            jump1 -= 2
            jump2 += 2
            start += 1
            
            self.iterate_string(jump1, jump2, start)
            
        # Last row
        self.iterate_string(val, val, numRows-1)

        return self.out

7. Reverse integer

link

Problem. Given a 32-bit integer reverse the digits, and if the number overflows return 0

Idea

Time = O(1), Space = O(1). Constant in terms of the number of digits in the number. Since the number is bounded by 32-bits, it can only have math.floor(math.log10(MAX_INT)) digits which is constant.

def reverse(self, x: int) -> int:
    if x == 0:
        return x

    MIN_INT = -2**31
    MAX_INT = 2**31 - 1
    MAX_LENGTH = math.floor(math.log10(MAX_INT)) + 1

    out = 0
    if x >= 0:
        is_positive = True
        NUM = MAX_INT
    else:
        is_positive = False
        NUM = MIN_INT
        x = -x

    x_length = math.floor(math.log10(x)) + 1
    check_next = True

    for i in range(x_length):
        digit = x % 10
        x = x // 10

        if x_length == MAX_LENGTH and check_next:
            max_digit = (NUM // 10**(x_length - i - 1)) % 10 # Find the digit from the reverse order in NUM

            if not is_positive:
                max_digit = 9 - max_digit  # Because of 2's complement
            if digit > max_digit:
                return 0
            if digit < max_digit:
                check_next = False
        
        out = 10 * out + digit

    if is_positive:
        return out
    return -out

8. String to Integer (atoi)

link

Problem. Convert a string to 32-bit signed integer.

Idea

Time = O(n), Space = O(1)
Just follow the rules outlined in the problem statement and convert them to code nothing special.
Some things to note, your code should handle ‘+42’, ‘-42’, ‘42’, ‘00042’.

def myAtoi(self, s: str) -> int:
    MAX_INT = 2**31 - 1
    MIN_INT = 2**31

    i = 0
    # Remove leading whitespace
    while i < len(s):
        if s[i] == ' ':
            i += 1
        else:
            break
    
    # Check number is positive or negative
    is_positive = None
    if i < len(s):
        if s[i] == '+':
            is_positive = True
            i += 1
        elif s[i] == '-':
            i += 1
            is_positive = False
        elif s[i] >= '0' and s[i] <= '9':
            is_positive = True
        else:
            is_positive = True

    # Remove leading zeros
    while i < len(s):
        if s[i] != '0':
            break
        i += 1

    # Get the number and ignore everything after that
    num = ''
    while i < len(s):
        if s[i] >= '0' and s[i] <= '9':
            num += s[i]
            i += 1
        else:
            break
    
    # Handle empty string
    if len(num) == 0:
        num = '0'
    
    target = None
    if is_positive:
        target = str(MAX_INT)
    else:
        target = str(MIN_INT)

    out = None
    if len(num) > len(target):
        # Clear overflow
        if is_positive:
            out = MAX_INT
        else:
            out = -MIN_INT
    elif len(num) < len(target):
        # Can never overflow
        out = 0
        for i in range(len(num)):
            out = out * 10 + int(num[i])

        if not is_positive:
            out = -out
    else:
        # Check if overflow occurs
        overflow = False
        for i in range(len(num)):
            if num[i] > target[i]:
                overflow = True
                break
            elif num[i] < target[i]:
                break

        if overflow:
            # Overflow occurred
            if is_positive:
                out = MAX_INT
            else:
                out = -MIN_INT
        else:
            # No overflow occurred
            out = 0
            for i in range(len(num)):
                out = out * 10 + int(num[i])
            
            if not is_positive:
                out = -out
    
    return out

9. Palindrome number

link

Problem

Check number is palindrome without converting to string.

Idea

Time = O(1), Space = O(1), as the number is bounded to 32-bits.

Check the first and last digit and repeat to center and use math.floor(math.log10(x)) + 1 to get length of number.

def isPalindrome(self, x: int) -> bool:
    if x < 0:
        return False
    if x == 0:
        return True

    l = math.floor(math.log10(x)) + 1
    
    for i in range(l // 2):
        left_digit = (x // 10**(l-i-1)) % 10
        right_digit = (x // 10**(i)) % 10
        
        if left_digit != right_digit:
            return False
    return True

You could have also tried reversing the number as shown below. But this has the problem that the number might overflow, and you would have to do additional checks for that.

# This code will result in overflow
new_num = 0
orig_x = x
while x != 0:
    digit = x % 10
    new_num = new_num * 10 + digit
    x = x // 10

return orig_x == new_num

10. Regular Expression Matching

link

Problem

Support . (match any character) and * (match zero or more of the preceding character)

Algorithms

Leetcode

Notes

CSS

Short Notes

HTML

React

Investing

Rust

Header Links

Leetcode 1 - 50

1. Two Sum

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindrome Substring

6. Zigzag Conversion

7. Reverse integer

8. String to Integer (atoi)

9. Palindrome number

10. Regular Expression Matching