1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

def count_pairs_less_than(nums: list[int], target: int) -> int:
    """
    Count pairs whose sum is less than target.
    
    Time: O(n) - single pass with two pointers
    Space: O(1)
    
    Key insight: If nums[left] + nums[right] < target,
    then ALL pairs (left, left+1), (left, left+2), ..., (left, right)
    are valid. That's (right - left) pairs.
    """
    nums.sort()  # Ensure sorted
    left = 0
    right = len(nums) - 1
    count = 0
    
    while left < right:
        if nums[left] + nums[right] < target:
            # All pairs (left, left+1..right) are valid
            count += right - left
            left += 1
        else:
            # Sum too large, try smaller right value
            right -= 1
    
    return count
 
 
def count_pairs_in_range(nums: list[int], lower: int, upper: int) -> int:
    """
    Count pairs whose sum is in range [lower, upper].
    
    Uses count_less_than as building block.
    """
    # pairs with sum < upper+1 minus pairs with sum < lower
    return count_pairs_less_than(nums, upper + 1) - count_pairs_less_than(nums, lower)
 
 
# How count_pairs_less_than works - detailed example:
# nums = [-1, 0, 1, 3], target = 2
# sorted: [-1, 0, 1, 3]
#
# left=0, right=3: -1 + 3 = 2, NOT < 2, so right--
# left=0, right=2: -1 + 1 = 0 < 2, so count += (2-0) = 2 pairs: (-1,0), (-1,1)
#                  left++
# left=1, right=2: 0 + 1 = 1 < 2, so count += (2-1) = 1 pair: (0,1)
#                  left++
# left=2, right=2: loop ends (left not < right)
#
# Wait, we're missing pairs! Let me recalculate...
# Actually (-1, 3) = 2 which is NOT < 2, so it's not counted. Correct.
# Pairs < 2: (-1,0)=-1, (-1,1)=0, (0,1)=1 -> 3 pairs
# Let me trace again...
 
def count_pairs_less_than_verbose(nums: list[int], target: int) -> int:
    """Verbose version for tracing."""
    nums.sort()
    left = 0
    right = len(nums) - 1
    count = 0
    
    print(f"Sorted nums: {nums}, target: {target}")
    
    while left < right:
        current_sum = nums[left] + nums[right]
        print(f"left={left} ({nums[left]}), right={right} ({nums[right]}), sum={current_sum}")
        
        if current_sum < target:
            pairs_added = right - left
            count += pairs_added
            print(f"  Sum < target. Adding {pairs_added} pairs. Total count: {count}")
            left += 1
        else:
            print(f"  Sum >= target. Moving right.")
            right -= 1
    
    print(f"Final count: {count}")
    return count
 
# Test
count_pairs_less_than_verbose([-1, 0, 1, 3], 2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

def pair_closest_to_target(nums: list[int], target: int) -> tuple[int, int]:
    """
    Find pair whose sum is closest to target.
    
    Time: O(n log n) for sorting + O(n) for search = O(n log n)
    Space: O(1)
    
    Returns:
        Tuple of (num1, num2) that form the closest sum
    """
    nums.sort()
    left = 0
    right = len(nums) - 1
    closest_sum = float('inf')
    best_pair = (nums[0], nums[1])
    
    while left < right:
        current_sum = nums[left] + nums[right]
        
        # Update if this sum is closer
        if abs(current_sum - target) < abs(closest_sum - target):
            closest_sum = current_sum
            best_pair = (nums[left], nums[right])
        
        # Exact match - can't do better
        if current_sum == target:
            return best_pair
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    
    return best_pair
 
 
def sum_closest_to_zero(nums: list[int]) -> tuple[int, int]:
    """
    Special case: find pair whose sum is closest to zero.
    
    This is equivalent to pair_closest_to_target with target=0.
    Commonly asked in interviews.
    """
    return pair_closest_to_target(nums, 0)
 
 
# Test
nums = [1, 60, -10, 70, -80, 85]
print(pair_closest_to_target(nums, 0))   # (-80, 85) sum = 5
print(pair_closest_to_target(nums, 100)) # (60, 70) sum = 130 or close alternative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def remove_duplicates_at_most_k(nums: list[int], k: int) -> int:
    """
    Remove duplicates allowing at most k copies of each element.
    
    Time: O(n)
    Space: O(1)
    
    Key insight: An element at position fast is valid if it differs from
    the element k positions before the current write position.
    
    If nums[fast] != nums[slow - k], we can add nums[fast].
    """
    if len(nums) <= k:
        return len(nums)
    
    slow = k  # First k elements are always valid
    
    for fast in range(k, len(nums)):
        # Compare with element k positions before slow
        if nums[fast] != nums[slow - k]:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow
 
 
def remove_duplicates_allow_two(nums: list[int]) -> int:
    """
    Special case: allow at most 2 copies.
    LeetCode 80: Remove Duplicates from Sorted Array II
    """
    return remove_duplicates_at_most_k(nums, 2)
 
 
# Detailed trace for k=2
def remove_duplicates_at_most_k_verbose(nums: list[int], k: int) -> int:
    print(f"Input: {nums}, k={k}")
    
    if len(nums) <= k:
        return len(nums)
    
    slow = k
    print(f"Starting slow={slow} (first {k} elements always kept)")
    
    for fast in range(k, len(nums)):
        compare_idx = slow - k
        print(f"fast={fast} ({nums[fast]}), slow={slow}, comparing with slow-k={compare_idx} ({nums[compare_idx]})")
        
        if nums[fast] != nums[slow - k]:
            print(f"  Different! nums[{slow}] = {nums[fast]}")
            nums[slow] = nums[fast]
            slow += 1
        else:
            print(f"  Same, skipping (already have k copies)")
    
    print(f"Final: {nums[:slow]}")
    return slow
 
 
# Test
nums = [1, 1, 1, 2, 2, 3]
remove_duplicates_at_most_k_verbose(nums, 2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

def remove_duplicates_unsorted(nums: list[int]) -> int:
    """
    Remove duplicates from unsorted array preserving first occurrence order.
    
    Time: O(n)
    Space: O(n) for the set
    
    Note: Can't do O(1) space for unsorted without O(n²) time.
    """
    seen = set()
    slow = 0
    
    for fast in range(len(nums)):
        if nums[fast] not in seen:
            seen.add(nums[fast])
            nums[slow] = nums[fast]
            slow += 1
    
    return slow
 
 
def remove_duplicates_unsorted_sorted_order(nums: list[int]) -> list[int]:
    """
    Remove duplicates and return in sorted order.
    
    Simpler: just convert to set and sort.
    Time: O(n log n) for sort
    Space: O(n)
    """
    return sorted(set(nums))
 
 
# When order matters and we want O(1) space:
# Option 1: Sort first, then use sorted dedup
# Trade-off: Destroys original order
 
def remove_duplicates_minimal_space(nums: list[int]) -> int:
    """
    Remove duplicates with O(1) space by sorting first.
    Original order is NOT preserved.
    
    Time: O(n log n) for sort + O(n) for dedup
    Space: O(1) if sort is in-place
    """
    nums.sort()
    
    if not nums:
        return 0
    
    slow = 1
    for fast in range(1, len(nums)):
        if nums[fast] != nums[fast - 1]:
            nums[slow] = nums[fast]
            slow += 1
    
    return slow
 
 
# Test
nums = [3, 1, 2, 1, 3, 2, 4]
length = remove_duplicates_unsorted(nums)
print(nums[:length])  # [3, 1, 2, 4] - order preserved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

def lomuto_partition(arr: list[int], low: int, high: int) -> int:
    """
    Lomuto partition: partition array around last element.
    
    After partition:
    - arr[low:pivot_idx] < pivot
    - arr[pivot_idx] = pivot
    - arr[pivot_idx+1:high+1] >= pivot
    
    Time: O(n) where n = high - low + 1
    Space: O(1)
    
    Returns:
        Final position of the pivot element
    """
    pivot = arr[high]  # Choose last element as pivot
    i = low - 1        # Boundary for elements < pivot
    
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    
    # Place pivot in its final position
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1
 
 
def quick_sort_lomuto(arr: list[int], low: int, high: int) -> None:
    """QuickSort using Lomuto partition."""
    if low < high:
        pivot_idx = lomuto_partition(arr, low, high)
        quick_sort_lomuto(arr, low, pivot_idx - 1)
        quick_sort_lomuto(arr, pivot_idx + 1, high)
 
 
# Trace example
def lomuto_partition_verbose(arr: list[int], low: int, high: int) -> int:
    print(f"Partitioning arr[{low}:{high+1}] = {arr[low:high+1]}")
    pivot = arr[high]
    print(f"Pivot = {pivot}")
    
    i = low - 1
    
    for j in range(low, high):
        print(f"  j={j}, arr[j]={arr[j]}, i={i}")
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
            print(f"    {arr[j-1]} < {pivot}, swapped, i now {i}, array: {arr}")
    
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    print(f"  Placed pivot at index {i+1}")
    print(f"  Result: {arr}")
    return i + 1
 
 
# Test
arr = [10, 80, 30, 90, 40, 50, 70]
lomuto_partition_verbose(arr, 0, len(arr) - 1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

def hoare_partition(arr: list[int], low: int, high: int) -> int:
    """
    Hoare partition: two pointers from opposite ends.
    
    More efficient than Lomuto (fewer swaps on average).
    
    Returns: partition point (not final pivot position)
    Note: Pivot may not be at the returned index!
    
    After partition:
    - arr[low:result+1] <= pivot
    - arr[result+1:high+1] > pivot
    
    Time: O(n)
    Space: O(1)
    """
    pivot = arr[low]  # Choose first element as pivot
    i = low - 1
    j = high + 1
    
    while True:
        # Move i right until we find element >= pivot
        i += 1
        while arr[i] < pivot:
            i += 1
        
        # Move j left until we find element <= pivot
        j -= 1
        while arr[j] > pivot:
            j -= 1
        
        # If pointers crossed, we're done
        if i >= j:
            return j
        
        # Swap elements at i and j
        arr[i], arr[j] = arr[j], arr[i]
 
 
def quick_sort_hoare(arr: list[int], low: int, high: int) -> None:
    """QuickSort using Hoare partition."""
    if low < high:
        partition_point = hoare_partition(arr, low, high)
        quick_sort_hoare(arr, low, partition_point)      # Note: partition_point, not partition_point - 1
        quick_sort_hoare(arr, partition_point + 1, high)
 
 
# Why Hoare is more efficient:
# - On average, 3x fewer swaps than Lomuto
# - Both are O(n) but constant factor matters
# - Lomuto does poorly on arrays with many duplicates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

def sort_colors(nums: list[int]) -> None:
    """
    Dutch National Flag: Sort array with values 0, 1, 2.
    
    LeetCode 75: Sort Colors
    
    Uses THREE pointers:
    - low: boundary for 0s (next position for 0)
    - mid: current element being examined
    - high: boundary for 2s (next position for 2, from end)
    
    Invariant:
    - nums[0:low] contains 0s
    - nums[low:mid] contains 1s
    - nums[mid:high+1] is unprocessed
    - nums[high+1:] contains 2s
    
    Time: O(n) - single pass
    Space: O(1)
    """
    low = 0
    mid = 0
    high = len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:
            # Swap to low region, advance both
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            # Swap to high region, only move high
            # (mid stays because we need to check the swapped element)
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
        else:  # nums[mid] == 1
            # Already in middle, just advance
            mid += 1
 
 
def sort_colors_verbose(nums: list[int]) -> None:
    """Dutch National Flag with detailed trace."""
    print(f"Input: {nums}")
    low = 0
    mid = 0
    high = len(nums) - 1
    
    step = 0
    while mid <= high:
        step += 1
        print(f"\nStep {step}: low={low}, mid={mid}, high={high}")
        print(f"  Current: {nums}")
        print(f"  Examining nums[{mid}] = {nums[mid]}")
        
        if nums[mid] == 0:
            print(f"  0 found: swap with low position {low}")
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 2:
            print(f"  2 found: swap with high position {high}")
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            print(f"  mid stays (new element needs checking)")
        else:
            print(f"  1 found: already in place, advance mid")
            mid += 1
    
    print(f"\nFinal: {nums}")
 
 
# Test
nums = [2, 0, 2, 1, 1, 0]
sort_colors_verbose(nums)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

def segregate_odd_even(nums: list[int]) -> None:
    """
    Move all even numbers before odd numbers.
    
    Time: O(n)
    Space: O(1)
    """
    left = 0  # Next position for even
    
    for right in range(len(nums)):
        if nums[right] % 2 == 0:  # Even number
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
 
 
def segregate_positives_negatives(nums: list[int]) -> None:
    """
    Move all negative numbers before positive numbers.
    Maintains relative order within each group.
    
    Time: O(n)
    Space: O(1)
    """
    left = 0  # Next position for negative
    
    for right in range(len(nums)):
        if nums[right] < 0:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
 
 
def segregate_alternating_positive_negative(nums: list[int]) -> None:
    """
    Rearrange to alternate positive and negative numbers.
    
    Example: [-1, 2, -3, 4, 5, -6] -> [2, -1, 4, -3, 5, -6] or similar
    
    Strategy:
    1. First segregate positives and negatives
    2. Then swap every other element from the larger group
    """
    # Step 1: Segregate
    neg_end = 0
    for i in range(len(nums)):
        if nums[i] < 0:
            nums[neg_end], nums[i] = nums[i], nums[neg_end]
            neg_end += 1
    
    # Now: nums[0:neg_end] are negative, nums[neg_end:] are positive
    
    # Step 2: Interleave
    # Swap negative at odd index with positive at even index
    negative = 0
    positive = neg_end
    
    # Skip first negative (it's at even index, which is fine for pattern: pos, neg, pos, neg...)
    # Actually we want: pos at 0, neg at 1, pos at 2, neg at 3...
    result = [0] * len(nums)
    pos_idx, neg_idx = 0, 1
    
    for num in nums:
        if num >= 0 and pos_idx < len(nums):
            result[pos_idx] = num
            pos_idx += 2
        elif num < 0 and neg_idx < len(nums):
            result[neg_idx] = num
            neg_idx += 2
    
    # Handle overflow (more positives than negatives or vice versa)
    # Fill remaining spots
    for num in nums:
        if num >= 0 and pos_idx < len(nums):
            result[pos_idx] = num
            pos_idx += 2
        elif num >= 0 and neg_idx < len(nums):
            result[neg_idx] = num  # Use negative slots for extra positives
            neg_idx += 2
        elif num < 0 and neg_idx < len(nums):
            result[neg_idx] = num
            neg_idx += 2
        elif num < 0 and pos_idx < len(nums):
            result[pos_idx] = num  # Use positive slots for extra negatives
            pos_idx += 2
    
    nums[:] = result  # Copy back
 
# Simpler version assuming equal counts:
def rearrange_alternating(nums: list[int]) -> list[int]:
    """
    Rearrange with alternating signs (assuming equal positive/negative counts).
    Returns new array (not in-place for simplicity).
    """
    positives = [x for x in nums if x >= 0]
    negatives = [x for x in nums if x < 0]
    
    result = []
    i, j = 0, 0
    
    while i < len(positives) and j < len(negatives):
        result.append(positives[i])
        result.append(negatives[j])
        i += 1
        j += 1
    
    # Append remaining
    result.extend(positives[i:])
    result.extend(negatives[j:])
    
    return result
 
 
# Tests
nums1 = [1, 2, 3, 4, 5, 6]
segregate_odd_even(nums1)
print(nums1)  # [2, 4, 6, 1, 3, 5] (evens first)
 
nums2 = [12, -7, 5, -3, 0, 4, -2]
segregate_positives_negatives(nums2)
print(nums2)  # [-7, -3, -2, 12, 0, 4, 5] (negatives first)
 
nums3 = [1, 2, 3, -4, -1, 4]
print(rearrange_alternating(nums3))  # [1, -4, 2, -1, 3, 4]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

def intersection_sorted(arr1: list[int], arr2: list[int]) -> list[int]:
    """
    Find intersection of two SORTED arrays.
    
    Time: O(m + n)
    Space: O(min(m, n)) for result
    """
    result = []
    i, j = 0, 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] == arr2[j]:
            # Skip duplicates
            if not result or result[-1] != arr1[i]:
                result.append(arr1[i])
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1
    
    return result
 
 
def union_sorted(arr1: list[int], arr2: list[int]) -> list[int]:
    """
    Find union of two SORTED arrays (all unique elements from both).
    
    Time: O(m + n)
    Space: O(m + n) for result
    """
    result = []
    i, j = 0, 0
    
    def add_unique(val):
        if not result or result[-1] != val:
            result.append(val)
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            add_unique(arr1[i])
            i += 1
        elif arr1[i] > arr2[j]:
            add_unique(arr2[j])
            j += 1
        else:  # Equal
            add_unique(arr1[i])
            i += 1
            j += 1
    
    # Add remaining from arr1
    while i < len(arr1):
        add_unique(arr1[i])
        i += 1
    
    # Add remaining from arr2
    while j < len(arr2):
        add_unique(arr2[j])
        j += 1
    
    return result
 
 
def merge_sorted_arrays(arr1: list[int], arr2: list[int]) -> list[int]:
    """
    Merge two sorted arrays (may include duplicates).
    
    This is the merge step of merge sort.
    
    Time: O(m + n)
    Space: O(m + n)
    """
    result = []
    i, j = 0, 0
    
    while i < len(arr1) and j < len(arr2):
        if arr1[i] <= arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1
    
    result.extend(arr1[i:])
    result.extend(arr2[j:])
    
    return result
 
 
# Tests
arr1 = [1, 2, 4, 5, 6]
arr2 = [2, 3, 5, 7]
 
print(intersection_sorted(arr1, arr2))  # [2, 5]
print(union_sorted(arr1, arr2))         # [1, 2, 3, 4, 5, 6, 7]
print(merge_sorted_arrays(arr1, arr2))  # [1, 2, 2, 3, 4, 5, 5, 6, 7]