This Scala function determines if a string is a palindrome, meaning it reads the same forwards and backward. It first cleans the input string by converting it to lowercase and removing all non-alphanumeric characters. Th...

The `isPalindrome` function first cleans the input string `s` by converting it to lowercase and removing any characters that are not letters or numbers using `toLowerCase` and `replaceAll`. An empty cleaned string is considered a palindrome. It then uses two pointers, `left` starting at the beginning and `right` at the end of the cleaned string. The `while` loop continues as long as `left` is less than `right`. Inside the loop, it compares the characters at `left` and `right`. If they don't match, the string is not a palindrome, and `false` is returned. If they match, the pointers are moved inwards (`left` increments, `right` decrements). If the loop completes without finding mismatches, the string is a palindrome, and `true` is returned. Time complexity is O(n) due to cleaning and traversal, where n is the length of the original string. Space complexity is O(n) in the worst case for the cleaned string.

function isPalindrome(s): cleaned_s = toLowerCase(s) cleaned_s = removeNonAlphanumeric(cleaned_s) left = 0 right = length(cleaned_s) - 1 while left < right: if cleaned_s[left] != cleaned_s[right]: return false left = lef...

This Scala code implements the Merge Sort algorithm, a classic divide-and-conquer sorting technique. It recursively divides the input array into halves until each subarray contains only one element, then merges these sor...

The `mergeSort` function recursively sorts an array. The base case is when the array has 0 or 1 element, in which case it's already sorted. Otherwise, it splits the array into two halves (`left` and `right`), recursively sorts each half, and then merges the two sorted halves using the `merge` helper function. The `merge` function takes two sorted arrays and combines them into a single sorted array. It uses three pointers: `i` for the left array, `j` for the right array, and `k` for the merged array. It iteratively compares elements from `left` and `right`, placing the smaller element into `merged` and advancing the corresponding pointers. After one of the arrays is exhausted, it copies the remaining elements from the other array. The time complexity of Merge Sort is O(n log n) because the array is divided logarithmically, and the merge step takes linear time. The space complexity is O(n) due to the auxiliary space required for the merged array.

function mergeSort(arr): if length(arr) <= 1: return arr mid = length(arr) / 2 left_half = arr[0 to mid-1] right_half = arr[mid to end] sorted_left = mergeSort(left_half) sorted_right = mergeSort(right_half) return merge...

This Scala function calculates the sum of all integers within a given list. It handles the edge case of an empty list by returning zero. This is a fundamental operation used in many data analysis and aggregation tasks.

The `sumList` function iterates through each element of the input `List[Int]`. It initializes a `total` variable to 0. If the list is empty, it immediately returns 0, which is a crucial edge case. Otherwise, it adds each number to the `total`. The loop correctly traverses all elements. The time complexity is O(n) where n is the number of elements in the list, as each element is visited once. The space complexity is O(1) as only a constant amount of extra space is used for the `total` variable.

function sumList(numbers): initialize total to 0 if numbers is empty: return 0 for each number in numbers: add number to total return total

This Scala code defines a Binary Search Tree (BST) and provides a function to insert new nodes. The `insert` function recursively finds the correct position for the new value while maintaining the BST property: all nodes...

The `insert` function takes an optional root node and a value to insert. If the root is `None` (empty tree), it creates a new `TreeNode` with the value and returns it. Otherwise, it compares the value with the current node's value. If the value is less, it recursively calls `insert` on the left child; if greater, it calls `insert` on the right child. If the value is equal, it does nothing, effectively preventing duplicates. The base case for the recursion is when `root` is `None`. The `inorderTraversal` helper function demonstrates how to retrieve elements in sorted order. Time complexity for insertion is O(h), where h is the height of the tree, which is O(log n) for a balanced BST and O(n) for a skewed BST. Space complexity is O(h) due to recursion stack depth.

function insert(root, value): if root is null: return new TreeNode(value) if value < root.value: root.left = insert(root.left, value) else if value > root.value: root.right = insert(root.right, value) // If value == root...

This Scala program calculates the factorial of a non-negative integer using a tail-recursive helper function. Tail recursion is a specific form of recursion where the recursive call is the very last operation in the func...

The `factorial` function first checks for invalid input (negative numbers) and throws an exception if found. It then calls the `factorialHelper` function, passing the input number `n` and an initial accumulator value of 1. The `factorialHelper` function is annotated with `@scala.annotation.tailrec`, signaling the compiler to optimize it. The base case for the recursion is when `n` equals 0, at which point the accumulated result is returned. Otherwise, the function calls itself with `n-1` and the accumulator multiplied by `n`. This process continues until `n` reaches 0. The time complexity is O(n) because each number from n down to 1 is processed once. The space complexity is O(1) due to tail call optimization, as it uses a constant amount of stack space, effectively behaving like an iterative loop. Edge cases handled include negative input and the factorial of 0, which is 1. The correctness is maintained by the invariant that `accumulator * n!` is always preserved throughout the recursive calls.

function factorial(n): if n < 0: throw error "Factorial not defined for negative numbers" return factorial_helper(n, 1) function factorial_helper(n, accumulator): if n == 0: return accumulator else: return factorial_help...

This Scala program reverses a string using a straightforward recursive function. The function operates by taking the first character of the string, recursively reversing the remainder of the string, and then concatenatin...

The `reverseString` function handles three cases: null or empty strings, single-character strings, and strings with multiple characters. For null or empty strings, it returns an empty string. For a single-character string, it returns the string itself as it's already reversed. For longer strings, it recursively calls `reverseString` on the substring starting from the second character (`str.substring(1)`) and then appends the first character (`str.charAt(0)`) to the result. This process continues until the base case of an empty string is reached. The time complexity is O(n^2) due to string concatenation in each recursive call, where n is the length of the string. A more efficient O(n) solution would use a mutable `StringBuilder` or an iterative approach. The space complexity is O(n) due to the recursion depth, which can lead to stack overflow for very long strings. Edge cases handled include null input, empty strings, and single-character strings.

function reverse_string(str): if str is null or empty: return "" else if length(str) == 1: return str else: return reverse_string(substring(str, 1, end)) + first_character(str)

This Scala program implements a linear search algorithm to find the index of a target integer within an array. It iterates through the array element by element, comparing each element to the target value. If a match is f...

The `linearSearch` function iterates through the input array `arr` using `arr.view.zipWithIndex`, which provides both the element and its index. For each element, it checks if it equals the `target`. If a match is found, the current `index` is returned immediately, demonstrating an early exit. If the loop completes without finding the `target`, it means the element is not in the array, and the function returns -1. The time complexity of linear search is O(n) in the worst case (when the element is at the end or not present) and O(1) in the best case (when the element is at the beginning). The space complexity is O(1) as it uses a constant amount of extra space. Edge cases handled include an empty array, the target being the first or last element, and the target not being present.

function linear_search(array, target): for each element at index in array: if element == target: return index return -1

This Scala program implements the binary search algorithm to find the index of a target element within a sorted array of integers. Binary search works by repeatedly dividing the search interval in half. If the value of t...

The `binarySearch` function initializes `low` to 0 and `high` to the last index of the array. It handles the edge case of an empty array by returning -1 immediately. The `while` loop continues as long as `low` is less than or equal to `high`. Inside the loop, the `mid` index is calculated to prevent potential integer overflow. If the element at `mid` matches the `target`, its index is returned. If the element at `mid` is less than the `target`, the search continues in the right half by setting `low` to `mid + 1`. Otherwise, the search continues in the left half by setting `high` to `mid - 1`. If the loop finishes without finding the target, -1 is returned. The time complexity is O(log n) because the search space is halved in each iteration. The space complexity is O(1) as it uses a constant amount of extra space. Edge cases include an empty array, the target being the first or last element, and the target not being present.

function binary_search(array, target): low = 0 high = length(array) - 1 if array is empty: return -1 while low <= high: mid = low + (high - low) / 2 if array[mid] == target: return mid else if array[mid] < target: low =...