## Pattern: Misc

### [Easy] Simple Moving Average

#### Problem

• Given a list, calculate a moving average of a window of size windowSize of numbers.
• Example:
Input:
a = [3, 1, 10, 3, 5]
windowSize = 2

Output:
2.0
5.5
6.5
4.0


#### Solution

if windowSize > len(a):
return -1

# Get the first window.
currSum = sum(a[0:windowSize])
print(currSum/windowSize)

# Slide the window from left to right.
for i in range(len(a) - windowSize):
currSum += a[windowSize+i]
currSum -= a[i]
print(currSum/windowSize)

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

#### Problem

• You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

• You may assume the two numbers do not contain any leading zero, except the number 0 itself.

• Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

• Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]

• Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

• Constraints:
• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.
• See problem on LeetCode.

#### Solution: Maintain carry and use divmod

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
carry = 0
res = n = ListNode(0)
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
carry, val = int(carry) // 10, int(carry) % 10 # or divmod(carry, 10)
n.next = n = ListNode(val) # or the traditional "n.next = ListNode(val); n = n.next"
return res.next;

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [7/Medium] Reverse Integer

#### Problem

• Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1], then return 0.

• Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

• Example 1:

Input: x = 123
Output: 321

• Example 2:
Input: x = -123
Output: -321

• Example 3:
Input: x = 120
Output: 21

• Constraints:
• -2^31 <= x <= 2^31 - 1
• See problem on LeetCode.

#### Solution: Convert to str, reverse str and add sign

class Solution(object):
def reverse(self, x: int) -> int:
# extract the sign
s = (x > 0) - (x < 0)
# or cmp(x, 0) which returns negative if x<y, zero if x==y, positive if x>y.

# Change the sign to + for negative numbers since
# [::-1] would move the - sign to the end.
# Note that for positive numbers, this is a no op.
r = int(str(x * s)[::-1])

# Put the sign back.
return s * r * (r < 2**31)

##### Complexity
• Time: $$O(n + n) = O(n)$$
• Space: $$O(1)$$

### [8/Medium] String to Integer (atoi)

#### Problem

• Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer (similar to C/C++’s atoi function).

• The algorithm for myAtoi(string s) is as follows:

2. Check if the next character (if not already at the end of the string) is ‘-‘ or ‘+’. Read this character in if it is either. This determines if the final result is negative or positive respectively. Assume the result is positive if neither is present.
3. Read in next the characters until the next non-digit character or the end of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e., “123” -> 123, “0032” -> 32). If no digits were read, then the integer is 0. Change the sign as necessary (from step 2).
5. If the integer is out of the 32-bit signed integer range [-2^31, 2^31 - 1], then clamp the integer so that it remains in the range. Specifically, integers less than -2^31 should be clamped to -2^31, and integers greater than 1. 2^31 - 1 should be clamped to 2^31 - 1.
6. Return the integer as the final result.
• Note:
• Only the space character ‘ ‘ is considered a whitespace character.
• Do not ignore any characters other than the leading whitespace or the rest of the string after the digits.
• Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
^
Step 3: "42" ("42" is read in)
^
The parsed integer is 42.
Since 42 is in the range [-2^31, 2^31 - 1], the final result is 42.

• Example 2:
Input: s = "   -42"
Output: -42
Explanation:
^
Step 2: "   -42" ('-' is read, so the result should be negative)
^
Step 3: "   -42" ("42" is read in)
^
The parsed integer is -42.
Since -42 is in the range [-2^31, 2^31 - 1], the final result is -42.

• Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading whitespace)
^
Step 2: "4193 with words" (no characters read because there is neither a '-' nor '+')
^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next character is a non-digit)
^
The parsed integer is 4193.
Since 4193 is in the range [-2^31, 2^31 - 1], the final result is 4193.

• Constraints:
• 0 <= s.length <= 200
• s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.
• See problem on LeetCode.

#### Solution: RegEx

class Solution(object):
def myAtoi(self, s: str) -> int:
"""
:type str: str
:rtype: int
"""
###better to do strip before sanity check (although 8ms slower):
#ls = list(s.strip())
#if len(ls) == 0 : return 0
if len(s) == 0:
return 0
ls = list(s.strip())

sign = -1 if ls[0] == '-' else 1
if ls[0] in ['-','+']:
del ls[0]

ret, i = 0, 0
while i < len(ls) and ls[i].isdigit():
ret = ret*10 + ord(ls[i]) - ord('0')
i += 1

return max(-2**31, min(sign * ret,2**31-1))

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$
class Solution:
def myAtoi(self, s: str) -> int:
if len(s) == 0:
return 0

i = 0
while i < len(s) and s[i] == ' ':
i += 1
if i == len(s): # all are leading whitespace
return 0

if s[i]=='+':
sign = 1
i += 1
elif s[i]=='-':
sign = -1
i += 1
else:
sign = 1

val = 0
while i < len(s) and s[i].isdigit():
val = val*10 + ord(s[i]) - ord('0')
i += 1

res = val*sign
if res < -2**31: return -2**31
elif res > 2**31-1: return 2**31-1
else: return res

##### Complexity
• Time: $$O(n)$$ where $$n = len(s)$$
• Space: $$O(1)$$

#### Solution: RegEx

class Solution:
# @return an integer
def myAtoi(self, s: str) -> int:
str = str.strip()
str = re.findall('(^[\+\-0]*\d+)\D*', str)

try:
result = int(''.join(str))
MAX_INT = 2147483647
MIN_INT = -2147483648

if result > MAX_INT > 0:
return MAX_INT
elif result < MIN_INT < 0:
return MIN_INT
else:
return result
except:
return 0

##### Complexity
• Time: $$O(n + n) = O(n)$$
• Space: $$O(1)$$

### [9/Easy] Palindrome Number

#### Problem

• Given an integer x, return true if x is palindrome integer.

• An integer is a palindrome when it reads the same backward as forward.

• For example, 121 is a palindrome while 123 is not.

• Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

• Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

• Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

• Constraints:
• -2^31 <= x <= 2^31 - 1
• Follow up: Could you solve it without converting the integer to a string?

• See problem on LeetCode.

#### Solution: Convert the number to string and compare it with the reversed string

• This is the easiest way to check if integer is palindrome.

• Convert the number to string and compare it with the reversed string.

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

return str(x) == str(x)[::-1]

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$ for storing the reversed integer

#### Solution: Don’t convert the number to string, recreate a new number in reverse order

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

inputNum = x
newNum = 0

# reverse number
while x:
newNum = newNum * 10 + x % 10
x = x // 10

return newNum == inputNum

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$ for storing the reversed integer

#### Solution: Instead of reversing the whole integer, let’s convert half of the integer and then check if it’s palindrome

• Instead of reversing the whole integer, let’s convert half of the integer and then check if it’s palindrome. How do we know when we’ve reached the half? Check if our new half is greater than the original one.

• For e.g.,

Even case:
If x = 1234, then let's reverse x with a loop.
Initially, x = 1234, result = 0
Loop iteration #1: x = 123, result = 1
Loop iteration #2: x = 12, result = 12

Odd case:
If x = 15951, then let's reverse x with a loop.
Initially, x = 15951, result = 0
Loop iteration #1: x = 1595, result = 1
Loop iteration #2: x = 159, result = 15
Loop iteration #3: x = 15, result = 159

• We see that result > x after 3 loops and we’ve crossed the digits of the integer half way the integer because it’s an integer of odd length. If it’s an even length integer, the loop stops exactly in the middle after iteration 2.

• Now we can compare x and result if the integer has an even length, or x and result//10 if the integer has an odd length and return True if they match.

class Solution:
def isPalindrome(self, x: int) -> bool:
# if x is negative, return False. if x is positive and last digit is 0, that also cannot form a palindrome, return False.
if x < 0 or (x > 0 and x % 10 == 0):
return False

result = 0

# reverse number till the midpoint
while x > result:
result = result * 10 + x % 10
x = x // 10

return x == result or x == result // 10 # or return True if (x == result or x == result // 10) else False

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$ for storing the reversed integer

### [14/Easy] Longest Common Prefix

#### Problem

• Write a function to find the longest common prefix string amongst an array of strings.

• If there is no common prefix, return an empty string "".

• Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

• Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

• Constraints:
• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.
• See problem on LeetCode.

#### Solution: Chop off the last character every iteration until the prefix fits the string

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
"""
:type strs: List[str]; rtype: str
"""
# early termination: if strs is None
if not strs:
return None

# early termination: if len(strs) is an iterable but has no strings inside
if not len(strs):
return None

prefix = strs[0] # or "min(strs, key=len)" or "sorted(strs, key=len)[0]"

for s in strs:
while s[:len(prefix)] != prefix: # or "while not s.startswith(prefix):"
# remove a character from "prefix" from the end
# until the prefix fits the string
prefix = prefix[:-1]

return prefix

##### Complexity
• Time: $$O(n^2)$$
• Space: $$O(1)$$

#### Solution: Aggregate the characters in each string by their positions and build the prefix incrementally until you hit >1 unique chars

class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
"""
:type strs: List[str]; rtype: str
"""
# the zip() call here aggregates the characters in each string
# by their positions, so the prefix/initial characters
# feature first.
# for example:
# >>> strs = ["flower","flow","flight"]
# >>> aggregatedCharsByPos = zip(*strs) # <zip object at location>
# >>> list(aggregatedCharsByPos)
# [('f', 'f', 'f'), ('l', 'l', 'l'), ('o', 'o', 'i'), ('w', 'w', 'g')]
# note that if the length of the iterables are not equal,
# zip creates the list of tuples of length equal to the smallest iterable.
aggregatedCharsByPos, retVal = zip(*strs), ""

for ch in aggregatedCharsByPos:
# if there are >1 unique characters at the same position,
# get out of the loop since you have the longest prefix already
if len(set(ch)) > 1:
break

# build up return value
retVal += c[0]

return retVal

##### Complexity
• Time: $$O(n + n) = O(n)$$
• Space: $$O(1)$$

### [21/Easy] Merge Two Sorted Lists

#### Problem

• You are given the heads of two sorted linked lists list1 and list2.

• Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

• Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

• Example 2:
Input: list1 = [], list2 = []
Output: []

• Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

• Constraints:
• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both list1 and list2 are sorted in non-decreasing order.
• See problem on LeetCode.

#### Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None:
return list2
elif list2 is None:
return list1
elif list1.val <= list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2

##### Complexity
• Time: $$O(m+n)$$ where $$m$$ and $$n$$ are the lengths of the two lists respectively
• Space: $$O(1)$$

### [31/Medium] Next Permutation

#### Problem

• A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
• For example, for arr = [1,2,3], the following are considered permutations of arr: [1,2,3], [1,3,2], [3,1,2], [2,3,1].
• The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
• Given an array of integers nums, find the next permutation of nums.
• The replacement must be in place and use only constant extra memory.

• Example 1:
Input: nums = [1,2,3]
Output: [1,3,2]

• Example 2:
Input: nums = [3,2,1]
Output: [1,2,3]

• Example 3:
Input: nums = [1,1,5]
Output: [1,5,1]

• Constraints:
• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100
• See problem on LeetCode.

#### Solution: Find the first non-increasing element

class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""

# To find next permutation, we'll start from the end.
i = j = len(nums)-1

# First we'll find the first non-increasing element starting from the end.
while i > 0 and nums[i-1] >= nums[i]:
i -= 1

# After completion of the first loop, there will be two cases:
# 1. "i" becomes zero (this will happen if the given array is sorted in decreasing order). In this case, simply reverse the sequence and return.
if i == 0:
nums.reverse()
return
# 2. If "i" is not zero then we'll find the first number greater than nums[i-1] starting from end.
while nums[j] <= nums[i-1]:
j -= 1

# Now our i and j pointers are pointing at two different positions:
# i -> first non-ascending number from end
# j -> first number greater than nums[i-1]

# We'll swap these two numbers
nums[i-1], nums[j] = nums[j], nums[i-1]

# We'll reverse the sequence starting from i to end
nums[i:]= nums[len(nums)-1:i-1:-1]

# We don't need to return anything as we've modified nums in-place

• Take an example from Nayuki and try to hand-trace the above code manually. This will better help to understand the code.

##### Complexity
• Time: $$O(3n) = O(n)$$
• Space: $$O(1)$$

### [43/Medium] 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.

• Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

• Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

• Example 2:
Input: num1 = "123", num2 = "456"
Output: "56088"

• Constraints:
• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.
• See problem on LeetCode.

#### Solution: Decode numbers, multiply them and encode them together

class Solution:
def multiply(self, num1: str, num2: str) -> str:
if num1 == '0' or num2 == '0':
return '0'

def decode(num):
ans = 0
for i in num:
ans = ans*10 + (ord(i) - ord('0'))
return ans

def encode(s):
news = ''
while s:
a = s % 10
s = s // 10
news = chr(ord('0') + a) + news
return news

return encode(decode(num1) * decode(num2))

• Same approach; differently structured:
class Solution(object):
def multiply(self, num1: str, num2: str) -> str:
"""
:type num1: str
:type num2: str
:rtype: str
"""
res = 0 # output
carry1 = 1 # carry1 takes care of num1

for i in num1[::-1]: # this goes over num1 from right to left as we do normal multiplication, in the above example first 3 and then 2.
carry2 = 1 # takes care of num2

for j in num2[::-1]: # this goes over num2 from right to left as we do normal multiplication, in the above example first 6 and then 3.
res += int(i)*int(j)*carry1*carry2 # this is each component calculated separately and added to res
carry2 *= 10 # after first iteration (number 6 is covered), it goes to the next number from right, which is 3 here, actually 30, right? That's why it multiplies the carry2 by 10. Similar for carry1.

carry1 *= 10

return str(res)

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [68/Hard] Valid Sudoku

#### Problem

• Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition. Note:
• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.
• Example 1:

Input: board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

• Example 2:
Input: board =
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

• Constraints:
• board.length == 9
• board[i].length == 9
• board[i][j] is a digit 1-9 or '.'.
• See problem on LeetCode.

def isValidSudoku(self, board):
return (self.is_row_valid(board) and
self.is_col_valid(board) and
self.is_square_valid(board))

def is_row_valid(self, board):
for row in board:
if not self.is_unit_valid(row):
return False
return True

def is_col_valid(self, board):
for col in zip(*board):
if not self.is_unit_valid(col):
return False
return True

def is_square_valid(self, board):
for i in (0, 3, 6):
for j in (0, 3, 6):
square = [board[x][y] for x in range(i, i + 3) for y in range(j, j + 3)]
if not self.is_unit_valid(square):
return False
return True

def is_unit_valid(self, unit):
unit = [i for i in unit if i != '.']
return len(set(unit)) == len(unit)


#### Solution: One-liner using Counter

def isValidSudoku(self, board):
return 1 == max(collections.Counter(
x
for i, row in enumerate(board)
for j, c in enumerate(row)
if c != '.'
for x in ((c, i), (j, c), (i/3, j/3, c))
).values() + [1])

• The + [1] is only for the empty board, where max would get an empty list and complain. It’s not necessary to get it accepted here, as the empty board isn’t among the test cases, but it’s good to have.

#### Solution: One-liner using len(set).

def isValidSudoku(self, board):
seen = sum(([(c, i), (j, c), (i/3, j/3, c)]
for i, row in enumerate(board)
for j, c in enumerate(row)
if c != '.'), [])
return len(seen) == len(set(seen))


#### Solution: One-liner using any.

def isValidSudoku(self, board):
seen = set()
return not any(x in seen or seen.add(x)
for i, row in enumerate(board)
for j, c in enumerate(row)
if c != '.'
for x in ((c, i), (j, c), (i/3, j/3, c)))


#### Solution: One-liner with iterating a different way

def isValidSudoku(self, board):
seen = sum(([(c, i), (j, c), (i/3, j/3, c)]
for i in range(9) for j in range(9)
for c in [board[i][j]] if c != '.'), [])
return len(seen) == len(set(seen))


### [68/Hard] Text Justification

#### Problem

• Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

• You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ‘ ‘ when necessary so that each line has exactly maxWidth characters.

• Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

• For the last line of text, it should be left-justified and no extra space is inserted between words.

• Note:
• A word is defined as a character sequence consisting of non-space characters only.
• Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.
• Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This    is    an",
"example  of text",
"justification.  "
]

• Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
"What   must   be",
"acknowledgment  ",
"shall be        "
]
Explanation: Note that the last line is "shall be    " instead of "shall     be", because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.

• Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
"Science  is  what we",
"understand      well",
"enough to explain to",
"a  computer.  Art is",
"everything  else  we",
"do                  "
]

• Constraints:
• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• words[i] consists of only English letters and symbols.
• 1 <= maxWidth <= 100
• words[i].length <= maxWidth
• See problem on LeetCode.

#### Solution: Two loops

class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
ans, cur = [], []
chars = 0

for word in words:
# if cur is empty or the total chars + total needed spaces + next word fit
if not cur or (len(word) + chars + len(cur)) <= maxWidth:
cur.append(word)
chars += len(word)
else:
# place spaces, append the line to the ans, and move on
line = self.placeSpacesBetween(cur, maxWidth - chars)
ans.append(line)
cur.clear()
cur.append(word)
chars = len(word)

# left justify any remaining text, which is easy
if cur:
extra_spaces = maxWidth - chars - len(cur) + 1
ans.append(' '.join(cur) + ' ' * extra_spaces)

return ans

def placeSpacesBetween(self, words, spaces):
if len(words) == 1: return words[0] + ' ' * spaces

space_groups = len(words)-1
spaces_between_words = spaces // space_groups
extra_spaces = spaces % space_groups

cur = []
for word in words:
cur.append(word)

# place the min of remaining spaces or spaces between words plus an extra if available
cur_extra = min(1, extra_spaces)
spaces_to_place = min(spaces_between_words + cur_extra, spaces)

cur.append(' ' * spaces_to_place)

if extra_spaces: extra_spaces -= 1
spaces -= spaces_to_place

return ''.join(cur)

##### Complexity
• Time: $$O(n^2)$$
• Space: $$O(n)$$

#### Solution: Two loops; cleaner version

class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
i, N, result = 0, len(words), []

while i < N:
# decide how many words to be put in one line
oneLine, j, currWidth, positionNum, spaceNum = [words[i]], i + 1, len(words[i]), 0, maxWidth - len(words[i])
while j < N and currWidth + 1 + len(words[j]) <= maxWidth:
oneLine.append(words[j])
currWidth += 1 + len(words[j])
spaceNum -= len(words[j])
positionNum, j = positionNum + 1, j + 1
i = j

# decide the layout of one line
if i < N and positionNum:
spaces = [' ' * (spaceNum // positionNum + (k < spaceNum % positionNum)) for k in range(positionNum)] + ['']
else: # last line or the line only has one word
spaces = [' '] * positionNum + [' ' * (maxWidth - currWidth)]

result.append(''.join([s for pair in zip(oneLine, spaces) for s in pair]))
return result

##### Complexity
• Time: $$O(n^2)$$
• Space: $$O(n)$$

#### Solution: Loop over once and adjust spacing

• We’ll build the result array line-by-line while iterating over words in the input. Whenever the current line gets too big, we’ll appropriately format it and proceed with the next line until for loop is over. Last but not least, we’ll need to left-justify the last line.
class Solution:
# Why slots: https://docs.python.org/3/reference/datamodel.html#slots
# TLDR: 1. faster attribute access. 2. space savings in memory.
# For letcode problems this can save ~ 0.1MB of memory <insert is something meme>
__slots__ = ()

def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
# Init return array in which, we'll store justified lines
lines = []
# current line width
width = 0
# current line words
line = []

for word in words:
# Gather as many words that will fit under maxWidth restrictions.
# Line length is a sum of:
# 1) Current word length
# 2) Sum of words already in the current line
# 3) Number of spaces (each word needs to be separated by at least one space)
if (len(word) + width + len(line)) <= maxWidth:
width += len(word)
line.append(word)
continue

# If the current line only contains one word, fill the remaining string with spaces.
if len(line) == 1:
# Use the format function to fill the remaining string with spaces easily and readable.
# You could also do something like:
#     line = " ".join(line)
#     line += " " * (maxWidth - len(line))
#     lines.append(line)
lines.append(
"{0: <{width}}".format( " ".join(line), width=maxWidth)
)
else:
# Else calculate how many common spaces and extra spaces are there for the current line.
# Example:
#  line = ['a', 'computer.', 'Art', 'is']
# width left in line equals to: maxWidth - width: 20 - 15 = 5
# len(line) - 1 because to the last word, we aren't adding any spaces
# Now divmod will give us how many spaces are for all words and how many extra to distribute.
# divmod(5, 3) = 1, 2
# This means there should be one common space for each word, and for the first two, add one extra space.
space, extra = divmod(
maxWidth - width,
len(line) - 1
)

i = 0
# Distribute extra spaces first
# There cannot be a case where extra spaces count is greater or equal to number words in the current line.
while extra > 0:
line[i] += " "
extra -= 1
i += 1

# Join line array into a string by common spaces, and append to justified lines.
lines.append(
(" " * space).join(line)
)

# Create new line array with the current word in iteration, and reset current line width as well.
line = [word]
width = len(word)

# Last but not least format last line to be left-justified with no extra space inserted between words.
# No matter the input, there always be the last line at the end of for loop, which makes things even easier considering the requirement.
lines.append(
"{0: <{width}}".format(" ".join(line), width=maxWidth)
)

return lines

##### Complexity
• Time: $$O(n)$$ since there is just one for loop, which iterates over words provided as input.
• Space: $$O(n + l)$$ where $$n$$ is the length of words, and $$l$$ max length of words in one line. Worst case scenario $$l = n$$, which will add up to $$O(2n)$$ but in asymptotic analysis we don’t care about constants so final complexity is still linear.

### [50/Medium] Pow(x, n)

#### Problem

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

• Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

• Example 2:
Input: x = 2.10000, n = 3
Output: 9.26100

• Example 3:
Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

• Constraints:
• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• See problem on LeetCode.

#### Solution: Use “**”

class Solution:
myPow = pow

• That’s even shorter than the other more obvious “cheat”:
class Solution:
def myPow(self, x: float, n: int) -> float:
return x ** n


#### Solution: Recursion

class Solution:
def myPow(self, x: float, n: int) -> float:
if not n:
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)


#### Solution: Iteration

class Solution:
def myPow(self, x: float, n: int) -> float:
if n < 0:
x = 1 / x
n = -n
pow = 1
while n:
if n & 1:
pow *= x
x *= x
n >>= 1
return pow

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [53/Easy] Maximum Subarray

#### Problem

• Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

• A subarray is a contiguous part of an array.

• Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

• Example 2:
Input: nums = [1]
Output: 1

• Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23

• Constraints:
• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• See problem on LeetCode.

class Solution:
def maxSubArray(self, A):
"""
@param A, a list of integers
@return an integer
"""

# not needed if the question says that the array should have at least one number.
if not A:
return 0

curSum = maxSum = A[0]
for num in A[1:]:
# Check if we should abandon the accumulated value so far
# and start a new run of numbers if the previous sum is negative
curSum = max(num, curSum + num) # or curSum = max(curSum, 0) + num

# Update answer if current sum is better than the previous one
maxSum = max(maxSum, curSum)

return maxSum

• Same approach; rephrased longer answer:
class Solution(object):
def maxSubArray(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
max_so_far = curr_so_far = -float('inf')
for i in range(len(nums)):
curr_so_far += nums[i] # Add current number

# Check if we should abandon the accumulated value so far
# and start a new run of numbers if the previous sum is negative
curr_so_far = max(curr_so_far, nums[i])

max_so_far = max(max_so_far, curr_so_far)

return max_so_far

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [54/Medium] Spiral Matrix

#### Problem

• Given an m x n matrix, return all elements of the matrix in spiral order.

• Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

• Example 2:

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

• Constraints:
• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 10
• -100 <= matrix[i][j] <= 100
• See problem on LeetCode.
##### Solution: Recursion
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
"""
:type matrix: List[List[int]]
:rtype: List[int]
"""
if len(matrix) == 0:
return []

new_matrix = []
for j in range(len(matrix[0])-1, -1, -1):
new_lst = []

for i in range(1, len(matrix)):
new_lst.append(matrix[i][j])

new_matrix.append(new_lst)

return matrix[0] + self.spiralOrder(new_matrix)

##### Solution: One-liner
• Take the first row plus the spiral order of the rotated remaining matrix.
def spiralOrder(self, matrix):
return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1])

##### Solution
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
height = len(matrix)
width = len(matrix[0])

top = 0
bottom = height - 1
left = 0
right = width - 1

ans = []
while top < bottom and left < right:
for col in range(left, right):
ans.append(matrix[top][col])

for row in range(top, bottom):
ans.append(matrix[row][right])

for col in range(right, left, -1):
ans.append(matrix[bottom][col])

for row in range(bottom, top, -1):
ans.append(matrix[row][left])

top += 1
bottom -= 1
left += 1
right -= 1

# If a matrix remain inside it is either a 1xn or a mx1
# a linear scan will return the same order as spiral for these
if len(ans) < height*width:
for row in range(top, bottom+1):
for col in range(left, right+1):
ans.append(matrix[row][col])

return ans

• Here are 3 examples:
Example 1: row remains in middle
[1,2,3,4]
[5,6,7,8]
[9,0,1,2]
The bottom nested for loops will traverse (in-order): 6,7

Example 2: Single element remains in middle
[1,2,3]
[4,5,6]
[7,8,9]
The bottom nested for loops will traverse (in-order): 5

Example C: Column remains in middle
[1,2,3]
[4,5,6]
[7,8,9]
[0,1,2]
The bottom nested for loops will traverse (in-order): 5,8

• Same approach; no need to handle edge cases with this solution. We already know the length of our result list should be length of m*n. So, just ignore the redundant elements and return res[:m*n].
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
left, right, top, bottom = 0, n - 1, 0, m - 1
res = []

while left <= right and top <= bottom:
# top left to top right
for col in range(left, right+1):
res.append(matrix[top][col])
top += 1

# top right to right bottom
for row in range(top, bottom+1):
res.append(matrix[row][right])
right -= 1

# right bottom to right left
for col in range(right, left-1, -1):
res.append(matrix[bottom][col])
bottom -= 1

# left bottom to top left
for row in range(bottom, top-1, -1):
res.append(matrix[row][left])
left += 1

# just ignore the redundant and return length of m*n
return res[:m*n]

• Same approach (but with if-conditions so don’t have to restrict the length of res when returning):
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
left, right, top, bottom = 0, n - 1, 0, m - 1
res = []

while left <= right and top <= bottom:
# top left to top right
for col in range(left, right+1):
res.append(matrix[top][col])
top += 1

# top right to right bottom
for row in range(top, bottom+1):
res.append(matrix[row][right])
right -= 1

if (top <= bottom):
# right bottom to right left
for col in range(right, left-1, -1):
res.append(matrix[bottom][col])
bottom -= 1

if (left <= right):
# left bottom to top left
for row in range(bottom, top-1, -1):
res.append(matrix[row][left])
left += 1

# just ignore the redundant and return length of m*n
return res

class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m , n = len(matrix), len(matrix[0])
#refers to row as row can only move up or down
topBound , bottomBound = 0, m-1
#refers to cols as cols can only move right or left
leftBound, rightBound = 0, n-1

res = []
size = m*n

# we iterate until we have gone over all elements
while len(res) < size:
# we iterate until we have found the center
# or while leftBound <= rightBound and topBound <= bottomBound:
# runs through the first row straight through each col
if topBound <= bottomBound:
for col in range(leftBound, rightBound+1):
res.append(matrix[topBound][col])
topBound += 1

# next runs down the column
if leftBound <= rightBound:
for row in range(topBound, bottomBound+1):
res.append(matrix[row][rightBound])
rightBound -= 1

# goes right to left in col
if topBound <= bottomBound:
for col in range(rightBound, leftBound -1, -1):
res.append(matrix[bottomBound][col])
bottomBound -= 1

# goes up
if leftBound <= rightBound:
for row in range(bottomBound, topBound-1, -1):
res.append(matrix[row][leftBound])
leftBound += 1

return res

• Note that the if conditions are the “key” concept. This prevents the double counting, especially for cases where the middle most is “horizontal” or “vertical”:
1 2 3 4     or        1 2 3     or     1 2 3
5 * * 7               4 * 5            4 * 4
7 7 7 7               4 4 4            4 * 4
4 * 4
3 3 3

##### Complexity
• Time: $$O(H*W)$$ since we traverse all elements in the matrix to be able to return them.
• Space: $$O(H*W)$$ due to the size of the output variable (which is as large as the input matrix). If you don’t consider output variable size in your analysis then: $$O(1)$$ space.

### [56/Medium] Merge intervals

#### Problem

• Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

• Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

• Example 2:
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

• Constraints:
• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 104
• See problem on LeetCode.

#### Solution: sort first, then compare the start of the current interval with the end of the prior interval

class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
out = []
for i in sorted(intervals, key=lambda i: i[0]):
# or for i in sorted(intervals, key=lambda i: i.start):
if out and i[0] <= out[-1][1]:
# or if out and i.start <= out[-1].end:
out[-1][1] = max(out[-1][1], i[1])
# or out[-1].end = max(out[-1].end, i.end)
else:
out += i, # Note that "i," is a tuple (because of the comma), and you can extend a tuple to a list (using "+=").
# or out += [i]
return out

##### Complexity
• Time: $$O(n\log{n} + n) = O(n\log{n})$$
• Space: $$O(n)$$

### [57/Medium] Insert Interval

#### Problem

• You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the i-th interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.
• Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
• Return intervals after the insertion.

• Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

• Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

• Constraints:
• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 105
• intervals is sorted by start_i in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105
• See problem on LeetCode.

#### Solution: sort first, then compare the start of the current interval with the end of the prior interval

• First, append the new interval to the intervals list, then follow the same idea as Merge Intervals.
class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.append(newInterval)
out = []

for i in sorted(intervals, key=lambda i: i[0]):
# or for i in sorted(intervals, key=lambda i: i.start):
if out and i[0] <= out[-1][1]:
# or if out and i.start <= out[-1].end:
out[-1][1] = max(out[-1][1], i[1])
# or out[-1].end = max(out[-1].end, i.end)
else:
out += i, # Note that "i," is a tuple (because of the comma), and you can extend an iterable to a list (using "+=").
# or out += [i] or simply out.append(i)
return out

##### Complexity
• Time: $$O(n\log{n} + n) = O(n\log{n})$$
• Space: $$O(n)$$

#### Solution: makes use of the property that the intervals were initially sorted according to their start times

class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
result = []

for interval in intervals:
# the start of the new interval is after the end of the current interval, so we can leave the current interval because the new one does not overlap with it
if newInterval[0] > interval[1]:
result.append(interval)

# the start of the current interval is after the end of the new interval, so we can add the new interval and update it to the current one
elif interval[0] > newInterval[1]:
result.append(newInterval)
newInterval = interval

# the new interval is in the range of the other interval, we have an overlap, so we must choose the min for start and max for end of interval
elif interval[1] >= newInterval[0] or interval[0] <= newInterval[1]:
newInterval[0] = min(interval[0], newInterval[0])
newInterval[1] = max(newInterval[1], interval[1])

result.append(newInterval);
return result

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$

### [62/Medium] Unique Paths

#### Problem

• There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
• Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
• The test cases are generated so that the answer will be less than or equal to 2 * 10^9.

• Example 1:

Input: m = 3, n = 7
Output: 28

• Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

• Constraints:
• 1 <= m, n <= 100
• See problem on LeetCode.

#### Solution: Recursion

• Since robot can move either down or right, there is only one path to reach the cells in the first row: right->right->...->right.

• The same is valid for the first column, though the path here is down->down-> ...->down.

• What about the “inner” cells (m, n)? To such cell one could move either from the cell on the left (m, n - 1), or from the cell above (m - 1, n). That means that the total number of paths to move into (m, n) cell is uniquePaths(m - 1, n) + uniquePaths(m, n - 1).

class Solution:
def uniquePaths(self, m: int, n: int) -> int:
if m == 1 or n == 1:
return 1

return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)


#### Solution: Dynamic Programming

• One could rewrite recursive approach into dynamic programming one.
• Algorithm:
• Initiate 2D array d[m][n] = number of paths. To start, put number of paths equal to 1 for the first row and the first column. For the simplicity, one could initiate the whole 2D array by ones.
• Iterate over all “inner” cells: d[col][row] = d[col - 1][row] + d[col][row - 1].
• Return d[m - 1][n - 1].
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
"""
dp[i][j] = number of ways to reach i,j
dp[0][j] = 1, since this is the top row. To reach any element
in the top row, we can only move right, so there is only 1 way.
Similarly, dp[i][0] = 1.
dp[i][j] = num ways to reach one left + num ways to reach one above
= (number of ways to reach i, j-1) + (num ways to reach i-1, j)
= dp[i][j-1] + dp[i-1][j]
"""

d = [[1] * n for _ in range(m)]

for col in range(1, m):
for row in range(1, n):
# The robot can only move either down or right at any point in time.
# so to get to [col][row], you have to look at the previous column (left), i.e., [col - 1][row]
# and the previous row (top), i.e., [col][row - 1]
d[col][row] = d[col - 1][row] + d[col][row - 1]

return d[m - 1][n - 1]


#### Complexity

• Time: $$\mathcal{O}(n \times m)$$
• Space: $$\mathcal{O}(n \times m)$$

#### Solution: Combination

• Could one do better than $$\mathcal{O}(n \times m)$$? The answer is yes.

• The problem is a classical combinatorial problem: there are $$h + v$$ moves to do from start to finish, $$h = m - 1$$ horizontal moves, and $$v = n - 1$$ vertical ones. One could choose when to move to the right, i.e. to define $$h$$ horizontal moves, and that will fix vertical ones. Or, one could choose when to move down, i.e., to define $$v$$ vertical moves, and that will fix horizontal ones.

• In other words, we’re asked to compute in how many ways one could choose $$p$$ elements from $$p + k$$ elements. In mathematics, that’s called binomial coefficients
$C_{h + v}^{h} = C_{h + v}^{v} = \frac{(h + v)!}{h! v!}$
• The number of horizontal moves to do is $$h = m - 1$$, the number of vertical moves is $$v = n - 1$$. That results in a simple formula
$C_{h + v}^{h} = \frac{(m + n - 2)!}{(m - 1)! (n - 1)!}$
• The job is done. Now time complexity will depend on the algorithm to compute factorial function $$(m + n - 2)!$$. In short, standard computation for k!k! using the definition requires $$\mathcal{O}(k^2 \log k)$$ time, and that will be not as good as DP algorithm.
• The best known algorithm to compute factorial function is done by Peter Borwein. The idea is to express the factorial as a product of prime powers, so that $$k!$$ can be computed in $$\mathcal{O}(k (\log k \log \log k)^2)$$ time. That’s better than $$\mathcal{O}(k^2)$$ and hence beats DP algorithm.
• The authors prefer not to discuss here various factorial function implementations, and hence provide Python3 solution only, with built-in divide and conquer factorial algorithm. If you’re interested in factorial algorithms, please check out good review on this page.
class Solution:
def combination_solution():
###################################
# Solution 2: combination         #
###################################
"""
Total path length is (m-1) + (n-1).
Consider the list of moves for a single path:
[down, right, down, down, right, ...]
We choose m-1 of these to be down (or choose n-1 of these to be right).
"""
def choose(n, r):
return int(math.factorial(n) / (math.factorial(r) * math.factorial(n-r)))
return choose(m+n-2, m-1)


#### Complexity

• Time: $$\mathcal{O}((m + n) (\log (m + n) \log \log (m + n))^2)$$
• Space: $$\mathcal{O}(1)$$

### [65/Hard] Valid number

#### Problem

• A valid number can be split up into these components (in order):
• A decimal number or an integer.
• (Optional) An e or E, followed by an integer.
• A decimal number can be split up into these components (in order):
• (Optional) A sign character (either + or -).
• One of the following formats:
• One or more digits, followed by a dot ..
• One or more digits, followed by a dot ., followed by one or more digits.
• A dot ., followed by one or more digits.
• An integer can be split up into these components (in order):
• (Optional) A sign character (either + or -).
• One or more digits.
• For example, all the following are valid numbers: ["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"], while the following are not valid numbers: ["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"].
• Given a string s, return true if s is a valid number.

• Example 1:
Input: s = "0"
Output: true

• Example 2:
Input: s = "e"
Output: false

• Example 3:
Input: s = "."
Output: false

• Constraints:
• 1 <= s.length <= 20
• s consists of only English letters (both uppercase and lowercase), digits (0-9), plus +, minus -, or dot ..
• See problem on LeetCode.

#### Solution

• To solve this problem, we should should just make a list of the possible error conditions and then check for each one.
• The error conditions are:
• More than one exponent character (e/E), or seeing an e/E when a number has not yet been seen.
• More than one sign, or a sign appearing after a decimal or number have been seen. This gets reset when passing an e/E.
• More than one decimal, or a decimal appearing after an e/E has been seen.
• Any other non-number character appearing.
• Reaching the end of S without an active number.
• To help with this process, we can set up some boolean flags for the different things of which we’re keeping track (num, exp, sign, dec). We’ll also need to remember to reset all flags except exp when we find an e/E, as we’re starting a new integer expression.

#### Solution: Rule-based

• Method 1:
class Solution:
def isNumber(self, s: str) -> bool:
num, exp, sign, dec = False, False, False, False

for c in s:
if c >= '0' and c <= '9': num = True
elif c == 'e' or c == 'E':
if exp or not num: return False
else: exp, num, sign, dec = True, False, False, False
elif c == '+' or c == '-':
if sign or num or dec: return False
else: sign = True
elif c == '.':
if dec or exp: return False
else: dec = True
else: return False

return num

• Method 2 (check for seenDigit, seenExponent and seenDot):
class Solution:
def isNumber(self, s: str) -> bool:
seenDigit = seenExponent = seenDot = False

for i, c in enumerate(s):
if c.isdigit():
seenDigit = True
elif c in ["+", "-"]:
if i > 0 and s[i-1] != "e" and s[i-1] != "E":
return False
elif c in ["e", "E"]:
if seenExponent or not seenDigit:
return False
seenExponent = True
seenDigit = False
elif c == ".":
if seenDot or seenExponent:
return False
seenDot = True
else:
return False

return seenDigit

##### Complexity
• Time: $$O(n)$$ where $$n$$ is the number of characters in the input string, i.e., n = len(s).
• Space: $$O(1)$$

#### Solution: Use a RegEx

class Solution:
def isNumber(self, s: str) -> bool:
# Example:               +-     1 or 1. or 1.2 or .2   e or E +- 1

### [1662/Easy] Check If Two String Arrays are Equivalent

#### Problem

• Given two string arrays word1 and word2, return true if the two arrays represent the same string, and false otherwise.

• A string is represented by an array if the array elements concatenated in order forms the string.

• Example 1:

Input: word1 = ["ab", "c"], word2 = ["a", "bc"]
Output: true
Explanation:
word1 represents string "ab" + "c" -> "abc"
word2 represents string "a" + "bc" -> "abc"
The strings are the same, so return true.

• Example 2:
Input: word1 = ["a", "cb"], word2 = ["ab", "c"]
Output: false

• Example 3:
Input: word1  = ["abc", "d", "defg"], word2 = ["abcddefg"]
Output: true

• Constraints:
• 1 <= word1.length, word2.length <= 103
• 1 <= word1[i].length, word2[i].length <= 103
• 1 <= sum(word1[i].length), sum(word2[i].length) <= 103
• word1[i] and word2[i] consist of lowercase letters.
• See problem on LeetCode.

#### Solution: Use ''.join()

class Solution:
def arrayStringsAreEqual(self, word1: List[str], word2: List[str]) -> bool:
return "".join(word1) == "".join(word2)

##### Complexity
• Time: $$O(max(n,m)$$ where $$n$$ and $$m$$ are the lengths of word1 and word2 respectively

### [1641/Medium] Count Sorted Vowel Strings

#### Problem

• Given an integer n, return the number of strings of length n that consist only of vowels (a, e, i, o, u) and are lexicographically sorted.
• A string s is lexicographically sorted if for all valid i, s[i] is the same as or comes before s[i+1] in the alphabet.

• Example 1:
Input: n = 1
Output: 5
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].

• Example 2:
Input: n = 2
Output: 15
Explanation: The 15 sorted strings that consist of vowels only are
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.

• Example 3:
Input: n = 33
Output: 66045

• Constraints:
• 1 <= n <= 50
• See problem on LeetCode.

#### Solution: Brute Force Using Backtracking

• Intuition:
• Backtracking is a general approach that works by identifying potential candidates and incrementally builds the solution using depth first search. Once the required goal is reached, we backtrack to explore another potential candidate.
• The backtracking solution for the given problem would be, to begin with, the first vowel character, continue using the same vowel until we build a string of length $$n$$. Post that, backtrack and use the next character.
• As we are picking up each vowel character in alphabetically sorted order (first a, then e, then i, and so on), we know that the resultant string is always lexicographically sorted.
• Example, For n = 3, pick the first vowel a, continue picking up the same vowel until we reach $$n$$. The resultant string would be aaa. Now that we have found our first combination, backtrack and pick up the next character e. Our next string would be aae. The process continues until all the vowel characters are explored.
• Algorithm:
• As we start with the first vowel a then e and so on, we need a way to determine the current vowel in a recursive function. We use an integer variable vowel for that purpose, where 1 denotes a, 2 denotes e, and so on.
• We begin with $$n$$ positions and first vowel a(1) and use method countVowelStringUtil to recursively compute all the combinations.
• On every recursion, we decrement n by 1 as we have used up that position and continue passing the same vowel. On the backtrack, we move on to the next vowel.
• Base Case:
• If n = 0, we have reached the end of the string and found one combination. Hence, we return 1 and backtrack.
• We try all the possibilities where adding the new vowel doesn’t break the lexicographic order. For example, if the last character of our actual possibility is ‘e’, we can’t add an ‘a’ after it.
def count(n, last=''):
if n == 0:
return 1
else:
nb = 0
for vowel in ['a', 'e', 'i', 'o', 'u']:
if last <= vowel:
nb += count(n-1, vowel)
return nb

##### Complexity
• Time: $$\mathcal{O}(n^{5})$$. We have to calculate the size of the recursion tree. Let’s analyze the number of nodes generated at each level. The following figure illustrates the number of enumerations at level 2.

• Space: $$\mathcal{O}(n)$$. This space will be used to store the recursion stack. We can’t have more than $$n$$ recursive calls on the call stack at any time.

#### Solution: Recursion + Memoization, Top Down Dynamic Programming

• If you have solved problems on Dynamic Programming before, it is pretty easy to optimize the Approach 2 using Memoization. In the above approach, the problem can be broken down into subproblems. On drawing the recursion tree, it is evident that the same subproblems are computed multiple times.

• In the above recursion tree, we could see that subproblems (2, 4), (2, 3) and (1, 2) are computed multiple times and the result would be always the same. The problem has Overlapping Subproblem and can be solved using Dynamic Programming.

• Algorithm:
• We could have stored the results of our computation for the first time and used it later. This technique of computing once and returning the stored value is called Memoization.
• As we must store results for every $$n$$ and $$\text{vowels}$$, we use a two dimensional array $$\text{memo}$$ of size n x 5 and follow the following steps for each recursive call:
• Check in the memo if we have already calculated results for a given $$n$$ and $$\text{vowels}$$ and return the result stored in the memo.
• Save the results of any calculations to $$\text{memo}$$.

Since arrays are 0-indexed, we initialize the array of size (n + 1, 5 + 1) and use the range 1..n and 1..5 for easier understanding and keeping it consistent with the previous approach.

• Key Insight:
• The fact that we are building strings from vowels really doesn’t matter. What does matter is that we have 5 elements and we want to know how many combinations (with replacement) we can make.
• Approach:
• Each iteration we have 2 choices. Add the current letter to the string or move on to the next letter.
• Once the string is n characters long, return 1 to signify we made 1 string. And if we reach the 6th letter, then return 0 because there are only 5 vowels to choose from so we cannot complete the string.
• Finally as the recursive function unwinds sum up how many strings were made.
@functools.lru_cache(None)

class Solution:
def countVowelStrings(self, n: int) -> int:
def helper(i, j):
if i == 5:
return 0
if j == 0:
return 1
return helper(i+1, j) + helper(i, j-1)
return helper(0, n)

##### Complexity
• Time: $$\mathcal{O}(n)$$, as for every $$n$$ and $$\text{vowels}$$ we calculate result only once, the total number of nodes in the recursion tree would be n x 5, which is roughly equal to $$n$$.
• Space: $$\mathcal{O}(n)$$, as we use a 2D array $$\text{memo}$$ of size n x 5 and the size of internal call stack would also be $$n$$ (As explained in Approach 2), the space complexity would be $$\mathcal{O}(n+n) = \mathcal{O}(n)$$.

#### Solution: One-liner

def countVowelStrings(self, n: int) -> int:
return len(list(itertools.combinations_with_replacement(range(5), n)))


#### Solution: Bottom Up Dynamic Programming, Tabulation

• Intuition:
• This is another approach to solve the Dynamic Programming problems. We use the iterative approach and store the result of subproblems in bottom-up fashion also known as Tabulation. We store the results of previous computations in tabular format and use those results for the next computations.
• Algorithm:
• We maintain a 2D array, dp of size n x 5 where, dp[n][vowels] denotes the total number of combinations for given n and number of \text{vowels}. Using the recurrence relation established in Approach 2, we could iteratively calculate the value for dp[n][vowels] as,
  dp[n][vowels] = dp[n - 1][vowels] + dp[n][vowels - 1]

• As this is the Bottom Up approach to solve the problem, we must initialize the table for the base cases. The base cases are the same as in Approach 2.
• If n = 1, the number of combinations are always equal to number of vowels. Hence, we initialize all the values of dp[1][vowels] with vowels.
• If vowels = 1, the number of combinations are always equal to 1. Hence, we initialize all the values of dp[n][1] with 1.
class Solution:
def countVowelStrings(self, k: int) -> int:
dp = [1] * 5

for _ in range(1, k):
for i in range(1, 5):
dp[i] = dp[i] + dp[i-1]

return sum(dp)

##### Complexity
• Time: $$\mathcal{O}(n)$$, as we iterate 5 x n times to fill the dp array, the time complexity is approximately $$\mathcal{O}(5 \cdot n) =\mathcal{O}(n)$$.
• Space: $$\mathcal{O}(n)$$, as we use a 2D array of size n x 5, the space complexity would be $$\mathcal{O}(n)$$.

#### Solution: Math

• Intuition and Algorithm:
• The problem is a variant of finding Combinations. Mathematically, the problem can be described as, given 5 vowels (let k = 5k=5), we want to find the number of combinations using only nn vowels. Also, we can repeat each of those vowels multiple times.

In other words, from $$k$$ vowels ($$k = 5$$), we can choose $$n$$ vowels with repetition. Denoted as $$\left(\!\!{k \choose n}\!\!\right)$$, the formulae for Combination with Repetition is given by $$\left(\!\!{k \choose n}\!\!\right) = \frac{(k + n - 1)!}{ (k - 1)! n!}$$

• We know that the $$k$$ value is 5 as there are always 5 vowels to choose from. Substituting $$k$$ as 5 in above formulae, $$\left(\!\!{5\choose n}\!\!\right) = \frac{(n+4) \cdot (n+3) \cdot (n+2) \cdot (n+1)}{24}$$
• The derivation can be illustrated as follows.

class Solution:
def countVowelStrings(self, k: int) -> int:
return (k + 4) * (k + 3) * (k + 2) * (k + 1) // 24

##### Complexity
• Time: $$\mathcal{O}(1)$$, as the approach runs in constant time.
• Space: $$\mathcal{O}(1)$$, as the approach uses constant extra space.

### [1678/Easy] Goal Parser Interpretation

#### Problem

• You own a Goal Parser that can interpret a string command. The command consists of an alphabet of “G”, “()” and/or “(al)” in some order. The Goal Parser will interpret “G” as the string “G”, “()” as the string “o”, and “(al)” as the string “al”. The interpreted strings are then concatenated in the original order.

• Given the string command, return the Goal Parser’s interpretation of command.

• Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

• Example 2:
Input: command = "G()()()()(al)"
Output: "Gooooal"

• Example 3:
Input: command = "(al)G(al)()()G"
Output: "alGalooG"

• Constraints:
• 1 <= command.length <= 100
• command consists of "G", "()", and/or "(al)" in some order.
• See problem on LeetCode.

#### Solution: Replace longest substring first, then replace smaller ones

class Solution:
def interpret(self, command: str) -> str:
command = command.replace('()','o')
command = command.replace('(', '')
command = command.replace(')','')

return command

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$ since a new string is created when applying .replace() (as strings are immutable)

### [1732/Easy] Find the Highest Altitude

#### Problem

• There is a biker going on a road trip. The road trip consists of n + 1 points at different altitudes. The biker starts his trip on point 0 with altitude equal 0.

• You are given an integer array gain of length n where gain[i] is the net gain in altitude between points i and i + 1 for all (0 <= i < n). Return the highest altitude of a point.

• Example 1:

Input: gain = [-5,1,5,0,-7]
Output: 1
Explanation: The altitudes are [0,-5,-4,1,1,-6]. The highest is 1.

• Example 2:
Input: gain = [-4,-3,-2,-1,4,3,2]
Output: 0
Explanation: The altitudes are [0,-4,-7,-9,-10,-6,-3,-1]. The highest is 0.

• Constraints:
• n == gain.length
• 1 <= n <= 100
• -100 <= gain[i] <= 100
• See problem on LeetCode.

#### Solution: DP

class Solution:
def largestAltitude(self, gain: List[int]) -> int:
dp = [0] * (len(gain)+1)
dp[0] = 0

for index in range (1, len(gain)+1):
dp[index] = dp[index-1] + gain[index-1]
return max(dp)


#### Solution: Use the gain list for iteration and append the sum of the i-th element of “res” and the i-th element of the “gain” list; then, find the max of the resulting list

class Solution:
def largestAltitude(self, gain: List[int]) -> int:
res = [0]

for i in range(len(gain)):
res.append(res[i] + gain[i])

return max(res)


### [1762/Medium] Buildings With an Ocean View

#### Problem

• There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.
• The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.
• Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

• Example 1:
Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

• Example 2:
Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.

• Example 3:
Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.

• Constraints:
• 1 <= heights.length <= 105
• 1 <= heights[i] <= 109
• See problem on LeetCode.

#### Solution: Reverse traversal and check for height violation

class Solution:
def findBuildings(self, heights: List[int]) -> List[int]:
retList = []
retList.append(len(heights)-1)
maxVal = heights[len(heights)-1]

for index in range(len(heights)-2,-1,-1):
if(heights[index] > maxVal):
maxVal = heights[index]
retList.append(index)

return reversed(retList) # sorted(retList)

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$

### [1650/Medium] Lowest Common Ancestor of a Binary Tree III

• Given two nodes of a binary tree p and q, return their lowest common ancestor (LCA).

• Each node will have a reference to its parent node. The definition for Node is below:

class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}

• According to the definition of LCA on Wikipedia: “The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself).”

• Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

• Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5 since a node can be a descendant of itself according to the LCA definition.

• Example 3:
Input: root = [1,2], p = 1, q = 2
Output: 1

• Constraints:
• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q exist in the tree.
• See problem on LeetCode.

#### Solution: Iteration

• The idea is to store the parents (path) from root to p, and then check q’s path.
"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""

class Solution:
def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
path = set()
while p:
p = p.parent
while q not in path:
q = q.parent
return q


#### Solution: Find depth difference, move pointers to the same level, then move pointers up until they meet

• We first find the depth of each pointer, and then move each pointer to the same level in the tree. Then, we move the pointers up level by level until they meet.
• Summary:
• Find the depth of each pointer.
• Move the deeper pointer up until it is at the same level as the other pointer.
• Move each pointer up level-by-level until they meet
• Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 8
Output: 3


• Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5


"""
# Definition for a Node.
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.parent = None
"""

class Solution:
def get_depth(self, p):
# helper function to find the depth of the pointer in the tree
depth = 0
while p:
p = p.parent
depth += 1
return depth

def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
# find the depth of each pointer
p_depth = self.get_depth(p)
q_depth = self.get_depth(q)

# Move the lower pointer up so that they are each at the same level.
# For the smaller depth (p_depth < q_depth or q_depth < p_depth),
# the loop will be skipped and the pointer will stay at the same depth.
for _ in range(p_depth - q_depth):
p = p.parent
for _ in range(q_depth - p_depth):
q = q.parent

# Now that they are at the same depth, move them up the tree in parallel until they meet
while p != q:
p=p.parent
q=q.parent
return p

##### Complexity
• Time: $$O(h)$$
• Space: $$O(1)$$

#### Solution: Recursion + Set

class Solution(object):
def lowestCommonAncestor(self, p, q):
pVals = set()
def traverse_up(root):
if root == None or root in pVals:
return root
return traverse_up(root.parent)

# This works because None in python evaluates to False, so doing None or Node will return Node.
return traverse_up(p) or traverse_up(q)


### [1887/Medium] Reduction Operations to Make the Array Elements Equal

#### Problem

• Given an integer array nums, your goal is to make all elements in nums equal. To complete one operation, follow these steps:
• Find the largest value in nums. Let its index be i (0-indexed) and its value be largest. If there are multiple elements with the largest value, pick the smallest i.
• Find the next largest value in nums strictly smaller than largest. Let its value be nextLargest.
• Reduce nums[i] to nextLargest.
• Return the number of operations to make all elements in nums equal.

• Example 1:
Input: nums = [5,1,3]
Output: 3
Explanation: It takes 3 operations to make all elements in nums equal:
1. largest = 5 at index 0. nextLargest = 3. Reduce nums[0] to 3. nums = [3,1,3].
2. largest = 3 at index 0. nextLargest = 1. Reduce nums[0] to 1. nums = [1,1,3].
3. largest = 3 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1].

• Example 2:
Input: nums = [1,1,1]
Output: 0
Explanation: All elements in nums are already equal.

• Example 3:
Input: nums = [1,1,2,2,3]
Output: 4
Explanation: It takes 4 operations to make all elements in nums equal:
1. largest = 3 at index 4. nextLargest = 2. Reduce nums[4] to 2. nums = [1,1,2,2,2].
2. largest = 2 at index 2. nextLargest = 1. Reduce nums[2] to 1. nums = [1,1,1,2,2].
3. largest = 2 at index 3. nextLargest = 1. Reduce nums[3] to 1. nums = [1,1,1,1,2].
4. largest = 2 at index 4. nextLargest = 1. Reduce nums[4] to 1. nums = [1,1,1,1,1].

• Constraints:
• 1 <= nums.length <= 5 * 104
• 1 <= nums[i] <= 5 * 104
• See problem on LeetCode.

#### Solution: Sort counter in descending order and build result by adding frequencies

• Algorithm:
• Go through numbers and their counts in decreasing order of frequencies.
• We keep track of remaining numbers we need to change in each iteration and add it to our result res.
• Explanation:
• sorted(Counter(nums).items(), reverse=True) gives items and their counts in reverse order
• We are doing items() instead of just taking values() as we want to order the elements in dictionary by the keys and not values.
• Example:
• Let’s take a look at [1, 2, 2, 5, 5, 43].
• We look at 43 and add 1 to to_change (as one of 43 needs to be changed to next number).
• We look at 5 and add to_change to result (changing 43 to 5), and add two 5’s, which is new_elements to to_change. At this stage, we have to_change = 3.
• We do so until the end when we are at 1, and we end up adding remaining 2’s to the result. Note that we drop the last new_elements for 1’s (since it doesn’t reflect in res).
class Solution:
def reductionOperations(self, nums: List[int]) -> int:
res = to_change = 0

for _, new_elements in sorted(Counter(nums).items(), reverse=True):
res += to_change
to_change += new_elements

return res

##### Complexity
• Time: $$O(n\log{n})$$ owing to the sort
• Space: $$O(n)$$ for storing the counts

#### Solution: Derive count add n-1-i

• First sort nums, then go from left to right, if a mismatch is found at index i, i.e. nums[i] != nums[i+1], then add n-1-i to the result.

class Solution:
def reductionOperations(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
count = 0

for i in range(n-1):
if nums[i] != nums[i+1]:
count += n-1-i

return count

##### Complexity
• Time: $$O(n\log{n})$$ owing to the sort + $$O(n)$$ owing to nums traversal = $$O(n\log{n})$$
• Space: $$O(1)$$

#### Solution: One-liner

• Same approach as above. First sort nums, then go from left to right, if a mismatch is found at index i, i.e. nums[i-1] != nums[i], then add n-i to the result.
class Solution:
def reductionOperations(self, nums: List[int]) -> int:
nums, n = sorted(nums), len(nums)
return sum([n-i if nums[i-1] != nums[i] else 0 for i in range(1, n)])

##### Complexity
• Time: $$O(n\log{n})$$ owing to the sort + $$O(n)$$ owing to nums traversal = $$O(n\log{n})$$
• Space: $$O(1)$$

### [1911/Medium] Maximum Alternating Subsequence Sum

#### Problem

• The alternating sum of a 0-indexed array is defined as the sum of the elements at even indices minus the sum of the elements at odd indices.
• For example, the alternating sum of [4,2,5,3] is (4 + 5) - (2 + 3) = 4.
• Given an array nums, return the maximum alternating sum of any subsequence of nums (after reindexing the elements of the subsequence).
• A subsequence of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements’ relative order. For example, [2,7,4] is a subsequence of [4,2,3,7,2,1,4] (the underlined elements), while [2,4,2] is not.
• Example 1:
Input: nums = [4,2,5,3]
Output: 7
Explanation: It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) - 2 = 7.

• Example 2:
Input: nums = [5,6,7,8]
Output: 8
Explanation: It is optimal to choose the subsequence [8] with alternating sum 8.

• Example 3:
Input: nums = [6,2,1,2,4,5]
Output: 10
Explanation: It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) - 1 = 10.

• Constraints:
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• See problem on LeetCode.

#### Solution: Add and subtract current number from max count

def maxAlternatingSum(self, A):
odd = even = 0
for a in A:
odd, even = [max(odd, even - a), max(even, odd + a)]
return even

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [1920/Easy] Build Array from Permutation

#### Problem

• Given a zero-based permutation nums (0-indexed), build an array ans of the same length where ans[i] = nums[nums[i]] for each 0 <= i < nums.length and return it.

• A zero-based permutation nums is an array of distinct integers from 0 to nums.length - 1 (inclusive).

• Example 1:

Input: nums = [0,2,1,5,3,4]
Output: [0,1,2,4,5,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
= [0,1,2,4,5,3]

• Example 2:
Input: nums = [5,0,1,2,3,4]
Output: [4,5,0,1,2,3]
Explanation: The array ans is built as follows:
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
= [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
= [4,5,0,1,2,3]

• Constraints:
• 1 <= nums.length <= 1000
• 0 <= nums[i] < nums.length
• The elements in nums are distinct.
• Follow-up: Can you solve it without using an extra space (i.e., O(1) memory)?

• See problem on LeetCode.

#### Solution: Simple list comprehension

class Solution:
def buildArray(self, nums: List[int]) -> List[int]:
return [nums[i] for i in nums]

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$

#### Solution: Simple list comprehension

def buildArray(self, nums: List[int]) -> List[int]:
n = len(nums);

for i in range(n):
nums[i] += n*(nums[nums[i]]%n)

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

return nums

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [2042/Easy] Check if Numbers Are Ascending in a Sentence

#### Problem

• A sentence is a list of tokens separated by a single space with no leading or trailing spaces. Every token is either a positive number consisting of digits 0-9 with no leading zeros, or a word consisting of lowercase English letters.
• For example, "a puppy has 2 eyes 4 legs" is a sentence with seven tokens: "2" and "4" are numbers and the other tokens such as "puppy" are words.
• Given a string s representing a sentence, you need to check if all the numbers in s are strictly increasing from left to right (i.e., other than the last number, each number is strictly smaller than the number on its right in s).
• Return True if so, or False otherwise.

• Example 1:

Input: s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
Output: true
Explanation: The numbers in s are: 1, 3, 4, 6, 12.
They are strictly increasing from left to right: 1 < 3 < 4 < 6 < 12.

• Example 2:
Input: s = "hello world 5 x 5"
Output: false
Explanation: The numbers in s are: 5, 5. They are not strictly increasing.

• Example 3:

Input: s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
Output: false
Explanation: The numbers in s are: 7, 51, 50, 60. They are not strictly increasing.

• Constraints:
• 3 <= s.length <= 200
• s consists of lowercase English letters, spaces, and digits from 0 to 9, inclusive.
• The number of tokens in s is between 2 and 100, inclusive.
• The tokens in s are separated by a single space.
• There are at least two numbers in s.
• Each number in s is a positive number less than 100, with no leading zeros.
• s contains no leading or trailing spaces.
• See problem on LeetCode.

#### Solution: Split the string, find numbers, check if current number is greater than previous

class Solution:
def areNumbersAscending(self, s: str) -> bool:
words = s.split(" ")
prev = 0

for word in words:
if word.isnumeric(): # or word.isdigit()
# https://datagy.io/python-isdigit
if int(word) <= prev:
return False
prev = int(word)

return True

##### Complexity
• Time: $$O(n)$$
• Space: $$O(n)$$ for words

#### Solution: One-liner

class Solution:
def areNumbersAscending(self, s: str) -> bool:
num = [int(i) for i in s.split() if i.isnumeric()]

#check if in ascending order and unique
return True if num == sorted(num) and len(num)==len(set(num)) else False

##### Complexity
• Time: $$O(n\log{n})$$ due to sorting
• Space: $$O(n)$$

#### Solution: Accumulate digits of every number, check if current number is greater than previous

class Solution:
def areNumbersAscending(self, s: str) -> bool:
prev = -1
curr = -1
temp = []

for ch in s:
if ch.isdigit(): # or ord(character) >= 48 and ord(character) <= 57:
# accumulate all the digits of the number
temp.append(ch)
# the below else is reached when we've accumulated all the digits number
else:
if len(temp) > 0:
curr = int("".join(temp))

if curr <= prev:
return False
else:
prev = curr

temp.clear() # or temp = []

# check the last number
if len(temp) > 0 and int("".join(temp)) <= prev:
return False

return True

##### Complexity
• Time: $$O(n)$$
• Space: $$O(1)$$

### [2060/Hard] Check if an Original String Exists Given Two Encoded Strings

#### Problem

• An original string, consisting of lowercase English letters, can be encoded by the following steps:

• Arbitrarily split it into a sequence of some number of non-empty substrings.
• Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string).
• Concatenate the sequence as the encoded string.
• For example, one way to encode an original string “abcdefghijklmnop” might be:

• Split it as a sequence: ["ab", "cdefghijklmn", "o", "p"].
• Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes ["ab", "12", "1", "p"].
• Concatenate the elements of the sequence to get the encoded string: “ab121p”.
• Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false.

• Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

• Example 1:
Input: s1 = "internationalization", s2 = "i18n"
Output: true
Explanation: It is possible that "internationalization" was the original string.
- "internationalization"
-> Split:       ["internationalization"]
-> Do not replace any element
-> Concatenate:  "internationalization", which is s1.
- "internationalization"
-> Split:       ["i", "nternationalizatio", "n"]
-> Replace:     ["i", "18",                 "n"]
-> Concatenate:  "i18n", which is s2

• Example 2:
Input: s1 = "l123e", s2 = "44"
Output: true
Explanation: It is possible that "leetcode" was the original string.
- "leetcode"
-> Split:      ["l", "e", "et", "cod", "e"]
-> Replace:    ["l", "1", "2",  "3",   "e"]
-> Concatenate: "l123e", which is s1.
- "leetcode"
-> Split:      ["leet", "code"]
-> Replace:    ["4",    "4"]
-> Concatenate: "44", which is s2.

• Example 3:
Input: s1 = "a5b", s2 = "c5b"
Output: false
Explanation: It is impossible.
- The original string encoded as s1 must start with the letter 'a'.
- The original string encoded as s2 must start with the letter 'c'.

• Constraints:
• 1 <= s1.length, s2.length <= 40
• s1 and s2 consist of digits 1-9 (inclusive), and lowercase English letters only.
• The number of consecutive digits in s1 and s2 does not exceed 3.
• See problem on LeetCode.

#### Solution: Top-down DP

• Preliminaries:
• To get the ending index of the numeric substring of ‘s’ starting at ‘start’; we use the following code:-
  def getValidPrefixLength(s,start):
end = start
while end < len(s) and s[end].isdigit(): end += 1
return end

• To get all possibles lengths that the numeric substrings ‘s’ could represent we use the following code:-
  @lru_cache(None)
def possibleLengths(s):
"""Return all possible lengths represented by numeric string s."""
lengths = {int(s)}
for i in range(1, len(s)):
# add all lengths by splitting numeric string s at index i
# & sum of first split part(i.e. x) and second split part(i.e. y) gives the answer
lengths |= {x+y for x in possibleLengths(s[:i]) for y in possibleLengths(s[i:])}
return length

• Main logic:
• The main logic is implement a top-down dynamic programming based approach that takes in current pointers of both strings s1 and s2 as well as the amount of prefix length lead that s2 has over s1. We consider six cases in the DP in the following order:
1. both have reached end,
2. s1 has not reached end and s1 has numeric prefix,
3. s2 has not reached end and s2 has numeric prefix,
4. There is no prefix lead difference between s1 and s2,
5. s2 leads over s1,
6. s1 leads over s2.
• Below is the self-explanatory commented code telling how these cases are implemented:
@lru_cache(None)
def dp(i, j, diff):
"""Return True if s1[i:] matches s2[j:] with given differences."""

# If both have reached end return true if none of them are leading
if i == len(s1) and j == len(s2): return diff == 0

# s1 has not reached end and s1 starts with a digit
if i < len(s1) and s1[i].isdigit():
i2 = getValidPrefixLength(s1,i)
for L in possibleLengths(s1[i:i2]):
# substract since lead of s2  decreases by L
if dp(i2, j, diff-L): return True

# s2 has not reached end and s2 starts with a digit
elif j < len(s2) and s2[j].isdigit():
j2 = getValidPrefixLength(s2,j)
for L in possibleLengths(s2[j:j2]):
if dp(i, j2, diff+L): return True

# if none of them have integer prefix or a lead over the other
elif diff == 0:
# if only one of them has reached end or current alphabets are not the same
if i == len(s1) or j == len(s2) or s1[i] != s2[j]: return False
# skip same alphabets
return dp(i+1, j+1, 0)

# if none of them have integer prefix & s2 lead over s1
elif diff > 0:
# no s1 to balance s2's lead
if i == len(s1): return False
# move s1 pointer forward and reduce diff
return dp(i+1, j, diff-1)

# if none of them have integer prefix & s1 lead over s2
else:
# no s2 to balance s1's lead
if j == len(s2): return False
# move s2 pointer forward and increase diff
return dp(i, j+1, diff+1)

• Finally, we call the function as dp(0, 0, 0). The main code is:
from functools import lru_cache
class Solution:
def possiblyEquals(self, s1: str, s2: str) -> bool:

def getValidPrefixLength(s,start):
end = start
while end < len(s) and s[end].isdigit(): end += 1
return end

@lru_cache(None)
def possibleLengths(s):
"""Return all possible lengths represented by numeric string s."""
ans = {int(s)}
for i in range(1, len(s)):
# add all lengths by splitting numeric string s at i
ans |= {x+y for x in possibleLengths(s[:i]) for y in possibleLengths(s[i:])}
return ans

@lru_cache(None)
def dp(i, j, diff):
"""Return True if s1[i:] matches s2[j:] with given differences."""

# If both have reached end return true if none of them are leading
if i == len(s1) and j == len(s2): return diff == 0

# s1 has not reached end and s1 starts with a digit
if i < len(s1) and s1[i].isdigit():
i2 = getValidPrefixLength(s1,i)
for L in possibleLengths(s1[i:i2]):
# subtract since lead of s2  decreases by L
if dp(i2, j, diff-L): return True

# s2 has not reached end and s2 starts with a digit
elif j < len(s2) and s2[j].isdigit():
j2 = getValidPrefixLength(s2,j)
for L in possibleLengths(s2[j:j2]):
if dp(i, j2, diff+L): return True

# if none of them have integer prefix or a lead over the other
elif diff == 0:
# if only one of them has reached end or current alphabets are not the same
if i == len(s1) or j == len(s2) or s1[i] != s2[j]: return False
# skip same alphabets
return dp(i+1, j+1, 0)

# if none of them have integer prefix and s2 lead over s1
elif diff > 0:
# no s1 to balance s2's lead
if i == len(s1): return False
# move s1 pointer forward and reduce diff
return dp(i+1, j, diff-1)

# if none of them have integer prefix and s1 lead over s2
else:
# no s2 to balance s1's lead
if j == len(s2): return False
# move s2 pointer forward and increase diff
return dp(i, j+1, diff+1)

return dp(0, 0, 0)


### [2108/Easy] Find First Palindromic String in the Array

#### Problem

• Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "".

• A string is palindromic if it reads the same forward and backward.

• Example 1:

Input: words = ["abc","car","ada","racecar","cool"]
Explanation: The first string that is palindromic is "ada".
Note that "racecar" is also palindromic, but it is not the first.


Example 2:

Input: words = ["notapalindrome","racecar"]
Output: "racecar"
Explanation: The first and only string that is palindromic is "racecar".

• Example 3:
Input: words = ["def","ghi"]
Output: ""
Explanation: There are no palindromic strings, so the empty string is returned.

• Constraints:
• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists only of lowercase English letters.
• See problem on LeetCode.

#### Solution

class Solution:
def firstPalindrome(self, words: List[str]) -> str:
for word in words:
if self.isPalindrome(word):
return word
return ""

def isPalindrome(self, word) -> bool:
l, r = 0, len(word)-1
while l < r:
if word[l] != word[r]:
return False
l += 1
r -= 1
return True
# or return word == word[::-1] (less efficient)

##### Complexity
• Time: $$O(nm)$$ where $$n$$ are the number of words in the input and $$m$$ is the average length of each word.
• Space: $$O(n)$$ for word[::-1]`