This C++ code implements a linear search algorithm using a sentinel value. The sentinel is an extra element appended to the array (or a copy of it) that is guaranteed to match the target value. This simplifies the loop c...

The `linearSearchSentinel` function utilizes a sentinel value to simplify the linear search process. It creates a temporary copy of the input array `arr` and appends the `target` value to this copy, effectively making the `target` the sentinel. The `linearSearchSentinelHelper` then iterates through this augmented array using a single `while` loop condition: `tempArr[i] != target`. This loop is guaranteed to terminate because the `target` is present at least once (as the sentinel). After the loop, it checks if the index `i` is less than `n - 1` (where `n` is the size of the augmented array). If `i < n - 1`, it means the `target` was found within the original portion of the array, and its index `i` is returned. Otherwise, if `i == n - 1`, it implies that the `target` was only found at the sentinel position, meaning it was not present in the original array, and -1 is returned. The time complexity is O(n) in the worst case, where n is the size of the original array, as it might need to scan through all elements plus the sentinel. The space complexity is O(n) due to the creation of a temporary copy of the array. This approach is a variation of linear search that can sometimes offer minor performance improvements by simplifying loop logic, especially in languages where array bounds checking is expensive.

function linearSearchSentinel(array, target): if array is empty: return -1 // Create a temporary array with the target appended as a sentinel temp_array = copy of array append target to temp_array n = length of temp_arra...

This C++ code implements a modified binary search algorithm to find the index of the first occurrence of a given target value within a sorted array. It's crucial for efficiently locating elements in large, ordered datase...

The `findFirstOccurrence` function utilizes a binary search approach to locate the target. The core logic resides in `findFirstOccurrenceHelper`, which iteratively narrows down the search space. When a potential match is found (`arr[mid] == target`), the index is recorded, and the search continues in the left half (`high = mid - 1`) to find an even earlier occurrence. If `arr[mid]` is less than the target, the search moves to the right half (`low = mid + 1`); otherwise, it moves to the left (`high = mid - 1`). The algorithm handles edge cases like an empty array and targets outside the array's range. 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. The loop invariant is that the target, if present, must lie within the `[low, high]` range, and `result` always stores the index of the leftmost `target` found so far.

function findFirstOccurrence(array, target): if array is empty: return -1 if target is less than first element or greater than last element: return -1 return findFirstOccurrenceHelper(array, target, 0, array.size() - 1)...

This C++ code provides a function to reverse a string in-place, meaning it modifies the original string directly without creating a new one. This is a fundamental string manipulation technique used in various application...

The `reverseString` function reverses a given `std::string` by employing a two-pointer approach. It initializes a `left` pointer at the beginning of the string and a `right` pointer at the end. The `while` loop continues as long as `left` is less than `right`. Inside the loop, the characters pointed to by `left` and `right` are swapped using the `swapChars` helper function. Subsequently, `left` is incremented, and `right` is decremented, moving the pointers towards the center of the string. This process effectively swaps characters from the outer ends inwards until the entire string is reversed. The time complexity is O(n), where n is the length of the string, because each character is swapped at most once. The space complexity is O(1) as the reversal is done in-place, requiring only a constant amount of extra memory for the pointers and temporary swap variable. The loop invariant is that the substring `str[0...left-1]` and `str[right+1...n-1]` are already reversed, and the characters within `str[left...right]` are yet to be processed.

function reverseString(string s): if s is empty: return left = 0 right = length(s) - 1 while left < right: swap characters at s[left] and s[right] increment left decrement right

This C++ code implements Breadth-First Search (BFS) for a graph represented by an adjacency list. BFS systematically explores a graph level by level, making it ideal for finding the shortest path in terms of the number o...

The `Graph` class uses `std::map` for its adjacency list, where keys are nodes and values are vectors of their neighbors. The `bfs` function initiates the traversal from a `startNode`. It uses a `std::queue` to manage nodes to visit and an `std::unordered_set` to keep track of visited nodes, preventing cycles and redundant processing. The `bfsHelper` function performs the core traversal, adding the start node to the queue and visited set, then iteratively dequeuing a node, processing it, and enqueuing its unvisited neighbors. The `shortestPath` function extends BFS to find the minimum number of edges between two nodes. It stores pairs of {node, distance} in the queue and returns the distance when the `endNode` is reached. The time complexity for BFS is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited at most once. The space complexity is O(V) in the worst case for the queue and visited set. Edge cases include empty graphs, disconnected components, and invalid start/end nodes.

class Graph: adjacency_list function addEdge(u, v): add v to adjacency_list[u] add u to adjacency_list[v] // for undirected graph function bfs(start_node): if graph is empty: return if start_node not in graph: print erro...

This C++ code finds a peak element in an array. A peak element is defined as an element that is strictly greater than its adjacent neighbors. The algorithm utilizes binary search to efficiently locate such an element. Th...

The `findPeakElement` function implements a binary search approach to find a peak element in a given array `nums`. A peak element is strictly greater than its neighbors. The algorithm handles edge cases such as empty or single-element arrays. The core logic relies on the observation that if `nums[mid] > nums[mid + 1]`, a peak must exist in the left half (including `mid`), otherwise, a peak must exist in the right half (excluding `mid`). The loop invariant is that a peak element is guaranteed to exist within the range `[left, right]`. The time complexity is O(log n) due to binary search, and the space complexity is O(1) as it uses a constant amount of extra space. The correctness is ensured by the monotonic property exploited by binary search: we always move towards a direction where a peak is guaranteed to exist.

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

This C++ code implements a modified binary search algorithm to find a target value within a sorted array that has been rotated at an unknown pivot point. The algorithm first determines which half of the array (left or ri...

The `searchRotated` function efficiently finds a `target` in a `nums` array that was originally sorted and then rotated. It uses a binary search approach, but with a modification to handle the rotation. In each step, it calculates the `mid` index. It then checks if the left half (`nums[left]` to `nums[mid]`) is sorted. If it is, it determines if the `target` lies within this sorted left half. If `target` is within `[nums[left], nums[mid])`, the search space is narrowed to the left (`right = mid - 1`). Otherwise, the search continues in the right half (`left = mid + 1`). If the left half is not sorted, it implies the right half (`nums[mid]` to `nums[right]`) must be sorted. It then checks if `target` is within `(nums[mid], nums[right]]`. If so, the search continues in the right half (`left = mid + 1`); otherwise, it continues in the left half (`right = mid - 1`). The loop terminates when `left > right`, indicating the target was not found. 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 like empty arrays, single-element arrays, and arrays with two elements are handled by the loop condition and the logic for determining the sorted half.

function searchRotated(nums, target): n = length of nums if n is 0: return -1 left = 0 right = n - 1 while left <= right: mid = left + (right - left) / 2 if nums[mid] == target: return mid // Check if left half is sorted...

This C++ code implements a queue data structure using two stacks. The `push` operation adds elements to the first stack, and the `pop` operation retrieves elements from the second stack. Elements are transferred from the...

This implementation of a queue uses two stacks, `stack1` and `stack2`, to simulate FIFO behavior. Elements are `push`ed onto `stack1`. When a `pop` or `peek` operation is requested, if `stack2` is empty, all elements from `stack1` are transferred to `stack2`. This reversal ensures that the element at the bottom of `stack1` (the oldest element) becomes the top of `stack2`, ready to be dequeued. The `transferElements` helper function handles this crucial step. The `pop` and `peek` operations then work on `stack2`. If `stack2` remains empty after the transfer attempt, it signifies an empty queue, and an exception is thrown. The `isEmpty` and `size` methods correctly reflect the total number of elements across both stacks. The time complexity for `push` is O(1). The amortized time complexity for `pop` and `peek` is O(1), because each element is pushed onto `stack1` once and popped from `stack1` and pushed onto `stack2` at most once, and finally popped from `stack2` once. In the worst case for a single `pop` operation (when a transfer is needed), it can be O(n), but averaged over many operations, it's constant. The space complexity is O(n) to store the elements.

class QueueUsingStacks: stack1: stack stack2: stack transferElements(): if stack2 is empty: while stack1 is not empty: move top of stack1 to stack2 pop from stack1 push(value): push value onto stack1 pop(): transferEleme...

This C++ code calculates the length of the Longest Increasing Subsequence (LIS) within a given array using dynamic programming. An increasing subsequence is a sequence of elements from the array that are in strictly incr...

The `lengthOfLIS` function computes the length of the Longest Increasing Subsequence (LIS) using dynamic programming. It initializes a DP array `dp` of the same size as `nums`, where `dp[i]` represents the length of the LIS ending at index `i`. Each `dp[i]` is initialized to 1, as a single element itself forms an LIS of length 1. The algorithm then iterates through the array: for each element `nums[i]`, it checks all preceding elements `nums[j]` (where `j < i`). If `nums[i]` is greater than `nums[j]`, it means `nums[i]` can extend the LIS ending at `j`. Thus, `dp[i]` is updated to be the maximum of its current value and `dp[j] + 1`. The final LIS length is the maximum value found 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 table. Edge cases like empty arrays are handled. The correctness relies on the principle of optimality: the LIS ending at `i` is found by considering all possible previous elements that can precede `nums[i]` and choosing the one that yields the longest subsequence.

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