Sorting Algorithms

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        bool swapped = false;
        for (int j = 0; j < n-1-i; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped) break;   // Early exit: already sorted
    }
}
// Best:  O(n)   — already sorted (with early exit)
// Avg:   O(n²)
// Worst: O(n²)  — reverse sorted
// Space: O(1) in-place
// Stable: YES

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n-1; i++) {
        int minIdx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[minIdx]) minIdx = j;
        swap(arr[i], arr[minIdx]);
    }
}
// Best/Avg/Worst: O(n²) — always scans full remaining array
// Space: O(1) in-place
// Stable: NO — swap may reorder equal elements
// Advantage: minimum number of swaps (exactly n-1)

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j+1] = arr[j];   // Shift right
            j--;
        }
        arr[j+1] = key;          // Insert
    }
}
// Best:  O(n)   — already sorted
// Avg:   O(n²)
// Worst: O(n²)  — reverse sorted
// Space: O(1) in-place
// Stable: YES
// Key advantage: O(n) for nearly sorted data — used internally by std::sort
//                for small subarrays (typically n < 16)

void merge(vector<int>& arr, int l, int mid, int r) {
    vector<int> left(arr.begin()+l,   arr.begin()+mid+1);
    vector<int> right(arr.begin()+mid+1, arr.begin()+r+1);
 
    int i = 0, j = 0, k = l;
    while (i < (int)left.size() && j < (int)right.size()) {
        if (left[i] <= right[j]) arr[k++] = left[i++];   // <= for stability
        else                      arr[k++] = right[j++];
    }
    while (i < (int)left.size())  arr[k++] = left[i++];
    while (j < (int)right.size()) arr[k++] = right[j++];
}
 
void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;
    int mid = l + (r-l)/2;
    mergeSort(arr, l, mid);
    mergeSort(arr, mid+1, r);
    merge(arr, l, mid, r);
}
 
// Entry point:
void mergeSort(vector<int>& arr) { mergeSort(arr, 0, arr.size()-1); }
 
// Time:  O(n log n) — always, regardless of input
// Space: O(n) — auxiliary array for merging
// Stable: YES — uses <= in merge comparison

long long mergeCount(vector<int>& arr, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r-l)/2;
    long long count = 0;
    count += mergeCount(arr, l, mid);
    count += mergeCount(arr, mid+1, r);
 
    // Count inversions during merge
    vector<int> temp;
    int i = l, j = mid+1;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) {
            temp.push_back(arr[i++]);
        } else {
            // arr[i..mid] are all > arr[j] (since left is sorted)
            count += (mid - i + 1);   // All remaining left elements form inversions with arr[j]
            temp.push_back(arr[j++]);
        }
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= r)   temp.push_back(arr[j++]);
    copy(temp.begin(), temp.end(), arr.begin()+l);
    return count;
}
 
long long countInversions(vector<int>& arr) {
    return mergeCount(arr, 0, arr.size()-1);
}
// Time: O(n log n), Space: O(n)

int partitionLomuto(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];
    int i = lo - 1;   // i = last index of "less than pivot" section
 
    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[hi]);   // Place pivot in correct position
    return i + 1;              // Pivot's final index
}
 
void quickSortLomuto(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = partitionLomuto(arr, lo, hi);
    quickSortLomuto(arr, lo, pivot-1);
    quickSortLomuto(arr, pivot+1, hi);
}
// Time:  O(n log n) avg, O(n²) worst (sorted input with last-element pivot)
// Space: O(log n) avg recursion stack, O(n) worst
// Stable: NO

int partitionHoare(vector<int>& arr, int lo, int hi) {
    int pivot = arr[lo + (hi-lo)/2];   // Middle element as pivot
    int i = lo - 1, j = hi + 1;
 
    while (true) {
        do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[j] > pivot);
        if (i >= j) return j;
        swap(arr[i], arr[j]);
    }
}
 
void quickSortHoare(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int p = partitionHoare(arr, lo, hi);
    quickSortHoare(arr, lo, p);
    quickSortHoare(arr, p+1, hi);
}
// Hoare: ~3x fewer swaps than Lomuto in practice

void quickSort3Way(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = arr[lo + (hi-lo)/2];
    int lt = lo, gt = hi, i = lo;
 
    while (i <= gt) {
        if      (arr[i] < pivot) swap(arr[lt++], arr[i++]);  // < pivot: swap to front
        else if (arr[i] > pivot) swap(arr[i], arr[gt--]);    // > pivot: swap to back
        else                     i++;                         // == pivot: skip
    }
    // After: arr[lo..lt-1] < pivot, arr[lt..gt] == pivot, arr[gt+1..hi] > pivot
    quickSort3Way(arr, lo, lt-1);
    quickSort3Way(arr, gt+1, hi);
}
// Key advantage: arr[lt..gt] is already sorted (all equal to pivot)
// For arrays with many duplicates: O(n) for a uniform array!

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void quickSortRandom(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;
    // Random pivot selection — makes O(n²) worst case astronomically unlikely
    int pivotIdx = lo + rng() % (hi - lo + 1);
    swap(arr[pivotIdx], arr[hi]);   // Move to end for Lomuto
    int p = partitionLomuto(arr, lo, hi);
    quickSortRandom(arr, lo, p-1);
    quickSortRandom(arr, p+1, hi);
}
// Expected time: O(n log n) for ANY input
// Worst case: O(n²) with probability 1/n! (negligible)

void siftDown(vector<int>& arr, int i, int n) {
    while (true) {
        int largest = i, l = 2*i+1, r = 2*i+2;
        if (l < n && arr[l] > arr[largest]) largest = l;
        if (r < n && arr[r] > arr[largest]) largest = r;
        if (largest == i) break;
        swap(arr[i], arr[largest]);
        i = largest;
    }
}
 
void heapSort(vector<int>& arr) {
    int n = arr.size();
 
    // Phase 1: Build max-heap in O(n)
    for (int i = n/2-1; i >= 0; i--)
        siftDown(arr, i, n);
 
    // Phase 2: Extract elements one by one
    for (int i = n-1; i > 0; i--) {
        swap(arr[0], arr[i]);     // Move max to end
        siftDown(arr, 0, i);      // Restore heap on arr[0..i-1]
    }
}
// Time:  O(n log n) always — build O(n) + n extractions × O(log n)
// Space: O(1) — in-place
// Stable: NO — long-distance swaps break stability
// Cache: Poor — accesses distant elements (heap jumps)
// In practice: slower than quicksort due to poor cache performance

void countingSort(vector<int>& arr, int maxVal) {
    vector<int> count(maxVal+1, 0);
 
    for (int x : arr) count[x]++;           // Count occurrences
    for (int i = 1; i <= maxVal; i++)
        count[i] += count[i-1];              // Prefix sum → positions
 
    vector<int> output(arr.size());
    for (int i = arr.size()-1; i >= 0; i--) { // Reverse for stability
        output[--count[arr[i]]] = arr[i];
    }
    arr = output;
}
// Time:  O(n + k) where k = range of values
// Space: O(n + k)
// Stable: YES (traverse input array right to left)
// Use when: k is small (e.g., sort chars, sort ages 0-100)
// Fails when: k is large (e.g., k = 10^9 → needs too much memory)

void countingSortByDigit(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n), count(10, 0);
 
    for (int x : arr) count[(x / exp) % 10]++;
    for (int i = 1; i < 10; i++) count[i] += count[i-1];
    for (int i = n-1; i >= 0; i--) {
        output[--count[(arr[i] / exp) % 10]] = arr[i];
    }
    arr = output;
}
 
void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSortByDigit(arr, exp);
}
// Time:  O(d × (n + 10)) = O(d × n) where d = number of digits
// Space: O(n + 10) = O(n)
// Stable: YES (LSD uses stable counting sort at each pass)
// For 32-bit integers: d = 10, so effectively O(10n) = O(n)
// In practice: competitive with comparison sorts for large n with bounded values
 
/*
  arr = [170, 45, 75, 90, 802, 24, 2, 66]
  exp=1:   [170, 90, 802, 2, 24, 45, 75, 66]   (sort by units digit)
  exp=10:  [802, 2, 24, 45, 66, 170, 75, 90]   (sort by tens digit)
  exp=100: [2, 24, 45, 66, 75, 90, 170, 802]   (sort by hundreds digit) ✓
*/

void bucketSort(vector<double>& arr) {
    int n = arr.size();
    vector<vector<double>> buckets(n);
 
    for (double x : arr) {
        int idx = x * n;      // Assumes arr[i] in [0, 1)
        buckets[idx].push_back(x);
    }
    for (auto& bucket : buckets)
        sort(bucket.begin(), bucket.end());   // Insertion sort within bucket
 
    int k = 0;
    for (auto& bucket : buckets)
        for (double x : bucket) arr[k++] = x;
}
// Time: O(n) avg (uniform distribution), O(n²) worst (all in one bucket)
// Space: O(n)
// Stable: YES (if using stable sort for buckets)
// Use when: data is uniformly distributed over a known range

#include <algorithm>
#include <numeric>
 
vector<int> v = {5, 3, 1, 4, 2};
 
// ── std::sort ─────────────────────────────────────── O(n log n), NOT stable
sort(v.begin(), v.end());                     // Ascending
sort(v.begin(), v.end(), greater<int>());     // Descending
sort(v.begin(), v.begin()+3);                 // Sort only first 3 elements
 
// ── std::stable_sort ──────────────────────────────── O(n log n), STABLE
// Preserves relative order of equal elements
stable_sort(v.begin(), v.end());
stable_sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
 
// ── std::partial_sort ─────────────────────────────── O(n log k)
// Rearranges so [first, middle) contains the k smallest in sorted order
partial_sort(v.begin(), v.begin()+3, v.end());
// v[0..2] = {1,2,3} (sorted), v[3..4] = {4,5} or {5,4} (unspecified)
 
// ── std::nth_element ──────────────────────────────── O(n) average
// Guarantees: v[k] = what it would be if sorted
//             elements before k are ≤ v[k], elements after k are ≥ v[k]
nth_element(v.begin(), v.begin()+2, v.end());
// v[2] = 3rd smallest. Others are partitioned but NOT sorted.
 
// ── std::inplace_merge ────────────────────────────── O(n log n)
// Merges two consecutive sorted ranges in-place
vector<int> m = {1,3,5, 2,4,6};
inplace_merge(m.begin(), m.begin()+3, m.end());
// m = {1,2,3,4,5,6}
 
// ── Checking if sorted ───────────────────────────────
bool sorted_asc = is_sorted(v.begin(), v.end());
auto it = is_sorted_until(v.begin(), v.end());   // Iterator to first unsorted element
 
// ── std::sort_heap ────────────────────────────────── O(n log n)
// Sorts a range that satisfies heap property (built with make_heap)
make_heap(v.begin(), v.end());
sort_heap(v.begin(), v.end());   // Now sorted ascending

// Sort pairs by second element, break ties by first (descending)
vector<pair<int,int>> v = {{1,3},{2,1},{3,3},{4,2}};
sort(v.begin(), v.end(), [](const auto& a, const auto& b) {
    if (a.second != b.second) return a.second < b.second;
    return a.first > b.first;
});
// Result: {2,1}, {4,2}, {3,3}, {1,3}
 
// Sort strings by length, break ties lexicographically
vector<string> words = {"banana","fig","apple","kiwi"};
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});
// Result: "fig", "kiwi", "apple", "banana"

struct Interval {
    int start, end;
    bool operator<(const Interval& other) const {
        return start < other.start;   // Sort by start time
    }
};
vector<Interval> intervals = {{1,3},{0,2},{4,6}};
sort(intervals.begin(), intervals.end());   // Uses operator<
 
// Or use std::tie for lexicographic multi-field comparison:
struct Task { string name; int priority; int deadline; };
bool operator<(const Task& a, const Task& b) {
    return tie(a.priority, a.deadline, a.name) <
           tie(b.priority, b.deadline, b.name);
}

// Sort indices by value — preserves original array, gives sorted permutation
vector<int> arr = {50, 30, 10, 40, 20};
vector<int> idx(arr.size());
iota(idx.begin(), idx.end(), 0);   // Fill with 0,1,2,...
 
sort(idx.begin(), idx.end(), [&](int a, int b) {
    return arr[a] < arr[b];
});
// idx = {2, 4, 1, 3, 0}  → arr[idx[0]]=10, arr[idx[1]]=20, ...
 
// Now access elements in sorted order without modifying arr:
for (int i : idx) cout << arr[i] << " ";   // 10 20 30 40 50

// ❌ INVALID: using <= instead of < causes undefined behavior!
sort(v.begin(), v.end(), [](int a, int b){ return a <= b; });
// cmp(3, 3) = true → violates irreflexivity → UB (likely crash/infinite loop)
 
// ✅ VALID: strict <
sort(v.begin(), v.end(), [](int a, int b){ return a < b; });

// 3Sum: sort first, then fix one element + two-pointer for the pair
// Sort: O(n log n) once, then O(n) per fixed element → O(n²) total

// Search insert position, count elements ≤ x, find closest value
// Sort: O(n log n) once, then O(log n) per query

// Activity selection: sort by end time → greedy select non-overlapping
// Fractional knapsack: sort by value/weight ratio → greedy fill
 
// Template:
sort(activities.begin(), activities.end(), [](auto& a, auto& b) {
    return a.end < b.end;   // Sort by end time
});

// Merge intervals: sort by start, then scan and merge overlapping
// Valid if intervals[i].start <= intervals[i-1].end

// If array contains values in [1, n], sort in O(n) by placing each
// value at its correct index (index = value - 1):
void cyclicSort(vector<int>& nums) {
    int i = 0;
    while (i < (int)nums.size()) {
        int correct = nums[i] - 1;
        if (nums[i] != nums[correct]) swap(nums[i], nums[correct]);
        else i++;
    }
}
// After cyclic sort: find missing/duplicate by scanning for nums[i] != i+1

void sortColors(vector<int>& nums) {
    int lo=0, mid=0, hi=nums.size()-1;
    while (mid <= hi) {
        if      (nums[mid] == 0) swap(nums[lo++], nums[mid++]);
        else if (nums[mid] == 1) mid++;
        else                     swap(nums[mid], nums[hi--]);
        // Note: don't increment mid after swap with hi (need to re-examine)
    }
}
// Time: O(n), Space: O(1) — single pass!

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());   // Sort by start time
    vector<vector<int>> result;
 
    for (auto& interval : intervals) {
        if (!result.empty() && interval[0] <= result.back()[1]) {
            // Overlapping — extend the current merged interval's end
            result.back()[1] = max(result.back()[1], interval[1]);
        } else {
            result.push_back(interval);   // Non-overlapping — start new
        }
    }
    return result;
}
// Time: O(n log n) for sort + O(n) for merge pass = O(n log n)
// Space: O(n) for output

string largestNumber(vector<int>& nums) {
    vector<string> strs;
    for (int x : nums) strs.push_back(to_string(x));
 
    sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
        return a + b > b + a;   // Custom: prefer whichever concatenation is larger
    });
 
    if (strs[0] == "0") return "0";   // All zeros edge case
    string result;
    for (const string& s : strs) result += s;
    return result;
}
// Time: O(n × m log n) where m = max digit length. Space: O(n)
 
/*
  nums = [3, 30, 34, 5, 9]
  Compare 3 and 30: "330" vs "303" → 330 > 303 → 3 before 30
  Compare 3 and 34: "334" vs "343" → 334 < 343 → 34 before 3
  Sorted: [9, 5, 34, 3, 30] → "9534330"
*/

long long mergeCount(vector<int>& arr, int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r-l)/2;
    long long count = mergeCount(arr,l,mid) + mergeCount(arr,mid+1,r);
 
    vector<int> temp;
    int i=l, j=mid+1;
    while (i<=mid && j<=r) {
        if (arr[i] <= arr[j]) { temp.push_back(arr[i++]); }
        else {
            count += (mid - i + 1);   // All left[i..mid] > arr[j]
            temp.push_back(arr[j++]);
        }
    }
    while (i<=mid) temp.push_back(arr[i++]);
    while (j<=r)   temp.push_back(arr[j++]);
    copy(temp.begin(), temp.end(), arr.begin()+l);
    return count;
}
long long countInversions(vector<int>& arr) { return mergeCount(arr,0,arr.size()-1); }
// Time: O(n log n), Space: O(n)

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](auto& a, auto& b) {
        return a[1] < b[1];   // Sort by END time (greedy: keep earliest-ending)
    });
 
    int removed=0, prevEnd = INT_MIN;
    for (auto& iv : intervals) {
        if (iv[0] >= prevEnd) {
            prevEnd = iv[1];  // No overlap — keep this interval
        } else {
            removed++;        // Overlap — remove this interval (it ends later)
        }
    }
    return removed;
}
// Time: O(n log n), Space: O(1)

int findMinArrowShots(vector<vector<int>>& points) {
    sort(points.begin(), points.end(), [](auto& a, auto& b) {
        return a[1] < b[1];   // Sort by end point
    });
 
    int arrows=1, arrowPos = points[0][1];
    for (int i=1; i<(int)points.size(); i++) {
        if (points[i][0] > arrowPos) {      // Current balloon starts after arrow
            arrows++;
            arrowPos = points[i][1];         // New arrow at new end point
        }
        // Else: current balloon is hit by the existing arrow
    }
    return arrows;
}
// Time: O(n log n), Space: O(1)

// Approach 1: Sort descending — O(n log n)
int hIndex(vector<int>& citations) {
    sort(citations.rbegin(), citations.rend());
    int h = 0;
    for (int i=0; i<(int)citations.size(); i++) {
        if (citations[i] >= i+1) h = i+1;   // i+1 papers have >= i+1 citations
        else break;
    }
    return h;
}
 
// Approach 2: Counting sort — O(n) (since h ≤ n)
int hIndex_count(vector<int>& citations) {
    int n = citations.size();
    vector<int> cnt(n+1, 0);
    for (int c : citations) cnt[min(c, n)]++;  // Cap at n (h ≤ n always)
 
    int papers = 0;
    for (int h=n; h>=0; h--) {
        papers += cnt[h];
        if (papers >= h) return h;             // papers papers have >= h citations
    }
    return 0;
}
// Approach 2: Time O(n), Space O(n)

int maximumGap(vector<int>& nums) {
    int n = nums.size();
    if (n < 2) return 0;
 
    int lo = *min_element(nums.begin(), nums.end());
    int hi = *max_element(nums.begin(), nums.end());
    if (lo == hi) return 0;
 
    // Bucket size: at least ceil((hi-lo)/(n-1))
    int bucketSize = max(1, (hi - lo) / (n-1));
    int bucketCount = (hi - lo) / bucketSize + 1;
 
    vector<int> bucketMin(bucketCount, INT_MAX);
    vector<int> bucketMax(bucketCount, INT_MIN);
 
    for (int x : nums) {
        int idx = (x - lo) / bucketSize;
        bucketMin[idx] = min(bucketMin[idx], x);
        bucketMax[idx] = max(bucketMax[idx], x);
    }
 
    // Maximum gap is between consecutive non-empty buckets
    int maxGap = 0, prevMax = lo;
    for (int i = 0; i < bucketCount; i++) {
        if (bucketMin[i] == INT_MAX) continue;   // Empty bucket
        maxGap = max(maxGap, bucketMin[i] - prevMax);
        prevMax = bucketMax[i];
    }
    return maxGap;
}
// Time: O(n), Space: O(n)

void wiggleSort(vector<int>& nums) {
    int n = nums.size();
    vector<int> sorted = nums;
    sort(sorted.begin(), sorted.end());
 
    // Place larger half at odd indices (descending), smaller at even (descending)
    int small = (n-1)/2, large = n-1;   // Start from end to handle duplicates
    for (int i=0; i<n; i++) {
        nums[i] = (i % 2 == 0) ? sorted[small--] : sorted[large--];
    }
}
// Time: O(n log n), Space: O(n)
 
// O(n) time using nth_element:
void wiggleSort_ON(vector<int>& nums) {
    int n = nums.size();
    auto mid = nums.begin() + (n-1)/2;
    nth_element(nums.begin(), mid, nums.end());
    int median = *mid;
 
    // Virtual indexing: map i to 3-way partitioned positions
    // (1-indexed odd positions first, then even positions)
    auto mapIdx = [&](int i) { return (1 + 2*i) % (n | 1); };
 
    int lo=0, mi=0, hi=n-1;
    while (mi <= hi) {
        if      (nums[mapIdx(mi)] > median) swap(nums[mapIdx(lo++)], nums[mapIdx(mi++)]);
        else if (nums[mapIdx(mi)] < median) swap(nums[mapIdx(mi)],   nums[mapIdx(hi--)]);
        else                                mi++;
    }
}
// Time: O(n) with nth_element, Space: O(1)

vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
    // Map each arr2 element to its priority (position in arr2)
    unordered_map<int,int> priority;
    for (int i=0; i<(int)arr2.size(); i++) priority[arr2[i]] = i;
 
    sort(arr1.begin(), arr1.end(), [&](int a, int b) {
        bool aInP = priority.count(a), bInP = priority.count(b);
        if (aInP && bInP) return priority[a] < priority[b];  // Both in arr2: use arr2 order
        if (aInP) return true;    // Only a in arr2: a comes first
        if (bInP) return false;   // Only b in arr2: b comes first
        return a < b;             // Neither in arr2: ascending
    });
    return arr1;
}
// Time: O(n log n), Space: O(m) where m = arr2.size()

// Approach 1: Cyclic sort (modifies array)
int findDuplicate_cyclic(vector<int>& nums) {
    int i = 0;
    while (i < (int)nums.size()) {
        if (nums[i] != i+1) {
            if (nums[nums[i]-1] == nums[i]) return nums[i];  // Duplicate found
            swap(nums[i], nums[nums[i]-1]);
        } else { i++; }
    }
    return -1;
}
 
// Approach 2: Binary search on answer (O(n log n), O(1) space, no modification)
int findDuplicate(vector<int>& nums) {
    int lo=1, hi=nums.size()-1;
    while (lo < hi) {
        int mid = lo + (hi-lo)/2;
        // Count numbers in [1..mid]
        int cnt = count_if(nums.begin(), nums.end(), [&](int x){ return x<=mid; });
        if (cnt > mid) hi = mid;   // Duplicate is in [1..mid]
        else           lo = mid+1; // Duplicate is in [mid+1..n]
    }
    return lo;
}
// Time: O(n log n), Space: O(1)
 
// Approach 3: Fast/slow pointer (Floyd's — O(n), O(1), no modification)
int findDuplicate_floyd(vector<int>& nums) {
    int slow=nums[0], fast=nums[0];
    do { slow=nums[slow]; fast=nums[nums[fast]]; } while (slow!=fast);
    slow=nums[0];
    while (slow!=fast) { slow=nums[slow]; fast=nums[fast]; }
    return slow;
}

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
 
    // Split: find first middle using fast/slow
    ListNode* slow=head, *fast=head->next;
    while (fast && fast->next) { slow=slow->next; fast=fast->next->next; }
    ListNode* mid = slow->next;
    slow->next = nullptr;
 
    ListNode* l = sortList(head);
    ListNode* r = sortList(mid);
 
    // Merge two sorted lists
    ListNode dummy(0); ListNode* tail=&dummy;
    while (l && r) {
        if (l->val <= r->val) { tail->next=l; l=l->next; }
        else                  { tail->next=r; r=r->next; }
        tail=tail->next;
    }
    tail->next = l ? l : r;
    return dummy.next;
}
// Time: O(n log n), Space: O(log n) recursion stack