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

I. Orientation — Transforming Structure to Simplify Computation

Transform-and-conquer solves a problem by converting its input, representation, or data structure into a form that is easier to process. Unlike divide-and-conquer, it does not necessarily create independent subproblems; the transformed form itself enables efficient searching, sorting, or traversal.

• Core principle: Transform an instance (I) into (I'), solve (I'), and interpret the result for (I).
• Transformation types:
  • Instance simplification: Reduce a problem to a simpler instance, as in balancing a search tree after an update.
  • Representation change: Replace comparison-based ordering with counts, digits, or buckets.
  • Prestructuring: Maintain elements in monotonic order so future queries become efficient.
  • Traversal restriction: Use pointer movement to avoid examining every pair or subarray.
• Efficiency measures: Running time is expressed using input size (n), key range (k), digit count (d), tree height (h), or window size (w).
• Amortized analysis: A single operation may be expensive, but the total over (n) operations is (O(n)), as with monotonic stacks and queues.
• Space–time trade-off: Counting arrays, buckets, stacks, queues, and tree metadata consume extra space to reduce computation.
• Comparison barrier: Comparison sorting requires (\Omega(n\log n)) comparisons in the worst case, but counting, radix, and bucket sort can be faster by exploiting key structure.

II. Balanced Search Trees — Height-Controlled Dynamic Searching

A. Balanced Search Trees

A balanced search tree maintains logarithmic height so that dynamic dictionary operations remain efficient.

• Search-tree property: For a node with key (x), keys in its left subtree are less than (x), while keys in its right subtree are greater than (x), subject to the chosen duplicate-key convention.
• Need for balance: An ordinary binary search tree can become a chain after inserting (10,20,30,40), producing height (h=n-1) and (O(n)) operations.
• Complexity relation:
  
  TEXT

    Search, insertion, deletion = O(h)
    Balanced height h = O(log n)
    Therefore, each operation = O(log n)

  
  Here, (h) is tree height and (n) is the number of nodes.
• AVL trees: Every node has balance factor
  [
  BF(v)=h(\text{left}(v))-h(\text{right}(v))\in{-1,0,1}.
  ]
  Violations are repaired using LL, RR, LR, or RL rotations.
• Red–black trees: Nodes are colored red or black; coloring restrictions ensure that the longest root-to-leaf path is at most twice the shortest, giving (h=O(\log n)).
• Rotations: A left or right rotation changes local links while preserving in-order key order. Rotations take (O(1)) time.
• Contrast:
  1. AVL tree: Stricter balance usually gives faster searches but may require more update rebalancing.
  2. Red–black tree: Weaker balance reduces restructuring and is common in library maps and sets.

B. Applications and Limitations

Balanced trees are appropriate when ordered data must support both updates and queries.

• Applications: Symbol tables, database indexes, ordered maps, predecessor queries, and range reporting use logarithmic navigation.
• Ordered operations: Minimum, maximum, successor, and predecessor can be supported in (O(\log n)).
• Limitation: Pointer storage, balance metadata, and rotations make implementation more complex than hashing.
• Trade-off: Hash tables offer expected (O(1)) lookup, but balanced trees preserve sorted order and guarantee (O(\log n)) worst-case operations.

III. Counting Sort — Sorting by Frequency Transformation

A. Counting Sort

Counting sort orders integer keys by recording how often each key occurs rather than comparing pairs of elements.

• Conditions: Keys must be integers in a known range, commonly (0) through (k).
• Procedure:
  1. Create count array (C[0\ldots k]).
  2. Count each key’s frequency.
  3. Convert frequencies to prefix sums.
  4. Place elements into output array (B).
• Pseudocode:
  
  TEXT

    for x in A:
        C[x] = C[x] + 1
    for i = 1 to k:
        C[i] = C[i] + C[i - 1]
    for j = n - 1 downto 0:
        B[C[A[j]] - 1] = A[j]
        C[A[j]] = C[A[j]] - 1

  
  Here, (A) is the input, (B) is the output, (C) stores counts or positions, (n) is the number of elements, and (k) is the maximum key.
• Stability: Traversing (A) from right to left preserves the relative order of equal keys.
• Complexity:
  [
  T(n,k)=O(n+k),\qquad S(n,k)=O(n+k).
  ]
• Example: For (A=[2,1,2,0]), frequencies are ([1,1,2]), and the sorted result is ([0,1,2,2]).

B. Applications and Limitations

Counting sort is effective only when the key range is reasonably small relative to the input.

• Applications: Ages, grades, small identifiers, and digit sorting are suitable bounded-key uses.
• Advantage: It can run in linear time because it avoids comparisons.
• Limitation: If (n=100) but keys range to (10^9), allocating (C) is impractical.
• Negative keys: An offset can map keys from ([m,M]) to ([0,M-m]).

IV. Radix Sort — Ordering Keys One Position at a Time

A. Radix Sort

Radix sort processes structured keys digit by digit using a stable sorting method at each position.

• LSD method: Least-significant-digit radix sort processes units, tens, hundreds, and so on.
• Stability requirement: The sort used for each digit must be stable; otherwise, ordering established by earlier passes is destroyed.
• Pseudocode:
  
  TEXT

    exp = 1
    while maximumKey / exp > 0:
        stableSortByDigit(A, exp, base)
        exp = exp * base

  
  Here, exp identifies the current positional value and base is the radix.
• Correctness idea: After pass (i), elements are ordered by their (i) least significant digits. Stability preserves lower-digit ordering when the next digit is processed.
• Complexity:
  [
  T(n)=O(d(n+b)),
  ]
  where (d) is the number of digits and (b) is the base or number of digit values.
• Example: Sorting (170,45,75,90) in base 10 uses stable passes on units, tens, and hundreds to obtain (45,75,90,170).

B. Applications and Limitations

Radix sort is valuable when keys have a fixed-length positional representation.

• Applications: Integers, fixed-length strings, dates, and machine words can be processed by digits or characters.
• Advantage: With bounded (d) and (b), running time approaches (O(n)).
• Limitation: Variable-length keys, large auxiliary arrays, or expensive digit extraction may reduce its benefit.
• Contrast with counting sort: Counting sort handles complete bounded keys directly; radix sort commonly uses counting sort on one digit per pass.

V. Bucket Sort — Distribution into Value Intervals

A. Bucket Sort

Bucket sort distributes values into intervals, sorts each interval, and concatenates the results.

• Procedure: Create buckets, map each element to a bucket, sort individual buckets, and join them in interval order.
• Mapping: For (n) buckets and values (x\in[0,1)), a common index is
  [
  i=\lfloor nx\rfloor,
  ]
  where (i) is the bucket index.
• Pseudocode:
  
  TEXT

    create n empty buckets
    for x in A:
        append x to bucket[floor(n * x)]
    sort each bucket
    concatenate buckets in index order

• Expected complexity: Under an approximately uniform distribution, bucket sizes remain small and expected time is (O(n)).
• Worst case: If all elements enter one bucket and comparison sorting is used internally, time may become (O(n^2)).
• Example: Values (0.12,0.78,0.25,0.14) distributed among ten buckets place (0.12) and (0.14) together, followed by (0.25) and (0.78).

B. Applications and Limitations

Bucket sort depends more strongly on input distribution than counting or radix sort.

• Applications: Uniformly distributed measurements and floating-point values over a known interval are suitable.
• Advantage: Separate buckets can be sorted independently or in parallel.
• Limitation: Poor bucket boundaries cause imbalance and degrade performance.
• Requirement: Concatenation is correct only when every key in bucket (i) is no greater than every key in bucket (i+1).

VI. Monotonic Stack — Linear-Time Nearest-Element Processing

A. Monotonic Stack

A monotonic stack stores candidates in increasing or decreasing order to answer nearest greater-or-smaller-element queries.

• Invariant: An increasing stack keeps values increasing from bottom to top; a decreasing stack keeps them decreasing.
• Next-greater algorithm:
  
  TEXT

    for i = 0 to n - 1:
        while stack not empty and A[stack.top] < A[i]:
            answer[stack.pop] = A[i]
        stack.push(i)

  
  The stack stores indices, allowing answers to be associated with original positions.
• Worked example: For ([2,1,4,3]), the next greater values are ([4,4,\text{none},\text{none}]).
• Amortized complexity: Every index is pushed once and popped at most once, so total time is (O(n)), not (O(n^2)).
• Variants: Changing < to > or adjusting equality handles next smaller, previous greater, and previous smaller queries.

B. Applications and Limitations

Monotonic stacks compress repeated backward searches into a single scan.

• Applications: Stock span, daily temperatures, histogram area, and subarray minimum calculations.
• Tie handling: Duplicate values require deliberate use of strict or non-strict comparison.
• Limitation: The technique fits nearest-boundary relationships, not arbitrary range queries.
• Space: At most (n) unresolved indices are stored, giving (O(n)) auxiliary space.

VII. Monotonic Queue — Efficient Sliding-Window Extremes

A. Monotonic Queue

A monotonic queue, usually implemented as a deque, maintains window candidates so the front is always the current minimum or maximum.

• Maximum invariant: Values decrease from front to rear; smaller rear values are removed because a newer, larger value dominates them.
• Pseudocode:
  
  TEXT

    for i = 0 to n - 1:
        while deque not empty and deque.front <= i - w:
            deque.popFront()
        while deque not empty and A[deque.back] <= A[i]:
            deque.popBack()
        deque.pushBack(i)
        if i >= w - 1:
            output A[deque.front]

  
  Here, (w) is window size and the deque stores indices.
• Example: For ([1,3,-1,-3,5]) with (w=3), window maxima are ([3,3,5]).
• Complexity: Each index enters and leaves the deque at most once, yielding (O(n)) time and (O(w)) space.
• Expiration rule: Indices at most (i-w) lie outside the current window and must be removed.

B. Applications and Limitations

Monotonic queues are specialized for extrema over continuously moving ranges.

• Applications: Sliding-window maximum or minimum, streaming measurements, and bounded-range dynamic programming.
• Advantage: It improves the heap-based (O(n\log w)) approach to (O(n)).
• Limitation: It does not directly provide medians, sums, or arbitrary order statistics.
• Distinction: A monotonic stack resolves nested nearest-element boundaries; a monotonic queue also removes expired elements from the front.

VIII. Two-Pointers Technique — Coordinated Linear Traversal

A. Two-Pointers Technique

The two-pointers technique coordinates two indices so each movement eliminates many impossible candidates.

• Opposite-direction pointers: On a sorted array, set (L=0) and (R=n-1). For target sum (t), move (L) right when (A[L]+A[R]<t), and move (R) left when the sum exceeds (t).
• Same-direction pointers: A slow pointer records a valid boundary while a fast pointer explores, as in duplicate removal or stable compaction.
• Sliding-window form: Right expands a contiguous range; left contracts it when a constraint is violated.
• Pseudocode for pair sum:
  
  TEXT

    L = 0; R = n - 1
    while L < R:
        s = A[L] + A[R]
        if s == target: return (L, R)
        if s < target: L = L + 1
        else: R = R - 1

• Complexity: Each pointer moves at most (n) positions, so traversal takes (O(n)); sorting beforehand may add (O(n\log n)).
• Correctness basis: Sorted order or a monotone constraint proves that discarded candidates cannot form a valid solution.

B. Applications and Limitations

Two pointers replace nested enumeration when pointer movement has a valid elimination rule.

• Applications: Pair-sum search, merging sorted arrays, palindrome checks, partitioning, duplicate removal, and variable-size windows.
• Advantage: Pair testing falls from (O(n^2)) brute force to (O(n)) after sorting.
• Limitation: Unsorted data or constraints with negative values may invalidate monotone window movement.
• Preserving indices: If sorting changes positions, store each value with its original index before applying opposite-direction pointers.