Menu iconMenu iconIntroduction to Algorithms
Introduction to Algorithms

Chapter 8: Data Structures Used in Algorithms

8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms

Problem 1: Arrays - Maximum Subarray Sum

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

Solution: We can solve this problem using Kadane's algorithm. Here is a Python code for this problem.

def max_subarray(nums):
    if not nums:
        return 0

    curr_sum = max_sum = nums[0]

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

    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # output: 6

Problem 2: Linked Lists - Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution: We can solve this problem by iteratively reversing the pointers of the linked list.

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Problem 3: Stacks - Valid Parentheses

Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and open brackets must be closed in the correct order.

Solution: This problem can be solved by using a stack.

def isValid(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

print(isValid("()[]{}"))  # output: True

Problem 4: Trees - Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution: This problem can be solved by using a depth-first search (DFS) algorithm.

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

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_height = maxDepth(root.left)
        right_height = maxDepth(root.right)
        return max(left_height, right_height) + 1

Remember to take some time to understand these problems and their solutions. Practice is the key to mastering the use of these data structures. Happy coding!

8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms

Problem 1: Arrays - Maximum Subarray Sum

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

Solution: We can solve this problem using Kadane's algorithm. Here is a Python code for this problem.

def max_subarray(nums):
    if not nums:
        return 0

    curr_sum = max_sum = nums[0]

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

    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # output: 6

Problem 2: Linked Lists - Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution: We can solve this problem by iteratively reversing the pointers of the linked list.

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Problem 3: Stacks - Valid Parentheses

Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and open brackets must be closed in the correct order.

Solution: This problem can be solved by using a stack.

def isValid(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

print(isValid("()[]{}"))  # output: True

Problem 4: Trees - Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution: This problem can be solved by using a depth-first search (DFS) algorithm.

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

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_height = maxDepth(root.left)
        right_height = maxDepth(root.right)
        return max(left_height, right_height) + 1

Remember to take some time to understand these problems and their solutions. Practice is the key to mastering the use of these data structures. Happy coding!

8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms

Problem 1: Arrays - Maximum Subarray Sum

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

Solution: We can solve this problem using Kadane's algorithm. Here is a Python code for this problem.

def max_subarray(nums):
    if not nums:
        return 0

    curr_sum = max_sum = nums[0]

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

    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # output: 6

Problem 2: Linked Lists - Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution: We can solve this problem by iteratively reversing the pointers of the linked list.

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Problem 3: Stacks - Valid Parentheses

Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and open brackets must be closed in the correct order.

Solution: This problem can be solved by using a stack.

def isValid(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

print(isValid("()[]{}"))  # output: True

Problem 4: Trees - Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution: This problem can be solved by using a depth-first search (DFS) algorithm.

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

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_height = maxDepth(root.left)
        right_height = maxDepth(root.right)
        return max(left_height, right_height) + 1

Remember to take some time to understand these problems and their solutions. Practice is the key to mastering the use of these data structures. Happy coding!

8.5 Practice Problems of Chapter 8: Data Structures Used in Algorithms

Problem 1: Arrays - Maximum Subarray Sum

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

Solution: We can solve this problem using Kadane's algorithm. Here is a Python code for this problem.

def max_subarray(nums):
    if not nums:
        return 0

    curr_sum = max_sum = nums[0]

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

    return max_sum

print(max_subarray([-2,1,-3,4,-1,2,1,-5,4]))  # output: 6

Problem 2: Linked Lists - Reverse a Linked List

Problem: Given the head of a singly linked list, reverse the list, and return the reversed list.

Solution: We can solve this problem by iteratively reversing the pointers of the linked list.

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

def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Problem 3: Stacks - Valid Parentheses

Problem: Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and open brackets must be closed in the correct order.

Solution: This problem can be solved by using a stack.

def isValid(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

print(isValid("()[]{}"))  # output: True

Problem 4: Trees - Maximum Depth of Binary Tree

Problem: Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution: This problem can be solved by using a depth-first search (DFS) algorithm.

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

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_height = maxDepth(root.left)
        right_height = maxDepth(root.right)
        return max(left_height, right_height) + 1

Remember to take some time to understand these problems and their solutions. Practice is the key to mastering the use of these data structures. Happy coding!