# Top 100 Amazon Coding Interview Questions and Answers

Contents

### 1. Find the Missing Number in an Array

To find the missing number in an array, you can calculate the sum of numbers from 1 to n using the formula n*(n+1)/2. Then, subtract the sum of the given array from it.

Code Example (Python):

``````def find_missing_number(arr):
n = len(arr) + 1
expected_sum = n * (n+1) // 2
actual_sum = sum(arr)
return expected_sum - actual_sum

# Usage
arr = [1, 2, 4, 5]
missing_number = find_missing_number(arr)``````

Reference: Find Missing Number in Array

### 2. Reverse a String

To reverse a string, you can use string slicing.

Code Example (Python):

``````def reverse_string(s):
return s[::-1]

# Usage
original = "hello"
reversed_str = reverse_string(original)``````

Reference: Reverse a String in Python

### 3. Check if a String is Palindrome

A palindrome reads the same backward as forward. To check, compare the string with its reverse.

Code Example (Python):

``````def is_palindrome(s):
return s == s[::-1]

# Usage
check_string = "racecar"
is_palindrome = is_palindrome(check_string)``````

Reference: Check Palindrome String in Python

### 4. Find the Largest Element in an Array

You can use the `max()` function to find the largest element in an array.

Code Example (Python):

``````def find_largest_element(arr):
return max(arr)

# Usage
arr = [4, 7, 2, 11, 8]
largest_element = find_largest_element(arr)``````

Reference: Find Maximum Element in Array

### 5. Implement a Binary Search

Binary search is an efficient algorithm for finding an item in a sorted list. It works by repeatedly dividing in half the portion of the list that could contain the item.

Code Example (Python):

``````def binary_search(arr, target):
left, right = 0, len(arr) - 1

while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1

# Usage
arr = [1, 3, 5, 7, 9, 11]
target = 7
index = binary_search(arr, target)``````

Reference: Binary Search Algorithm

### 6. Implement a Queue using Stacks

You can implement a queue using two stacks. One stack is used for pushing elements, and the other for popping.

Code Example (Python):

``````class QueueUsingStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []

def enqueue(self, val):
self.stack1.append(val)

def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop() if self.stack2 else None

# Usage
q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
val = q.dequeue()``````

Reference: Queue using Stacks

### 7. Find the Intersection Point of Two Linked Lists

To find the intersection point of two linked lists, calculate the length difference, then traverse both lists until they have the same length.

Code Example (Python):

``````def get_intersection_point(headA, headB):
lenA, lenB = 0, 0

while currentA:
lenA += 1
currentA = currentA.next

while currentB:
lenB += 1
currentB = currentB.next

diff = abs(lenA - lenB)

if lenA > lenB:
for _ in range(diff):
currentA = currentA.next
else:
for _ in range(diff):
currentB = currentB.next

while currentA != currentB:
currentA = currentA.next
currentB = currentB.next

return currentA``````

Reference: Intersection Point of Two Linked Lists

### 8. Find the Smallest Element in a Rotated Sorted Array

To find the smallest element in a rotated sorted array, you can use binary search.

Code Example (Python):

``````def find_smallest_element(nums):
left, right = 0, len(nums) - 1

while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid

return nums[left]``````

Reference: Find Minimum in Rotated Sorted Array

### 9. Check if a Binary Tree is Balanced

A balanced binary tree is a tree in which the height of the left and right subtrees of every node differ by at most one.

Code Example (Python):

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def is_balanced(root):
def height(node):
if not node:
return -1
left_height = height(node.left)
right_height = height(node.right)

if left_height == float('-inf') or right_height == float('-inf') or abs(left_height - right_height) > 1:
return float('-inf')

return max(left_height, right_height) + 1

return height(root) != float('-inf')``````

Reference: Balanced Binary Tree

### 10. Find the First Non-Repeating Character in a String

You can find the first non-repeating character in a string by using a hash map to count the occurrences.

Code Example (Python):

``````def first_non_repeating_char(s):
char_count = {}
for char in s:
if char in char_count:
char_count[char] += 1
else:
char_count[char] = 1

for char in s:
if char_count[char] == 1:
return char

return None``````

Reference: First Unique Character in a String

### 11. Implement a LRU Cache

A Least Recently Used (LRU) cache is a data structure that maintains the most recently used items. It has a capacity and discards the least recently used item if itโs full.

Code Example (Python โ Using OrderedDict):

``````from collections import OrderedDict

class LRUCache:
def __init__(self, capacity):
self.cache = OrderedDict()
self.capacity = capacity

def get(self, key):
if key in self.cache:
value = self.cache[key]
self.cache.move_to_end(key)
return value
return -1

def put(self, key, value):
if key in self.cache:
del self.cache[key]
elif len(self.cache) == self.capacity:
self.cache.popitem(last=False)

self.cache[key] = value``````

Reference: LRU Cache Implementation

### 12. Validate a Binary Search Tree (BST)

A binary search tree (BST) is a binary tree where, for each node, any descendant of the left child is less than the node, and any descendant of the right child is greater than the node.

Code Example (Python):

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def is_valid_BST(root):
def validate(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True

if not (lower < node.val < upper):
return False

return validate(node.left, lower, node.val) and validate(node.right, node.val, upper)

return validate(root)``````

Reference: Validate Binary Search Tree

### 13. Rotate an Array

To rotate an array, you can use array slicing or reverse sections of the array.

Code Example (Python):

``````def rotate_array(nums, k):
k %= len(nums)
nums[:k], nums[k:] = nums[-k:], nums[:-k]``````

Reference: Rotate Array

### 14. Implement a Trie (Prefix Tree)

A Trie is a tree-like data structure used for storing a dynamic set of strings. Itโs useful for tasks like autocomplete.

Code Example (Python):

``````class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True

def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word

def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True``````

Reference: Trie (Prefix Tree)

### 15. Find the Longest Substring Without Repeating Characters

To find the longest substring without repeating characters, you can use the sliding window technique.

Code Example (Python):

``````def longest_substring(s):
max_length = 0
start = 0
char_map = {}

for i, char in enumerate(s):
if char in char_map and char_map[char] >= start:
start = char_map[char] + 1
char_map[char] = i
max_length = max(max_length, i - start + 1)

return max_length``````

Reference: Longest Substring Without Repeating Characters

### 16. Merge Intervals

Given a collection of intervals, merge any overlapping intervals.

Code Example (Python):

``````def merge_intervals(intervals):
if not intervals:
return []

intervals.sort(key=lambda x: x[0])
result = [intervals[0]]

for interval in intervals[1:]:
if interval[0] <= result[-1][1]:
result[-1][1] = max(result[-1][1], interval[1])
else:
result.append(interval)

return result``````

Reference: Merge Intervals

### 17. Reverse a Linked List

To reverse a linked list, you can iteratively reverse the pointers.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

prev = None

while current:
next_node = current.next
current.next = prev
prev = current
current = next_node

return prev``````

### 18. Implement a Stack using Queues

You can implement a stack using two queues. One queue is used for pushing elements, and the other for popping.

Code Example (Python):

``````from queue import Queue

class StackUsingQueues:
def __init__(self):
self.queue1 = Queue()
self.queue2 = Queue()

def push(self, val):
self.queue1.put(val)

while not self.queue2.empty():
self.queue1.put(self.queue2.get())

self.queue1, self.queue2 = self.queue2, self.queue1

def pop(self):
return self.queue2.get() if not self.queue2.empty() else None``````

Reference: Implement Stack using Queues

### 19. Find the Missing Number

Given an array containing n distinct numbers taken from the range 0 to n, find the one that is missing from the array.

Code Example (Python):

``````def find_missing_number(nums):
n = len(nums)
expected_sum = n * (n + 1) // 2
actual_sum = sum(nums)
return expected_sum - actual_sum``````

Reference: Missing Number

### 20. Check if a String is a Palindrome

A palindrome is a word, phrase, number, or other sequence of characters that reads the same forward and backward.

Code Example (Python):

``````def is_palindrome(s):
s = ''.join(char.lower() for char in s if char.isalnum())
return s == s[::-1]``````

Reference: Valid Palindrome

### 21. Find the Maximum Subarray Sum

To find the maximum subarray sum, you can use Kadaneโs algorithm.

Code Example (Python):

``````def max_subarray_sum(nums):
max_sum = float('-inf')
current_sum = 0

for num in nums:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)

return max_sum``````

Reference: Maximum Subarray

### 22. Implement a Binary Search

Binary search is an efficient algorithm for finding an item from a sorted list of items.

Code Example (Python):

``````def binary_search(nums, target):
left, right = 0, len(nums) - 1

while left <= right:
mid = (left + right) // 2

if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1

return -1``````

Reference: Binary Search

### 23. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of pโs anagrams in s.

Code Example (Python):

``````from collections import Counter

def find_anagrams(s, p):
result = []
p_counter = Counter(p)
s_counter = Counter(s[:len(p)-1])

for i in range(len(p)-1, len(s)):
s_counter[s[i]] += 1
if s_counter == p_counter:
result.append(i - len(p) + 1)
s_counter[s[i - len(p) + 1]] -= 1
if s_counter[s[i - len(p) + 1]] == 0:
del s_counter[s[i - len(p) + 1]]

return result``````

Reference: Find All Anagrams in a String

### 24. Implement a Queue using Stacks

You can implement a queue using two stacks. One stack is used for enqueueing, and the other for dequeueing.

Code Example (Python):

``````class QueueUsingStacks:
def __init__(self):
self.stack1 = []
self.stack2 = []

def enqueue(self, val):
self.stack1.append(val)

def dequeue(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop() if self.stack2 else None``````

Reference: Implement Queue using Stacks

### 25. Counting Sort

Counting Sort is a non-comparison based sorting algorithm that sorts integers within a specific range.

Code Example (Python):

``````def counting_sort(nums):
max_val = max(nums)
count = [0] * (max_val + 1)

for num in nums:
count[num] += 1

result = []
for i in range(max_val + 1):
result.extend([i] * count[i])

return result``````

Reference: Counting Sort

### 26. Find the Peak Element in an Array

A peak element in an array is an element that is greater than its neighbors.

Code Example (Python):

``````def find_peak_element(nums):
left, right = 0, len(nums) - 1

while left < right:
mid = (left + right) // 2

if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1

return left``````

Reference: Find Peak Element

### 27. Detect Cycle in a Directed Graph

Detecting a cycle in a directed graph can be done using depth-first search (DFS).

Code Example (Python):

``````from collections import defaultdict

class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices

self.graph[u].append(v)

def is_cyclic_util(self, v, visited, rec_stack):
visited[v] = True
rec_stack[v] = True

for neighbor in self.graph[v]:
if not visited[neighbor]:
if self.is_cyclic_util(neighbor, visited, rec_stack):
return True
elif rec_stack[neighbor]:
return True

rec_stack[v] = False
return False

def is_cyclic(self):
visited = [False] * self.V
rec_stack = [False] * self.V

for node in range(self.V):
if not visited[node]:
if self.is_cyclic_util(node, visited, rec_stack):
return True

return False``````

Reference: Detect Cycle in a Directed Graph

### 28. Implement a Min-Heap

A min-heap is a binary tree data structure where the parent node is smaller than its children.

Code Example (Python):

``````import heapq

class MinHeap:
def __init__(self):
self.heap = []

def push(self, val):
heapq.heappush(self.heap, val)

def pop(self):
return heapq.heappop(self.heap)

def peek(self):
return self.heap[0] if self.heap else None

def size(self):
return len(self.heap)``````

Reference: heapq โ Heap queue algorithm

### 29. Two Sum Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

Code Example (Python):

``````def two_sum(nums, target):
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = i``````

Reference: Two Sum

### 30. Implement Depth-First Search (DFS)

Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures.

Code Example (Python โ Recursive):

``````class Graph:
def __init__(self):
self.graph = {}

self.graph[node] = neighbors

def dfs_recursive(self, node, visited):
if node not in visited:
print(node, end=' ')
for neighbor in self.graph[node]:
self.dfs_recursive(neighbor, visited)``````

Reference: Depth-First Search

### 31. Implement Breadth-First Search (BFS)

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures.

Code Example (Python):

``````from collections import deque

class Graph:
def __init__(self):
self.graph = {}

self.graph[node] = neighbors

def bfs(self, start):
visited = set()
queue = deque([start])

while queue:
node = queue.popleft()
print(node, end=' ')

for neighbor in self.graph[node]:
if neighbor not in visited:
queue.append(neighbor)

### 32. Implement Dijkstraโs Algorithm

Dijkstraโs algorithm is used to find the shortest path between nodes in a weighted graph.

Code Example (Python):

``````import heapq

def dijkstra(graph, start):
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]

while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)

if current_distance > distances[current_node]:
continue

for neighbor, weight in graph[current_node].items():
distance = current_distance + weight

if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))

return distances``````

Reference: Dijkstraโs Algorithm

### 33. Reverse a Linked List

Reversing a linked list involves changing the direction of pointers in each node so that the list is reversed.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

prev = None

while current:
next_node = current.next
current.next = prev
prev = current
current = next_node

return prev``````

### 34. Check for Balanced Parentheses

You can check if a string containing parentheses is balanced using a stack.

Code Example (Python):

``````def is_valid_parentheses(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}

for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)

return not stack``````

Reference: Valid Parentheses

### 35. Merge Intervals

Merging intervals involves combining overlapping intervals into a single interval.

Code Example (Python):

``````def merge_intervals(intervals):
if not intervals:
return []

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]

for interval in intervals[1:]:
if interval[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], interval[1])
else:
merged.append(interval)

return merged``````

Reference: Merge Intervals

### 36. Serialize and Deserialize a Binary Tree

Serializing a binary tree means converting it into a string, while deserializing means converting it back to a binary tree.

Code Example (Python):

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def serialize(root):
def build_string(node):
if not node:
return 'None,'
return str(node.val) + ',' + build_string(node.left) + build_string(node.right)

return build_string(root)

def deserialize(data):
def build_tree(values):
val = values.pop(0)
if val == 'None':
return None
node = TreeNode(int(val))
node.left = build_tree(values)
node.right = build_tree(values)
return node

values = data.split(',')
return build_tree(values[:-1])``````

Reference: Serialize and Deserialize Binary Tree

### 37. Longest Common Subsequence

The Longest Common Subsequence (LCS) problem involves finding the longest subsequence that two sequences have in common.

Code Example (Python):

``````def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[m][n]``````

Reference: Longest Common Subsequence

### 38. Topological Sorting

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v.

Code Example (Python):

``````from collections import defaultdict

class Graph:
def __init__(self, vertices):
self.graph = defaultdict(list)
self.V = vertices

self.graph[u].append(v)

def topological_sort_util(self, v, visited, stack):
visited[v] = True
for neighbor in self.graph[v]:
if not visited[neighbor]:
self.topological_sort_util(neighbor, visited, stack)
stack.append(v)

def topological_sort(self):
visited = [False] * self.V
stack = []

for i in range(self.V):
if not visited[i]:
self.topological_sort_util(i, visited, stack)

return stack[::-1]``````

Reference: Topological Sorting

### 39. Find All Anagrams in a String

Given a string `s` and a non-empty string `p`, find all the start indices of `p`โs anagrams in `s`.

Code Example (Python):

``````from collections import Counter

def find_anagrams(s, p):
result = []
p_counter = Counter(p)
s_counter = Counter(s[:len(p)])

for i in range(len(s) - len(p) + 1):
if s_counter == p_counter:
result.append(i)
if i + len(p) < len(s):
s_counter[s[i]] -= 1
if s_counter[s[i]] == 0:
del s_counter[s[i]]
s_counter[s[i + len(p)]] += 1

return result``````

Reference: Find All Anagrams in a String

### 40. Longest Palindromic Substring

Given a string, find the longest palindromic substring in it.

Code Example (Python):

``````def longest_palindrome(s):
def expand_around_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]

longest = ""
for i in range(len(s)):
odd_palindrome = expand_around_center(s, i, i)
even_palindrome = expand_around_center(s, i, i + 1)

if len(odd_palindrome) > len(longest):
longest = odd_palindrome
if len(even_palindrome) > len(longest):
longest = even_palindrome

return longest``````

Reference: Longest Palindromic Substring

### 41. Minimum Window Substring

Given a string `s` and a string `t`, find the minimum window in `s` which will contain all the characters in `t` in complexity O(n).

Code Example (Python):

``````from collections import Counter

def min_window(s, t):
if not s or not t:
return ""

target_counts = Counter(t)
required = len(target_counts)
left, right = 0, 0
formed = 0
window_counts = {}

ans = float('inf'), None, None

while right < len(s):
char = s[right]
window_counts[char] = window_counts.get(char, 0) + 1

if char in target_counts and window_counts[char] == target_counts[char]:
formed += 1

while left <= right and formed == required:
char = s[left]

if right - left + 1 < ans[0]:
ans = (right - left + 1, left, right)

window_counts[char] -= 1
if char in target_counts and window_counts[char] < target_counts[char]:
formed -= 1

left += 1

right += 1

return "" if ans[0] == float('inf') else s[ans[1]:ans[2] + 1]``````

Reference: Minimum Window Substring

### 42. Implement Trie (Prefix Tree)

A trie, also known as a prefix tree, is a tree-like data structure used for efficient retrieval of a set of keys with strings.

Code Example (Python):

``````class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True

def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word

def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True``````

Reference: Trie (Prefix Tree)

### 43. Valid Sudoku

Determine if a 9ร9 Sudoku board is valid. The Sudoku board could be partially filled, where empty cells are filled with the character `'.'`.

Code Example (Python):

``````def is_valid_sudoku(board):
rows = [{} for _ in range(9)]
columns = [{} for _ in range(9)]
boxes = [{} for _ in range(9)]

for i in range(9):
for j in range(9):
if board[i][j] != '.':
num = int(board[i][j])
box_index = (i // 3) * 3 + j // 3

rows[i][num] = rows[i].get(num, 0) + 1
columns[j][num] = columns[j].get(num, 0) + 1
boxes[box_index][num] = boxes[box_index].get(num, 0) + 1

if rows[i][num] > 1 or columns[j][num] > 1 or boxes[box_index][num] > 1:
return False

return True``````

Reference: Valid Sudoku

### 44. Merge Intervals

Given a collection of intervals, merge any overlapping intervals.

Code Example (Python):

``````def merge(intervals):
if not intervals:
return []

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]

for i in range(1, len(intervals)):
current_interval = intervals[i]
if current_interval[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], current_interval[1])
else:
merged.append(current_interval)

return merged``````

Reference: Merge Intervals

### 45. Validate Binary Search Tree (BST)

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

Code Example (Python):

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def is_valid_bst(root):
def validate(node, lower=float('-inf'), upper=float('inf')):
if not node:
return True

val = node.val
if val <= lower or val >= upper:
return False

if not validate(node.right, val, upper):
return False
if not validate(node.left, lower, val):
return False

return True

return validate(root)``````

Reference: Validate Binary Search Tree

### 46. Maximum Subarray

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

Code Example (Python):

``````def max_subarray(nums):
max_sum = nums[0]
current_sum = nums[0]

for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)

return max_sum``````

Reference: Maximum Subarray

### 47. Longest Increasing Subsequence (LIS)

Given an unsorted array of integers, find the length of longest increasing subsequence.

Code Example (Python):

``````def length_of_lis(nums):
if not nums:
return 0

dp = [1] * len(nums)

for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)

return max(dp)``````

Reference: Longest Increasing Subsequence

### 48. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Code Example (Python):

``````def trap(height):
if not height:
return 0

left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
trapped_water = 0

while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
trapped_water += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
trapped_water += right_max - height[right]

return trapped_water``````

Reference: Trapping Rain Water

### 49. 3Sum

Given an integer array nums, return all the unique triplets that sum up to a target value.

Code Example (Python):

``````def three_sum(nums):
nums.sort()
triplets = []

for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue

left, right = i + 1, len(nums) - 1

while left < right:
total = nums[i] + nums[left] + nums[right]

if total < 0:
left += 1
elif total > 0:
right -= 1
else:
triplets.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1

return triplets``````

Reference: 3Sum

### 50. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

Code Example (Python):

``````def exist(board, word):
def dfs(i, j, k):
if not (0 <= i < len(board)) or not (0 <= j < len(board[0])) or board[i][j] != word[k]:
return False
if k == len(word) - 1:
return True

tmp, board[i][j] = board[i][j], "/"
found = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
board[i][j] = tmp
return found

for i in range(len(board)):
for j in range(len(board[0])):
if dfs(i, j, 0):
return True

return False``````

Reference: Word Search

### 51. Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses โ 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Code Example (Python):

``````from collections import defaultdict, deque

def can_finish(numCourses, prerequisites):
graph = defaultdict(list)
indegree = [0] * numCourses

for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1

queue = deque()

for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)

while queue:
course = queue.popleft()
numCourses -= 1

for neighbor in graph[course]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)

return numCourses == 0``````

Reference: Course Schedule

### 52. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Code Example (Python):

``````def longest_palindrome(s):
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1

start, end = 0, 0

for i in range(len(s)):
len1 = expand_around_center(i, i)
len2 = expand_around_center(i, i + 1)
max_len = max(len1, len2)

if max_len > end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2

return s[start:end+1]``````

Reference: Longest Palindromic Substring

### 53. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

Code Example (Python):

``````from heapq import heappush, heappop

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def merge_k_sorted_lists(lists):
heap = []

for l in lists:
while l:
heappush(heap, l.val)
l = l.next

dummy = ListNode()
current = dummy

while heap:
current.next = ListNode(heappop(heap))
current = current.next

return dummy.next``````

Reference: Merge k Sorted Lists

### 54. Valid Parentheses

Given a string s containing just the characters โ(โ, โ)โ, โ{โ, โ}โ, โ[โ and โ]โ, determine if the input string is valid.

Code Example (Python):

``````def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}

for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)

return not stack``````

Reference: Valid Parentheses

### 55. Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodesโ values.

Code Example (Python):

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def inorder_traversal(root):
result = []
stack = []

while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
result.append(root.val)
root = root.right

return result``````

Reference: Binary Tree Inorder Traversal

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

prev = None

return prev``````

### 57. Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Code Example (Python):

``````def subarray_sum(nums, k):
count = 0
sum_dict = {0: 1}
curr_sum = 0

for num in nums:
curr_sum += num
if curr_sum - k in sum_dict:
count += sum_dict[curr_sum - k]
if curr_sum in sum_dict:
sum_dict[curr_sum] += 1
else:
sum_dict[curr_sum] = 1

return count``````

Reference: Subarray Sum Equals K

### 58. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

return None

while a != b:
a = a.next if a else headB
b = b.next if b else headA

return a``````

Reference: Intersection of Two Linked Lists

### 59. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Code Example (Python):

``````from collections import Counter

def top_k_frequent(nums, k):
counter = Counter(nums)
return [item[0] for item in counter.most_common(k)]``````

Reference: Top K Frequent Elements

### 60. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Code Example (Python):

``````def three_sum(nums):
nums.sort()
result = []

for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue

left, right = i + 1, len(nums) - 1

while left < right:
total = nums[i] + nums[left] + nums[right]

if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1

return result``````

Reference: 3Sum

### 61. Longest Common Prefix

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 โโ.

Code Example (Python):

``````def longest_common_prefix(strs):
if not strs:
return ""

for i, char in enumerate(zip(*strs)):
if len(set(char)) > 1:
return strs[0][:i]

return min(strs)``````

Reference: Longest Common Prefix

### 62. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def merge_two_lists(l1, l2):
dummy = ListNode()
current = dummy

while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next

current.next = l1 or l2

return dummy.next``````

Reference: Merge Two Sorted Lists

### 63. Container With Most Water

Given n non-negative integers a1, a2, โฆ, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Code Example (Python):

``````def max_area(height):
max_area = 0
left, right = 0, len(height) - 1

while left < right:
max_area = max(max_area, min(height[left], height[right]) * (right - left))
if height[left] < height[right]:
left += 1
else:
right -= 1

return max_area``````

Reference: Container With Most Water

### 64. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

prev = None

for _ in range(k):
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node

return prev

count = 0

while count < k and curr:
curr = curr.next
count += 1

if count == k:

Reference: Reverse Nodes in k-Group

### 65. Valid Parentheses

Given a string containing just the characters โ(โ, โ)โ, โ{โ, โ}โ, โ[โ and โ]โ, determine if the input string is valid. An input string is valid if the brackets are closed in the correct order.

Code Example (Python):

``````def is_valid(s):
stack = []
mapping = {')': '(', '}': '{', ']': '['}

for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)

return not stack``````

Reference: Valid Parentheses

### 66. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Code Example (Python):

``````class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True

def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word

def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True``````

Reference: Implement Trie (Prefix Tree)

Given a singly linked list, determine if it is a palindrome.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def reverse_list(node):
prev = None
while node:
next_node = node.next
node.next = prev
prev = node
node = next_node
return prev

while fast and fast.next:
slow = slow.next
fast = fast.next.next

slow = reverse_list(slow)

while slow:
if slow.val != fast.val:
return False
slow = slow.next
fast = fast.next

return True``````

### 68. Longest Common Prefix

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 โโ.

Code Example (Python):

``````def longest_common_prefix(strs):
if not strs:
return ""

min_len = min(len(s) for s in strs)
lcp = ""

for i in range(min_len):
char = strs[0][i]
if all(s[i] == char for s in strs):
lcp += char
else:
break

return lcp``````

Reference: Longest Common Prefix

### 69. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Code Example (Python):

``````def two_sum(nums, target):
num_dict = {}

for i, num in enumerate(nums):
complement = target - num
if complement in num_dict:
return [num_dict[complement], i]
num_dict[num] = i

return None``````

Reference: Two Sum

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.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

p, q, current = l1, l2, dummy_head
carry = 0

while p is not None or q is not None:
x = p.val if p else 0
y = q.val if q else 0
sum = carry + x + y
carry = sum // 10
current.next = ListNode(sum % 10)
current = current.next

if p: p = p.next
if q: q = q.next

if carry > 0:
current.next = ListNode(carry)

### 71. Merge Intervals

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.

Code Example (Python):

``````def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]

for interval in intervals[1:]:
if interval[0] <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], interval[1])
else:
merged.append(interval)

return merged``````

Reference: Merge Intervals

### 72. Valid Parentheses

Given a string containing just the characters โ(โ, โ)โ, โ{โ, โ}โ, โ[โ and โ]โ, determine if the input string is valid. An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Code Example (Python):

``````def is_valid(s):
stack = []
bracket_pairs = {')': '(', '}': '{', ']': '['}

for char in s:
if char in bracket_pairs.values():
stack.append(char)
elif char in bracket_pairs.keys():
if not stack or bracket_pairs[char] != stack.pop():
return False
else:
return False

return not stack``````

Reference: Valid Parentheses

### 73. Container With Most Water

Given n non-negative integers a1, a2, โฆ, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Code Example (Python):

``````def max_area(height):
max_area = 0
left, right = 0, len(height) - 1

while left < right:
h = min(height[left], height[right])
max_area = max(max_area, (right - left) * h)

while height[left] <= h and left < right:
left += 1
while height[right] <= h and left < right:
right -= 1

return max_area``````

Reference: Container With Most Water

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

prev = None

return prev``````

### 75. Group Anagrams

Given an array of strings, group anagrams together.

Code Example (Python):

``````def group_anagrams(strs):
anagram_dict = {}

for word in strs:
sorted_word = "".join(sorted(word))
if sorted_word in anagram_dict:
anagram_dict[sorted_word].append(word)
else:
anagram_dict[sorted_word] = [word]

return list(anagram_dict.values())``````

Reference: Group Anagrams

### 76. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Code Example (Python):

``````class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True

def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word

def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True``````

Reference: Implement Trie (Prefix Tree)

### 77. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence.

Code Example (Python):

``````def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]

for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

return dp[m][n]``````

Reference: Longest Common Subsequence

### 78. Merge Intervals

Given a collection of intervals, merge any overlapping intervals.

Code Example (Python):

``````def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []

for interval in intervals:
if not merged or interval[0] > merged[-1][1]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])

return merged``````

Reference: Merge Intervals

Given two words (beginWord and endWord), and a dictionaryโs word list, find the length of the shortest transformation sequence from beginWord to endWord.

Code Example (Python):

``````from collections import deque

wordSet = set(wordList)
if endWord not in wordSet:
return 0

queue = deque([(beginWord, 1)])

while queue:
word, level = queue.popleft()

if word == endWord:
return level

for i in range(len(word)):
for char in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + char + word[i+1:]
if new_word in wordSet:
wordSet.remove(new_word)
queue.append((new_word, level+1))

return 0``````

### 80. Valid Parentheses

Given a string containing just the characters โ(โ, โ)โ, โ{โ, โ}โ, โ[โ and โ]โ, determine if the input string is valid.

Code Example (Python):

``````def is_valid(s):
stack = []
mapping = {")": "(", "}": "{", "]": "["}

for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)

return not stack``````

Reference: Valid Parentheses

### 81. Maximum Subarray

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

Code Example (Python):

``````def max_sub_array(nums):
max_sum = float('-inf')
current_sum = 0

for num in nums:
current_sum += num
max_sum = max(max_sum, current_sum)

if current_sum < 0:
current_sum = 0

return max_sum``````

Reference: Maximum Subarray

### 82. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks.

Code Example (Python):

``````class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []

def push(self, x):
self.stack1.append(x)

def pop(self):
self.peek()
return self.stack2.pop()

def peek(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]

def empty(self):
return not self.stack1 and not self.stack2``````

Reference: Implement Queue using Stacks

### 83. Merge Intervals

Given a collection of intervals, merge any overlapping intervals.

Code Example (Python):

``````def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []

for interval in intervals:
if not merged or interval[0] > merged[-1][1]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])

return merged``````

Reference: Merge Intervals

### 84. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Code Example (Python):

``````def climb_stairs(n):
if n == 1:
return 1
first, second = 1, 2

for i in range(3, n+1):
third = first + second
first = second
second = third

return second``````

Reference: Climbing Stairs

### 85. Subsets

Given an integer array nums, return all possible subsets (the power set).

Code Example (Python):

``````def subsets(nums):
result = [[]]

for num in nums:
result += [curr + [num] for curr in result]

return result``````

Reference: Subsets

### 86. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def merge_two_lists(l1, l2):
dummy = ListNode()
current = dummy

while l1 and l2:
if l1.val < l2.val:
current.next = l1
l1 = l1.next
else:
current.next = l2
l2 = l2.next
current = current.next

if l1:
current.next = l1
if l2:
current.next = l2

return dummy.next``````

Reference: Merge Two Sorted Lists

### 87. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Code Example (Python):

``````def length_of_longest_substring(s):
char_index = {}
max_length = 0
start = 0

for end in range(len(s)):
if s[end] in char_index and char_index[s[end]] >= start:
start = char_index[s[end]] + 1
char_index[s[end]] = end
max_length = max(max_length, end - start + 1)

return max_length``````

Reference: Longest Substring Without Repeating Characters

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

prev = None

return prev``````

### 89. Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

Code Example (Python):

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

def is_valid_bst(root):
def is_valid(node, min_val, max_val):
if not node:
return True

if not (min_val < node.val < max_val):
return False

return is_valid(node.left, min_val, node.val) and is_valid(node.right, node.val, max_val)

return is_valid(root, float('-inf'), float('inf'))``````

Reference: Validate Binary Search Tree

### 90. Best Time to Buy and Sell Stock

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Code Example (Python):

``````def max_profit(prices):
min_price = float('inf')
max_profit = 0

for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price

return max_profit``````

Reference: Best Time to Buy and Sell Stock

### 91. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Code Example (Python):

``````def longest_palindrome(s):
def expand_around_center(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left + 1:right]

longest = ""

for i in range(len(s)):
palindrome1 = expand_around_center(i, i)
palindrome2 = expand_around_center(i, i + 1)

if len(palindrome1) > len(longest):
longest = palindrome1
if len(palindrome2) > len(longest):
longest = palindrome2

return longest``````

Reference: Longest Palindromic Substring

### 92. Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed.

Code Example (Python):

``````def reverse_integer(x):
if x == 0:
return 0

max_int = 2**31 - 1
min_int = -2**31

if x > 0:
result = int(str(x)[::-1])
else:

result = -int(str(-x)[::-1])

if result < min_int or result > max_int:
return 0

return result``````

Reference: Reverse Integer

### 93. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Code Example (Python):

``````def two_sum(nums, target):
num_dict = {}

for i, num in enumerate(nums):
complement = target - num
if complement in num_dict:
return [num_dict[complement], i]
num_dict[num] = i

return None``````

Reference: Two Sum

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.

Code Example (Python):

``````class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

dummy = ListNode()
current = dummy
carry = 0

while l1 or l2:
x = l1.val if l1 else 0
y = l2.val if l2 else 0

current_sum = x + y + carry
carry = current_sum // 10

current.next = ListNode(current_sum % 10)
current = current.next

if l1: l1 = l1.next
if l2: l2 = l2.next

if carry > 0:
current.next = ListNode(carry)

return dummy.next``````

### 95. Container With Most Water

Given n non-negative integers a1, a2, โฆ, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Code Example (Python):

``````def max_area(height):
max_area = 0
left = 0
right = len(height) - 1

while left < right:
max_area = max(max_area, min(height[left], height[right]) * (right - left))

if height[left] < height[right]:
left += 1
else:
right -= 1

return max_area``````

Reference: Container With Most Water

### 96. Valid Parentheses

Given a string containing just the characters โ(โ, โ)โ, โ{โ, โ}โ, โ[โ and โ]โ, determine if the input string is valid.

Code Example (Python):

``````def is_valid(s):
stack = []

for char in s:
if char in '({[':
stack.append(char)
else:
if not stack:
return False
if char == ')' and stack[-1] != '(':
return False
if char == '}' and stack[-1] != '{':
return False
if char == ']' and stack[-1] != '[':
return False
stack.pop()

return not stack``````

Reference: Valid Parentheses

### 97. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Code Example (Python):

``````def is_palindrome(x):
if x < 0 or (x % 10 == 0 and x != 0):
return False

reversed_num = 0
while x > reversed_num:
reversed_num = reversed_num * 10 + x % 10
x = x // 10

return x == reversed_num or x == reversed_num // 10``````

Reference: Palindrome Number

### 98. Roman to Integer

Given a roman numeral, convert it to an integer.

Code Example (Python):

``````def roman_to_integer(s):
roman_dict = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000
}

result = 0
prev_value = 0

for char in s:
value = roman_dict[char]

if value > prev_value:
result += value - 2 * prev_value
else:
result += value

prev_value = value

return result``````

Reference: Roman to Integer

### 99. Integer to Roman

Given an integer, convert it to a roman numeral.

Code Example (Python):

``````def integer_to_roman(num):
value_dict = {
1: 'I',
4: 'IV',
5: 'V',
9: 'IX',
10: 'X',
40: 'XL',
50: 'L',
90: 'XC',
100: 'C',
400: 'CD',
500: 'D',
900: 'CM',
1000: 'M'
}

result = ""

for value in sorted(value_dict.keys(), reverse=True):
while num >= value:
result += value_dict[value]
num -= value

return result``````

Reference: Integer to Roman

### 100. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Code Example (Python):

``````def climb_stairs(n):
if n <= 2:
return n

prev1 = 1
prev2 = 2

for i in range(3, n + 1):
current = prev1 + prev2
prev1 = prev2
prev2 = current

return prev2``````

Reference: Climbing Stairs