This R function removes duplicate elements from a sorted array in-place. It iterates through the array using two pointers: one (`i`) to scan through all elements and another (`unique_idx`) to keep track of the position w...

The `remove_duplicates` function has a time complexity of O(n) because it iterates through the array once. The space complexity is O(1) as it modifies the array in-place without using any significant auxiliary data structures. The `unique_idx` pointer effectively partitions the array: elements from index 1 to `unique_idx` are unique, while elements beyond `unique_idx` are either duplicates or unprocessed. When `nums[i]` is found to be different from `nums[unique_idx]`, it means `nums[i]` is a new unique element. We then increment `unique_idx` and copy `nums[i]` to `nums[unique_idx]`. Edge cases include empty arrays (returning 0) and arrays with a single element (returning 1). The invariant is that the subarray `nums[1...unique_idx]` always contains unique elements in their original relative order.

function remove_duplicates(array): n = length of array if n == 0: return 0 if n == 1: return 1 unique_idx = 1 for i from 2 to n: if array[i] != array[unique_idx]: unique_idx = unique_idx + 1 array[unique_idx] = array[i]...

This R code implements the merge sort algorithm, a highly efficient, comparison-based sorting technique. It works by recursively dividing the input array into smaller halves, sorting them, and then merging the sorted hal...

Merge sort operates on the divide-and-conquer principle. The `merge_sort` function recursively splits the array until subarrays of size 0 or 1 are reached, which are inherently sorted. The `merge_sorted_arrays` helper function then efficiently combines two already sorted subarrays into a single sorted array. This merging process involves comparing elements from both subarrays and placing the smaller one into the result. The time complexity is O(n log n) in all cases (best, average, and worst) because the array is always divided into halves, and the merge step takes linear time. The space complexity is O(n) due to the auxiliary space required for the merged array during the merge operation. Edge cases like empty arrays or arrays with a single element are handled by the base case in `merge_sort`, ensuring correct termination. The invariant maintained is that at each step of the merge, the `merged_array` up to index `k-1` is sorted, and the remaining elements in `left` and `right` are also sorted.

function merge_sort(array): if length of array <= 1: return array find middle index left_half = array from start to middle right_half = array from middle+1 to end sorted_left = merge_sort(left_half) sorted_right = merge_...

This R function efficiently finds a peak element in an array using a modified binary search. A peak element is defined as an element that is strictly greater than its neighbors. The algorithm leverages the property that...

The `find_peak_element` function uses binary search to locate a peak element in O(log n) time complexity. The space complexity is O(1) as it only uses a few variables. The core idea is to compare the middle element `nums[mid]` with its right neighbor `nums[mid + 1]`. If `nums[mid] < nums[mid + 1]`, it implies that a peak must exist in the right half of the array because the sequence is increasing. Conversely, if `nums[mid] >= nums[mid + 1]`, a peak must exist in the left half (including `mid` itself) because the sequence is either decreasing or has reached a plateau. Edge cases include empty arrays (returning NULL) and single-element arrays (returning the element itself). The loop invariant is that a peak element is guaranteed to exist within the range `[left, right]`.

function find_peak_element(array): n = length of array if n == 0: return NULL if n == 1: return array[1] left = 1 right = n while left < right: mid = floor((left + right) / 2) if array[mid] > array[mid + 1]: # Peak is in...

This R code defines a Trie (prefix tree) data structure using the R6 object-oriented system. A Trie is a tree-like data structure used for efficient retrieval of keys in a dataset of strings. It's particularly useful for...

The Trie data structure provides efficient string operations. Each node in the Trie represents a character, and paths from the root to a node represent prefixes. The `insert` method traverses the Trie, creating new nodes for characters not yet present, and marks the end of a word. The `search_prefix` method checks if a given prefix exists by traversing the Trie. If the traversal completes successfully, the prefix exists. The time complexity for both insertion and prefix search is O(L), where L is the length of the word or prefix, as we visit at most L nodes. The space complexity is O(N * L_avg), where N is the number of words and L_avg is the average length of words, as each character in each word might create a new node. Edge cases handled include empty strings (ignored or specially handled) and attempting to search for a prefix that doesn't exist. The invariant is that any path from the root to a node corresponds to a valid prefix of at least one inserted word.

class TrieNode: children = map of char to TrieNode isEndOfWord = boolean class Trie: root = TrieNode function initialize(): root = new TrieNode() function insert(word): if word is empty: return node = root for each chara...

This R implementation uses Kadane's algorithm to efficiently find the maximum sum of a contiguous subarray within a given numeric vector. This problem is a classic in algorithm design and has applications in financial an...

Kadane's algorithm is a dynamic programming approach that solves the maximum subarray sum problem in linear time. It maintains two variables: `current_max` (the maximum sum ending at the current position) and `max_so_far` (the overall maximum sum found anywhere in the array). For each element `nums[i]`, `current_max` is updated to be the maximum of `nums[i]` itself (starting a new subarray) or `current_max + nums[i]` (extending the current subarray). `max_so_far` is then updated to be the maximum of its current value and `current_max`. The algorithm correctly handles arrays with all negative numbers by ensuring `max_so_far` is initialized with the first element and `current_max` is updated appropriately. The time complexity is O(n) because it involves a single pass through the array. The space complexity is O(1) as it uses a fixed amount of extra space regardless of the input size. Edge cases such as empty arrays or arrays with a single element are handled explicitly.

function max_subarray_sum(nums): if nums is empty: return 0 if length(nums) is 1: return nums[1] max_so_far = nums[1] current_max = nums[1] for i from 2 to length(nums): current_max = max(nums[i], current_max + nums[i])...

This R function implements a modified binary search to find the index of the first occurrence of a target value in a sorted numeric vector. Standard binary search finds any occurrence, but this version is optimized to lo...

The `find_first_occurrence` function uses a binary search strategy adapted to find the first occurrence of a `target` in a `sorted_vec`. It initializes `low` to the first index (1 in R's 1-based indexing) and `high` to the last index. The `result_index` is initialized to -1, indicating the target has not been found. The `while` loop continues as long as `low` is less than or equal to `high`. Inside the loop, `mid` is calculated. If `sorted_vec[mid]` equals `target`, we've found a potential first occurrence. We store this `mid` in `result_index` and then crucially set `high` to `mid - 1` to continue searching in the left half for an even earlier occurrence. If `sorted_vec[mid]` is less than `target`, the target must be in the right half, so `low` is updated. If `sorted_vec[mid]` is greater than `target`, the target must be in the left half, so `high` is updated. After the loop, if `result_index` is not -1, it means a target was found, and we return `result_index - 1` to convert it to a 0-based index. Otherwise, -1 is returned. The time complexity is O(log n) due to the binary search nature. The space complexity is O(1) as it uses a constant amount of extra space.

function find_first_occurrence(sorted_vec, target): low = 1 high = length(sorted_vec) result_index = -1 if length(sorted_vec) is 0: return -1 while low <= high: mid = floor((low + high) / 2) if sorted_vec[mid] == target:...

This R function computes the sum of all numeric elements within a given vector. It iterates through each number in the vector and accumulates their total. This is a fundamental operation used in statistical analysis, dat...

The `sum_vector_elements` function calculates the sum of elements in a numeric vector. It initializes a variable `total_sum` to 0. Then, it iterates through the input vector `numbers` using a `for` loop, from the first element to the last. In each iteration, the current element `numbers[i]` is added to `total_sum`. After the loop finishes, `total_sum` holds the sum of all elements. The function includes an edge case check for an empty vector; if the vector is empty, it immediately returns 0, preventing errors. The time complexity is O(n), where n is the number of elements in the vector, because each element is visited exactly once. The space complexity is O(1) as it only uses a constant amount of extra space for the `total_sum` variable and loop counter.

function sum_vector_elements(numbers): if length(numbers) is 0: return 0 total_sum = 0 for i from 1 to length(numbers): total_sum = total_sum + numbers[i] return total_sum

This R function calculates the Longest Common Subsequence (LCS) of two strings using dynamic programming. The LCS is the longest sequence of characters that appear in the same order in both strings, but not necessarily c...

The `longest_common_subsequence` function implements a classic dynamic programming approach to find the LCS. It constructs a 2D table `dp` where `dp[i, j]` stores the length of the LCS of the first `i` characters of `text1` and the first `j` characters of `text2`. The table is filled iteratively. If `text1[i]` equals `text2[j]`, the LCS length increases by one from the diagonal element `dp[i-1, j-1]`. Otherwise, it takes the maximum from the element above (`dp[i-1, j]`) or to the left (`dp[i, j-1]`). The base cases are when either string is empty, resulting in an LCS length of 0. After filling the table, the LCS string is reconstructed by backtracking from the bottom-right corner of the `dp` table. The time complexity is O(n*m) where n and m are the lengths of the input strings, due to the nested loops filling the DP table. The space complexity is also O(n*m) for storing the DP table. Edge cases like empty input strings are handled by returning an empty LCS.

function longest_common_subsequence(text1, text2): n = length(text1) m = length(text2) create dp table of size (n+1)x(m+1) initialized to 0 for i from 1 to n: for j from 1 to m: if text1[i] == text2[j]: dp[i+1, j+1] = dp...