This function finds a peak element in an array. A peak element is an element that is strictly greater than its neighbors. The array can contain multiple peaks, and the function is guaranteed to find one of them. This is...

The algorithm uses binary search to efficiently find a peak element. The core idea is that if nums[mid] < nums[mid+1], then a peak must exist to the right of mid (including mid+1), so we discard the left half. Conversely, if nums[mid] > nums[mid+1], a peak must exist at or to the left of mid, so we discard the right half. The loop invariant is that a peak element is guaranteed to exist within the range [left, right]. The time complexity is O(log n) because we halve the search space in each iteration. The space complexity is O(1) as we only use a few variables. Edge cases like a single-element array are handled correctly as the loop condition `left < right` will not be met, and `left` (which is 0) will be returned, which is the peak.

function findPeakElement(nums): left = 0 right = length(nums) - 1 while left < right: mid = left + floor((right - left) / 2) if nums[mid] > nums[mid + 1]: right = mid else: left = mid + 1 return left

This function reverses a singly linked list in place. It iterates through the list, changing the direction of each node's pointer to point to the previous node. This is a fundamental operation for manipulating linked lis...

The algorithm reverses a singly linked list iteratively. It uses three pointers: `prev`, `current`, and `nextTemp`. `prev` points to the node that will become the next of the current node (initially nil). `current` points to the node being processed. `nextTemp` temporarily stores the next node in the original list before `current.Next` is modified. In each iteration, `current.Next` is set to `prev`, effectively reversing the link. Then, `prev` is updated to `current`, and `current` is updated to `nextTemp`. This process continues until `current` becomes nil, at which point `prev` points to the new head of the reversed list. The time complexity is O(n), where n is the number of nodes, as each node is visited once. The space complexity is O(1) because only a constant amount of extra space is used for the pointers. Edge cases like an empty list or a list with a single node are handled correctly.

function reverseList(head): prev = null current = head while current is not null: nextTemp = current.next current.next = prev prev = current current = nextTemp return prev

This function finds the kth smallest element in a matrix where each row and column is sorted in ascending order. The matrix can contain duplicate values. This problem is common in competitive programming and algorithm de...

This implementation uses a min-heap to efficiently find the kth smallest element. The heap stores tuples of {value, row_index, col_index}. Initially, the heap is populated with the first element from each row. We then repeatedly extract the minimum element from the heap (k times). After extracting an element, if its row has a next element, that next element is pushed onto the heap. This ensures that we always consider the smallest available elements. The time complexity is O(k log n), where n is the number of rows, because we perform k heap operations, and each heap operation takes O(log n) time. The space complexity is O(n) for storing elements in the heap. Edge cases include an empty matrix or a matrix with only one element. The constraints on k ensure it's within the bounds of the matrix size.

function kthSmallest(matrix, k): n = number of rows in matrix if n is 0: return error or default value minHeap = new MinHeap() // Push the first element of each row into the heap for r from 0 to n-1: if matrix[r] is not...

This function calculates the length of the longest increasing subsequence (LIS) within a given array of integers. An increasing subsequence is a sequence of elements from the array that are in strictly increasing order,...

The algorithm uses dynamic programming to solve the LIS problem. Let dp[i] be the length of the longest increasing subsequence ending at index i. The base case is dp[i] = 1 for all i, as a single element forms an increasing subsequence of length 1. For each element nums[i], we iterate through all previous elements nums[j] (where j < i). If nums[i] > nums[j], it means nums[i] can extend the increasing subsequence ending at nums[j]. We then update dp[i] to be the maximum of its current value and dp[j] + 1. The overall LIS length is the maximum value in the dp array. The time complexity is O(n^2) due to the nested loops, and the space complexity is O(n) for the dp array. Edge cases like an empty array or an array with all identical elements are handled correctly.

function lengthOfLIS(nums): if nums is empty: return 0 dp = array of size length(nums), initialized to 1 for i from 1 to length(nums) - 1: for j from 0 to i - 1: if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j] + 1) return...

This Go program implements a Trie (Prefix Tree), a specialized tree data structure used for efficient retrieval of keys in a dataset of strings. It supports inserting words, searching for exact word matches, and checking...

The Trie implementation uses a `TrieNode` struct, where each node contains an array of pointers to its children (one for each letter of the alphabet) and a boolean flag `isEndOfWord` to indicate if a word terminates at that node. The `Trie` struct holds the root node. The `Insert` method traverses the Trie, creating new nodes for characters that don't exist, and marks the final node of a word. The `Search` method checks if a word exists by traversing the Trie and verifying the `isEndOfWord` flag. The `StartsWith` method checks if a prefix exists by simply traversing the Trie along the prefix path. The time complexity for `Insert`, `Search`, and `StartsWith` is O(L), where L is the length of the word or prefix, as it depends on the depth of the Trie. The space complexity is O(N*L) in the worst case, where N is the number of words and L is the average length of words, as each character of each word might create a new node. Edge cases like inserting or searching for empty strings, and handling prefixes that don't exist, are addressed.

class TrieNode: children: array of TrieNode (size 26) isEndOfWord: boolean class Trie: root: TrieNode function NewTrieNode(): node = new TrieNode() initialize node.children to null node.isEndOfWord = false return node fu...

This Go program identifies the single missing number from an array that contains `n` distinct numbers taken from the range `0` to `n`. It leverages the property of arithmetic series to efficiently calculate the expected...

The `findMissingNumber` function determines the missing number in an array of `n` distinct numbers from the range `0` to `n`. It first calculates the expected sum of all numbers from `0` to `n` using the arithmetic series formula: `n * (n + 1) / 2`. Then, it iterates through the input array `nums` to compute the actual sum of its elements. The difference between the `expectedSum` and `actualSum` reveals the missing number. The time complexity is O(n) because the array is traversed once to calculate the actual sum. The space complexity is O(1) as it uses a constant amount of extra space. Edge cases such as an empty array (where `n=0`) are handled, correctly returning `0` as the missing number in the `0..0` range.

function findMissingNumber(nums): n = length(nums) if n == 0: return 0 expectedSum = n * (n + 1) / 2 actualSum = 0 for each number num in nums: actualSum = actualSum + num return expectedSum - actualSum

This Go program finds a peak element in an array using a binary search approach. A peak element is defined as an element that is strictly greater than its immediate neighbors. This algorithm is useful in scenarios where...

The `findPeakElement` function implements a binary search algorithm to efficiently locate a peak element in an array. The core idea is that if `nums[mid] < nums[mid+1]`, then a peak must exist in the right half of the array (from `mid+1` to `right`), because the array is guaranteed to have at least one peak and conceptually `nums[-1]` and `nums[n]` are negative infinity. Conversely, if `nums[mid] >= nums[mid+1]`, then a peak could be at `mid` or in the left half (from `left` to `mid`). The loop invariant is that a peak element is always present within the range `[left, right]`. The time complexity is O(log n) due to the binary search, and the space complexity is O(1) as it uses a constant amount of extra space. Edge cases like a single-element array are handled. The algorithm terminates when `left == right`, at which point `left` (or `right`) is the index of a peak element.

function findPeakElement(nums): left = 0 right = length(nums) - 1 if length(nums) == 1: return 0 while left < right: mid = left + (right - left) / 2 if nums[mid] < nums[mid + 1]: left = mid + 1 else: right = mid return l...

This Go program counts the occurrences of vowels (a, e, i, o, u) within a given string, irrespective of their case. It utilizes a helper function to determine if a character is a vowel. This is a fundamental string manip...

The `countVowels` function iterates through each character of the input string `s`. For every character, it calls the `isVowel` helper function. The `isVowel` function checks if the character matches any of the lowercase or uppercase vowels using a `switch` statement. If `isVowel` returns `true`, a counter `vowelCount` is incremented. The loop continues until all characters are processed. The time complexity is O(n), where n is the length of the string, because each character is examined once. The space complexity is O(1) as only a few variables are used. An edge case for an empty string is handled, returning 0 vowels.

function countVowels(s): vowelCount = 0 if length(s) == 0: return 0 for each character char in s: if isVowel(char): vowelCount = vowelCount + 1 return vowelCount function isVowel(char): if char is 'a', 'e', 'i', 'o', 'u'...