Unit 5: Transform-and-Conquer and Advanced Algorithmic Techniques - Subjective Questions

A balanced search tree is a binary search tree in which the height is kept proportional to the logarithm of the number of stored keys. For nodes, its height is typically .

Balancing is necessary because:

• An ordinary binary search tree can become skewed when keys are inserted in sorted or nearly sorted order.
• A skewed tree can have height , making search, insertion, and deletion linear-time operations.
• A balanced tree limits its height to .
• Therefore, search, insertion, and deletion can be performed in time in the worst case.

Examples of balanced search trees include AVL trees, red-black trees, 2-3 trees, and B-trees.

For every node in an AVL tree, the balance factor is defined as:

The AVL balance condition requires to be one of , , or .

When insertion violates this condition, one of four cases occurs:

• Left-Left case: The new key is inserted in the left subtree of the left child. Perform a single right rotation.
• Right-Right case: The new key is inserted in the right subtree of the right child. Perform a single left rotation.
• Left-Right case: The new key is inserted in the right subtree of the left child. First rotate the left child to the left, then rotate the unbalanced node to the right.
• Right-Left case: The new key is inserted in the left subtree of the right child. First rotate the right child to the right, then rotate the unbalanced node to the left.

Rotations preserve the binary-search-tree ordering while restoring a height of .

AVL trees and red-black trees are self-balancing binary search trees, but they use different balancing policies.

• Balance strictness: AVL trees maintain a balance factor of , , or at every node. Red-black trees use coloring rules and permit greater height variation.
• Height: AVL trees are usually shorter and more rigidly balanced. A red-black tree with internal nodes has height at most .
• Search: AVL trees may provide faster searches because of their smaller height.
• Insertion and deletion: Red-black trees generally require fewer rotations and are often better for update-intensive workloads.
• Complexity: Both support search, insertion, and deletion in worst-case time.
• Applications: AVL trees are suitable for search-heavy systems, while red-black trees are common in standard-library maps, sets, schedulers, and operating-system structures.

Thus, AVL trees emphasize tighter balance, whereas red-black trees provide a practical compromise between search efficiency and update cost.

Insertion:

1. Follow the ordinary binary-search-tree search path to locate the insertion position.
2. Insert the new key as a leaf.
3. Move upward toward the root, updating heights, balance factors, colors, or other balancing information.
4. Apply rotations or restructuring wherever a balancing rule is violated.

Deletion:

1. Locate the key using binary search on the tree.
2. If the node has two children, replace it with its inorder successor or predecessor.
3. Remove the resulting node with at most one child.
4. Traverse upward and repair balance violations using rotations, recoloring, merging, or redistribution, depending on the tree type.

If the balanced tree contains nodes, its height is . Searching for the affected location takes . Repair work is performed along at most one root-to-leaf path, so it also takes . Therefore:

The additional space is for an iterative implementation or for the recursion stack.

Counting sort is a non-comparison sorting algorithm for integer keys drawn from a limited range through .

For the input :

1. Create a count array initialized to zero.
2. Count each key. The nonzero counts are , , , , and .
3. Convert counts to cumulative counts when a stable output is required.
4. Scan the input from right to left, placing each element in its final output position and decrementing its cumulative count.
5. The sorted output is .

For input elements and key range size :

• Time complexity:
• Auxiliary space: for the stable version

Counting sort is efficient when , but it becomes wasteful when the key range is much larger than the number of elements.

Counting sort is a non-comparison sort because it does not determine order by comparing pairs of keys. Instead, it counts how many times each key occurs.

For a count array , cumulative counts are computed as:

After this transformation, gives the number of elements with keys less than or equal to . Therefore, it identifies the final position immediately after the last occurrence of key .

To preserve stability, the input is traversed from right to left. For an element :

• Place it at position in the output array.
• Decrement .

Reverse traversal ensures that if two records have equal keys, the record appearing later in the input is placed later in the output. Thus, their original relative order is preserved.

Stability is essential when counting sort is used as an intermediate stable sorting step in algorithms such as least-significant-digit radix sort.

Least-significant-digit radix sort processes digits from the least significant position to the most significant position. A stable sorting algorithm, commonly counting sort, is applied at each digit position.

For decimal keys:

• Units digit pass:
• Tens digit pass:
• Hundreds digit pass:

The final array is sorted because every pass preserves the ordering established by earlier, less significant digits.

If there are digits, keys, and radix , and counting sort is used for each pass, the running time is:

The auxiliary space is . Radix sort is particularly effective when is bounded and is chosen so that each digit pass is efficient.

LSD radix sort:

• Processes digits from the least significant digit to the most significant digit.
• Usually performs the same stable sorting operation on the complete array during every pass.
• Naturally handles fixed-length integer keys.
• Requires the digit-level sort to be stable.

MSD radix sort:

• Processes the most significant digit first.
• Divides keys into groups according to the current digit and recursively sorts each group using the next digit.
• Can stop early for groups of identical prefixes.
• Is useful for variable-length strings and lexicographic sorting.

Stability is required in LSD radix sort because the ordering produced for less significant digits must survive later passes. If two keys have the same current digit, a stable pass keeps them in the order determined by previously processed digits. Without stability, a later pass could destroy earlier ordering, and the final result might not be sorted.

Bucket sort distributes elements among several buckets, sorts each bucket, and concatenates the results.

For real numbers uniformly distributed in :

1. Create empty buckets .
2. Place value into bucket .
3. Sort each bucket, often using insertion sort.
4. Concatenate the buckets in index order.

Distribution and concatenation each require time. Let be the number of elements in bucket . If insertion sort is used, bucket sorting costs:

Under a uniform distribution, the expected number of elements per bucket is constant, and:

Therefore, the expected total running time is . If all elements fall into one bucket, however, insertion sort takes , giving the worst-case running time.

Counting sort:

• Assumes integer keys from a small known range.
• Runs in time, where represents the key range.
• Can be stable when cumulative counts and an output array are used.
• Is suitable when is not much larger than .

Radix sort:

• Assumes keys can be decomposed into digits or components.
• Runs in time for digits and radix .
• LSD radix sort requires a stable digit-level sort.
• Is suitable for fixed-width integers, identifiers, and strings.

Bucket sort:

• Assumes keys are approximately uniformly distributed over a known interval.
• Has expected complexity with suitable buckets, but can take in the worst case.
• Stability depends on how elements are inserted and how individual buckets are sorted.
• Is suitable for uniformly distributed real-valued data.

All three techniques can outperform comparison sorting because they exploit additional information about the keys or their distribution.

A monotonic stack stores elements or indices in consistently increasing or decreasing order. Elements that violate the required order are removed before a new element is pushed.

To find the next greater element to the right:

1. Initialize an empty stack of indices.
2. Scan the array from left to right.
3. While the stack is nonempty and the current element is greater than the element at the index on top of the stack, pop that index.
4. Assign the current element as the next greater element for every popped index.
5. Push the current index.
6. Assign to indices remaining in the stack after the scan.

For , the next greater elements are .

Each index is pushed once and popped at most once. Therefore, the total time complexity is and the auxiliary space is .

Maintain a stack of bar indices whose heights are in nondecreasing order. Append a sentinel bar of height so that all remaining bars are processed.

For each index :

1. While the stack is nonempty and the current height is smaller than the height at the top index, pop an index .
2. The popped bar has height .
3. Its right boundary is .
4. Its left boundary is one position after the new stack top. If the stack is empty, the left boundary is .
5. Thus, the width is when the stack is empty; otherwise it is .
6. Compute the area as and update the maximum.
7. Push after all taller bars have been removed.

The stack identifies the maximal interval over which each popped bar is the minimum height. Every index is pushed once and popped once, so the total number of stack operations is . Hence, the algorithm runs in time and uses space.

To find a previous smaller element, scan from left to right while maintaining an increasing stack. Before processing , pop indices whose values are greater than or equal to . The new top, if present, is the nearest previous index containing a smaller value.

To find a next smaller element, either scan from right to left using a similar increasing stack or resolve waiting indices during a left-to-right scan whenever a smaller value appears.

These boundaries define the maximal interval over which can act as the minimum element. They are useful for:

• Computing the largest rectangle in a histogram.
• Calculating the sum of subarray minimums.
• Determining spans of influence for array elements.
• Finding nearest obstructing or limiting values.

Because every index is pushed and popped at most once in each scan, all boundaries can be computed in time using space.

A monotonic queue is usually implemented with a deque and maintains its stored values or indices in increasing or decreasing order.

When maintaining a decreasing queue:

• Elements smaller than or equal to a newly inserted element are removed from the back.
• The new element is inserted at the back.
• Expired elements are removed from the front.
• The front always contains the maximum element in the active range.

An ordinary queue preserves insertion order and supports insertion at the rear and removal from the front, but it does not maintain an ordered extremum.

A monotonic stack supports operations at one end and is commonly used for nearest-greater or nearest-smaller boundary problems. A monotonic queue uses both ends of a deque and is particularly useful for maintaining a minimum or maximum over a moving window.

Each element enters and leaves the deque at most once, so a sequence of operations takes total time.

Store array indices in a deque such that their corresponding values are in decreasing order.

For each index :

1. Remove the front index if it is outside the current window, that is, if it is at most .
2. Remove indices from the back while their values are less than or equal to .
3. Insert at the back.
4. Once , report the value at the front as the window maximum.

For and , the windows and maxima are:

Therefore, the output is . Each index is inserted and removed at most once, so the time complexity is and the deque uses space.

Consider a recurrence of the form:

A direct implementation examines up to previous states for every , resulting in time.

A monotonic increasing deque can maintain candidate indices :

1. Remove the front index when it becomes smaller than .
2. The front now contains the index with the minimum valid value.
3. Compute using that front value.
4. Remove indices from the back while their values are greater than or equal to , because they cannot become a future minimum before expires.
5. Insert index at the back.

Every state enters and leaves the deque at most once. Consequently, the recurrence is evaluated in time instead of , while the deque requires space.

The two-pointers technique uses two indices that move through a data structure according to conditions that eliminate unnecessary repeated work.

Main variants include:

• Opposite-direction pointers: One pointer begins at each end and they move inward. This is used for pair-sum search in a sorted array, palindrome checking, and container-area problems.
• Same-direction pointers: Both pointers move forward, often representing the beginning and end of a window. This is used for removing duplicates and partitioning sequences.
• Fast and slow pointers: One pointer moves faster than the other. This is used for cycle detection, locating the middle of a linked list, and in-place filtering.
• Sliding-window pointers: The right pointer expands a range and the left pointer contracts it when a condition is violated. This is used for subarray and substring optimization.

Two pointers often reduce a nested-loop solution from to after any required preprocessing.

Initialize and . While , compute:

• If , return the pair.
• If , increment .
• If , decrement .
• If the pointers meet without equality, no valid pair exists.

Correctness:

If , pairing with any element at an index smaller than cannot produce , because those elements are no larger than . Therefore, can be safely eliminated.

If , pairing with any element at an index larger than cannot produce , because those elements are no smaller than . Therefore, can be safely eliminated.

Each step discards only a value that cannot belong to a solution within the remaining interval. Hence, if a pair exists, the algorithm eventually finds it.

The running time is and the auxiliary space is . If the array must first be sorted, the total time becomes .

Maintain a window and its current sum.

1. Initialize , , and the best length to infinity.
2. Move from left to right, adding to the sum.
3. While , record the current length , subtract , and increment .
4. Continue until all right endpoints have been processed.

The method is correct for positive elements because expanding the window cannot decrease its sum, while removing elements from the left cannot increase it. Therefore, once a window reaches , repeatedly moving the left pointer identifies the shortest valid window for that right endpoint.

Each pointer advances at most times, so the algorithm runs in time and uses auxiliary space.

This direct method does not generally work with negative elements because window expansion and contraction no longer change the sum monotonically.

All three techniques process sequences efficiently by maintaining an invariant that prevents repeated examination of irrelevant elements.

• Two pointers: The invariant usually describes a valid interval or an eliminated search region. Pointer movement is justified by sorted order, positivity, or another monotonic property. Typical applications include pair-sum search, partitioning, and variable-length windows.
• Monotonic stack: The stack maintains increasing or decreasing order among unresolved elements. Popping identifies the nearest element that violates or satisfies an order relation. Typical applications include next-greater elements, histogram areas, and subarray-boundary calculations.
• Monotonic queue: A deque maintains ordered candidates within an active window. The front supplies the current minimum or maximum, while expired and dominated candidates are removed. Typical applications include sliding-window extrema and dynamic-programming optimization.

Their linear-time behavior comes from amortization: each pointer moves only forward, or each element is inserted and removed only a constant number of times. The correct technique depends on whether the problem concerns an interval, a nearest ordered boundary, or an extremum over a moving range.