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

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

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

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