fbpx

Top 100 Amazon Coding Interview Questions and Answers

Top 100 Amazon Coding Interview Questions and Answers
Contents show

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
    currentA, currentB = headA, headB

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

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

    diff = abs(lenA - lenB)
    currentA, currentB = headA, headB

    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

def reverse_linked_list(head):
    prev = None
    current = head

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

    return prev

Reference: Reverse Linked List


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

    def add_edge(self, u, v):
        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 = {}

    def add_edge(self, node, neighbors):
        self.graph[node] = neighbors

    def dfs_recursive(self, node, visited):
        if node not in visited:
            print(node, end=' ')
            visited.add(node)
            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 = {}

    def add_edge(self, node, neighbors):
        self.graph[node] = neighbors

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

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

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

Reference: Breadth-First Search


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

def reverse_linked_list(head):
    prev = None
    current = head

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

    return prev

Reference: Reverse a Linked List


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

    def add_edge(self, u, v):
        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


56. Reverse Linked List

Reverse a singly linked list.

Code Example (Python):

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

def reverse_list(head):
    prev = None

    while head:
        temp = head.next
        head.next = prev
        prev = head
        head = temp

    return prev

Reference: Reverse Linked List


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

def get_intersection_node(headA, headB):
    if not headA or not headB:
        return None

    a, b = headA, headB

    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

def reverse_k_group(head, k):
    def reverse(head, k):
        prev = None
        curr = head

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

        return prev

    count = 0
    curr = head

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

    if count == k:
        new_head = reverse(head, k)
        head.next = self.reverse_k_group(curr, k)
        return new_head

    return head

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)


67. Palindrome Linked List

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 is_palindrome(head):
    def reverse_list(node):
        prev = None
        while node:
            next_node = node.next
            node.next = prev
            prev = node
            node = next_node
        return prev

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

    slow = reverse_list(slow)
    fast = head

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

    return True

Reference: Palindrome Linked List


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


70. Add Two Numbers

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

def add_two_numbers(l1, l2):
    dummy_head = ListNode(0)
    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)

    return dummy_head.next

Reference: Add Two Numbers


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


74. Reverse Linked List

Reverse a linked list.

Code Example (Python):

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

def reverse_linked_list(head):
    prev = None

    while head is not None:
        temp = head.next
        head.next = prev
        prev = head
        head = temp

    return prev

Reference: Reverse Linked List


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


79. Word Ladder

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

def ladder_length(beginWord, endWord, wordList):
    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

Reference: Word Ladder


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


88. Reverse Linked List

Reverse a singly linked list.

Code Example (Python):

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

def reverse_linked_list(head):
    prev = None

    while head:
        next_node = head.next
        head.next = prev
        prev = head
        head = next_node

    return prev

Reference: Reverse Linked List


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


94. Add Two Numbers

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

def add_two_numbers(l1, l2):
    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

Reference: Add Two Numbers


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