# 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

Problem

• 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]:
# 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)

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

return root``````

### 3. Longest Substring Without Repeating Characters

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

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

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

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

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)

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
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

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

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

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