This implementation simulates a queue data structure using two stacks. A queue follows the First-In, First-Out (FIFO) principle, while stacks follow Last-In, First-Out (LIFO). This approach is a classic exercise in under...

The `MyQueue` class uses two stacks: `enqueueStack` and `dequeueStack`. When an element is enqueued, it's simply pushed onto `enqueueStack`. When `dequeue` or `peek` is called, if `dequeueStack` is empty, all elements from `enqueueStack` are popped and pushed onto `dequeueStack`. This reverses the order, making the oldest element accessible at the top of `dequeueStack`. The `empty` method checks if both stacks are empty. The amortized time complexity for `enqueue` is O(1). The amortized time complexity for `dequeue` and `peek` is O(1) because each element is moved from `enqueueStack` to `dequeueStack` at most once. In the worst case, a single `dequeue` or `peek` operation could be O(n) if all elements need to be transferred. The space complexity is O(n) to store the elements.

class MyQueue: initialize enqueueStack as empty stack initialize dequeueStack as empty stack method enqueue(x): push x onto enqueueStack method dequeue(): if dequeueStack is empty: if enqueueStack is empty: throw error "...

This function finds the starting and ending indices of a given target value in a sorted array of integers. If the target is not found in the array, it returns `[-1, -1]`. This problem is a variation of binary search, req...

The algorithm uses two modified binary searches. The first search aims to find the leftmost (first) occurrence of the target. When `nums[mid] == target`, we record `mid` as a potential `firstPos` and continue searching in the left half (`right = mid - 1`) to find an even earlier occurrence. If `nums[mid] < target`, we search the right half (`left = mid + 1`); otherwise, we search the left half (`right = mid - 1`). The second search finds the rightmost (last) occurrence. When `nums[mid] == target`, we record `mid` as a potential `lastPos` and continue searching in the right half (`left = mid + 1`) for a later occurrence. If `nums[mid] < target`, we search the right half (`left = mid + 1`); otherwise, we search the left half (`right = mid - 1`). If the first search doesn't find the target (`firstPos == -1`), the target is not present, and `[-1, -1]` is returned. Otherwise, the results of both searches are combined into the `result` array. Both searches have a time complexity of O(log n), making the overall time complexity O(log n). The space complexity is O(1) as only a few variables are used.

function searchRange(nums, target): result = [-1, -1] if nums is empty: return result // Find first occurrence left = 0 right = length of nums - 1 firstPos = -1 while left <= right: mid = left + (right - left) / 2 if num...

This code performs an inorder traversal of a binary tree. Inorder traversal visits nodes in the order: left subtree, root node, then right subtree. This traversal is particularly useful for binary search trees (BSTs) bec...

The `inorderTraversal` function initializes an empty mutable list `result` and calls a recursive helper function `inorderHelper`. The `inorderHelper` function takes a `TreeNode` and the `result` list. The base case for the recursion is when `node` is `null`, meaning we've gone past a leaf node, and the function simply returns. Otherwise, it first recursively calls itself on the `node.left` child. After the left subtree has been fully traversed and its values added to `result`, the value of the current `node` is added to `result`. Finally, it recursively calls itself on the `node.right` child. This ensures the left-root-right visiting order characteristic of inorder traversal. The time complexity is O(n), where n is the number of nodes, because each node is visited exactly once. The space complexity is O(h) in the average case (for a balanced tree) and O(n) in the worst case (for a skewed tree), due to the recursion stack depth, plus O(n) for the result list.

class TreeNode: value: Int left: TreeNode or null right: TreeNode or null function inorderTraversal(root): result = empty list inorderHelper(root, result) return result function inorderHelper(node, result): if node is nu...

This function finds a peak element in an array. A peak element is an element that is strictly greater than its neighbors. The array may contain multiple peaks; in that case, returning the index to any one of the peaks is...

The algorithm employs a binary search approach to find a peak element in an array. It iteratively narrows down the search space by comparing the middle element with its right neighbor. If the middle element is greater than its right neighbor, it implies that a peak might exist in the left half (including the middle element), so the search space is reduced to the left. Otherwise, the peak must be in the right half, and the search space is adjusted accordingly. The loop continues until the left and right pointers converge, at which point the index `left` (or `right`) points to a peak element. 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 an empty array or an array with a single element are handled. The correctness relies on the invariant that a peak element always exists within the current search range.

function findPeakElement(array): if array is empty: throw error if array has one element: return index 0 left = 0 right = length of array - 1 while left < right: mid = left + (right - left) / 2 if array[mid] > array[mid...

This function implements the Bubble Sort algorithm to sort an array of integers in ascending order. It repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass...

Bubble Sort works by repeatedly stepping through the list, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The outer loop runs `n-1` times, and the inner loop performs comparisons and swaps. In the worst-case scenario (a reverse-sorted array), Bubble Sort performs O(n^2) comparisons and O(n^2) swaps. In the best-case scenario (an already sorted array), with the optimization of checking for swaps, it performs O(n) comparisons and O(1) swaps. The space complexity is O(1) because it sorts the array in-place. The algorithm's correctness is based on the fact that each pass guarantees that the largest unsorted element 'bubbles up' to its correct position at the end of the unsorted portion of the array. Edge cases such as an empty array or an array with a single element are handled by an initial check.

function bubbleSort(array): n = length of array if n <= 1: return repeat: swapped = false for i from 0 to n-2: if array[i] > array[i+1]: swap array[i] and array[i+1] swapped = true n = n - 1 // Optimization: last element...

This class provides a solution to the N-Queens problem using a backtracking algorithm. The N-Queens puzzle is the challenge of placing N non-attacking queens on an N×N chessboard. This means no two queens should share th...

The N-Queens problem is solved using a recursive backtracking approach. The `solveNQueens` function initializes the board and a list to store solutions, then calls the recursive `solve` function starting from the first row. The `solve` function attempts to place a queen in each column of the current `row`. Before placing a queen, it calls `isSafe` to check if the position is valid (i.e., not attacked by any previously placed queens). If a position is safe, a queen is placed, and the function recursively calls itself for the next row (`row + 1`). If placing a queen in a certain column does not lead to a solution, the algorithm backtracks by removing the queen (resetting the cell to empty) and trying the next column. The base case for the recursion is when all `n` queens have been successfully placed (`row == n`), at which point the current board configuration is formatted and added to the list of solutions. The `isSafe` function checks for conflicts in the same column, and both upper diagonals. The time complexity is roughly O(N!), as in the worst case, it might explore all permutations, though pruning significantly reduces the actual search space. The space complexity is O(N^2) for the board and O(N) for the recursion depth, plus space for storing solutions. Edge cases like N=1 are implicitly handled. The correctness is guaranteed by the exhaustive search and pruning of invalid states.

class NQueensSolver: board = N x N grid, initialized to empty solutions = empty list N = board size function solveNQueens(N): initialize board and solutions call solve(0) return solutions function solve(row): if row == N...

This function calculates the length of the longest common subsequence (LCS) between two strings. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the...

The algorithm uses dynamic programming to solve the Longest Common Subsequence problem. A 2D array `dp` is created where `dp[i][j]` represents 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 the `i`-th character of `text1` matches the `j`-th character of `text2`, then `dp[i][j]` is one plus the LCS of the strings excluding these characters (`dp[i-1][j-1] + 1`). If they don't match, `dp[i][j]` is the maximum of the LCS obtained by excluding the `i`-th character of `text1` (`dp[i-1][j]`) or the `j`-th character of `text2` (`dp[i][j-1]`). The base cases `dp[0][j]` and `dp[i][0]` are initialized to 0, representing the LCS with an empty string. The final result is `dp[m][n]`. The time complexity is O(m*n) and the space complexity is O(m*n), where m and n are the lengths of the two strings. Edge cases like empty strings are handled by the initialization of the DP table.

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

This algorithm counts the occurrences of vowels (a, e, i, o, u) within a given string, ignoring case. It's a fundamental string processing task often used in natural language processing, text analysis, and basic programm...

The `countVowels` function iterates through each character of the input string. For every character, it converts it to lowercase to ensure case-insensitivity. It then checks if this lowercase character exists within a predefined set of vowels ('a', 'e', 'i', 'o', 'u'). If a match is found, a counter is incremented. The function handles edge cases such as null or empty strings by returning 0 immediately. The time complexity is O(n), where n is the length of the string, because each character is processed once. The space complexity is O(1) (or O(k) where k is the number of vowels, which is constant) as it only uses a small, fixed-size set for vowel lookup.

function countVowels(text): if text is null or empty: return 0 vowelCount = 0 vowels = set of 'a', 'e', 'i', 'o', 'u' for each character in text: lowerChar = convert character to lowercase if lowerChar is in vowels: vowe...