This Lua code implements the Merge Sort algorithm, a highly efficient, comparison-based sorting technique. It recursively divides the input array into halves, sorts them, and then merges the sorted halves. Merge Sort is...

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` function. The `merge` function takes two sorted arrays and combines them into a single sorted array. It uses two pointers, `i` and `j`, to iterate through `left` and `right` respectively. It compares elements from both arrays and inserts the smaller element into the `result` array, advancing the corresponding pointer. After one of the arrays is exhausted, any remaining elements from the other array are appended. The time complexity of Merge Sort is O(n log n) due to the recursive division and linear merging steps. The space complexity is O(n) because of the auxiliary space required for the `result` array during merging and for storing the subarrays in recursive calls.

function mergeSort(array): if length(array) <= 1: return array calculate mid_point = floor(length(array) / 2) create left_half from array[1 to mid_point] create right_half from array[mid_point + 1 to end] sorted_left = m...

This function reverses a given string in Lua. It iterates through the string from the last character to the first, appending each character to a new string. This is a fundamental string manipulation task useful in variou...

The `reverseString` function takes a string as input and returns its reversed version. It first checks for nil or empty string inputs, returning an empty string in those edge cases. The core logic involves a `for` loop that iterates backward from the length of the string down to 1. In each iteration, `string.sub` extracts a single character, which is then concatenated to the `reversed` string. The time complexity is O(n), where n is the length of the string, due to the single pass. The space complexity is also O(n) because a new string of length n is created. The invariant maintained is that `reversed` always holds the reversed prefix of the processed part of the original string.

function reverseString(input_string): if input_string is nil or empty: return empty_string initialize reversed_string as empty for index from length(input_string) down to 1: append character at index from input_string to...

This Lua code implements binary search to find a target value in a sorted array. It includes a helper function to find the first occurrence of the target if duplicates exist. Binary search is highly efficient for searchi...

The `binarySearch` function efficiently finds a `target` in a sorted `arr`ay. It initializes `low` and `high` pointers to the array boundaries. The `while` loop continues as long as `low` is less than or equal to `high`. In each iteration, it calculates the `mid` index and compares `arr[mid]` with the `target`. If they match, the index is returned. If `arr[mid]` is less than `target`, the search continues in the right half (`low = mid + 1`). Otherwise, it searches the left half (`high = mid - 1`). If the loop finishes without finding the target, -1 is returned. The `findFirstOccurrence` helper uses `binarySearch` and then backtracks to find the earliest index of the target. Time complexity is O(log n) for `binarySearch` and O(log n) in the worst case for `findFirstOccurrence` (if all elements are the target). Space complexity is O(1) for both.

function binarySearch(array, target_value): set low = 1 set high = length(array) if array is empty: return -1 while low <= high: calculate mid = floor((low + high) / 2) if array[mid] == target_value: return mid else if a...

This Lua code calculates the factorial of a non-negative integer. It provides both an iterative approach and a recursive approach with memoization. Factorial is a fundamental mathematical concept used in combinatorics, p...

The `calculateFactorial` function computes n! iteratively. It first handles edge cases: returning `nil` for negative inputs and `1` for `n=0`. For positive `n`, it initializes `result` to 1 and iterates from 1 to `n`, multiplying `result` by the current loop variable `i`. The time complexity is O(n) because of the single loop. The space complexity is O(1) as it only uses a few variables. The `factorialWithMemoization` function uses recursion with a memoization table (`memo`) to store previously computed factorial values. This avoids redundant calculations, making it more efficient for repeated calls with the same arguments. The time complexity with memoization becomes O(n) for the first call and O(1) for subsequent calls with already computed values. The space complexity is O(n) due to the memoization table and recursion depth.

function calculateFactorial(number): if number < 0: return invalid_input_indicator if number == 0: return 1 initialize result = 1 for i from 1 to number: result = result * i return result function factorialWithMemoizatio...

This Lua code implements insertion into a Binary Search Tree (BST). It defines a `TreeNode` structure and a `BinarySearchTree` class. The `insert` method handles the initial empty tree case and then delegates to a recurs...

The `BinarySearchTree` implementation uses a recursive approach for insertion. The `TreeNode` metatable defines the structure of each node, containing a key, value, and references to left and right children. The `insert` method checks if the tree is empty; if so, it creates the root node. Otherwise, it calls `insert_recursive`. This recursive function compares the new key with the current node's key. If the new key is smaller, it attempts to insert into the left subtree; if larger, into the right subtree. If a child is `nil`, a new `TreeNode` is created and attached. If the key already exists, the node's value is updated. The time complexity for insertion is O(h), where h is the height of the tree. In the worst case (a skewed tree), h can be n, leading to O(n) complexity. In a balanced tree, h is O(log n), giving O(log n) complexity. The space complexity is O(h) due to the recursion stack. The `in_order_traversal` helper has O(n) time and O(h) space complexity. The BST property (left < parent < right) is maintained by the insertion logic.

define TreeNode with key, value, left, right define BinarySearchTree with root function BinarySearchTree.insert(key, value): if root is nil: root = new TreeNode(key, value) else: call insert_recursive(root, key, value) f...

This Lua code generates a Fibonacci sequence up to a specified number of terms. It iteratively calculates each subsequent number by summing the two preceding ones. The code includes a helper function to retrieve only the...

The `fibonacci_sequence` function generates the first `n` Fibonacci numbers. It handles negative input by raising an error and returns an empty table for `n=0`. For `n=1`, it returns a table containing only 0. For `n > 1`, it initializes `a=0` and `b=1`, then iteratively calculates the next Fibonacci number by summing `a` and `b`. The values of `a` and `b` are updated in each iteration. A basic check for potential number overflow is included, though Lua's standard number type (double-precision float) can handle quite large values. The time complexity is O(n) as it iterates `n` times. The space complexity is O(n) for storing the sequence in a table. The `get_nth_fibonacci` helper function also has O(n) time complexity but O(1) space complexity, as it only stores the last two numbers. The invariant is that `a` and `b` always hold the two most recent Fibonacci numbers needed for the next calculation.

function fibonacci_sequence(n): if n < 0: raise error "Input must be non-negative" if n == 0: return empty list initialize sequence list a = 0 b = 1 add a to sequence if n == 1: return sequence add b to sequence for i fr...

This Lua code implements a Queue data structure using a circular buffer. This approach is memory-efficient as it reuses space in a fixed-size array. The `enqueue` operation adds an item to the rear, and `dequeue` removes...

The `CircularBufferQueue` uses a fixed-size array (`buffer`) and two pointers, `front` and `rear`, to manage queue operations. `front` points to the first element, and `rear` points to the next available slot. The `capacity` defines the maximum number of elements. When `rear` reaches the end of the array, it wraps around to the beginning using the modulo operator (`% self.capacity`). Similarly, `front` wraps around. The `size` variable tracks the current number of elements. `enqueue` adds an item at `rear` and increments `rear`. `dequeue` retrieves the item at `front`, clears the slot (optional), and increments `front`. Both operations update `size`. The time complexity for `enqueue`, `dequeue`, `peek`, `is_empty`, `is_full`, and `get_size` is O(1) because they involve a constant number of operations regardless of the queue size. The space complexity is O(capacity) because the buffer size is fixed. The invariant is that `size` accurately reflects the number of elements between `front` (inclusive) and `rear` (exclusive), considering wrap-around.

define CircularBufferQueue with capacity, buffer, front, rear, size function CircularBufferQueue.new(capacity): initialize queue with capacity, empty buffer, front=0, rear=0, size=0 return queue function CircularBufferQu...

This Lua code defines a function to reverse a given string. It first converts the string into a table of characters, then uses a two-pointer approach with a helper function to swap characters from the ends inwards. This...

The `reverse_string` function takes a string `s` and returns its reversed version. It handles the edge case of an empty or nil string by returning an empty string. The string is converted into a table of individual characters for easier manipulation. Two pointers, `left` and `right`, are initialized to the beginning and end of the table, respectively. The `while` loop continues as long as `left` is less than `right`. Inside the loop, the `swap_chars` helper function exchanges the characters at the `left` and `right` indices. The pointers are then moved inwards. This process guarantees that each character is swapped exactly once with its counterpart from the other end. The time complexity is O(n) because each character is accessed and swapped a constant number of times, where n is the length of the string. The space complexity is also O(n) due to the creation of the character table. The invariant maintained is that the portion of the string outside the `left` and `right` pointers remains reversed.

function reverse_string(s): if s is nil or empty: return "" convert s to a table of characters (char_table) initialize left pointer to 1 initialize right pointer to length of char_table while left < right: swap character...