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

/**
 * Two Sum: Brute Force Approach
 * Time: O(n²) - nested loops check all pairs
 * Space: O(1) - no extra data structures
 */
function twoSumBruteForce(nums: number[], target: number): [number, number] | null {
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    
    return null; // No solution found
}
 
// Analysis of the nested loop:
// When i = 0: j runs from 1 to n-1 → n-1 comparisons
// When i = 1: j runs from 2 to n-1 → n-2 comparisons
// ...
// When i = n-2: j runs from n-1 to n-1 → 1 comparison
// Total: (n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n²)
 
// Example
console.log(twoSumBruteForce([2, 7, 11, 15], 9)); // [0, 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
52
53
54
55
56
57
58
59
60
61

/**
 * Two Sum: Hash Table Approach (Two-Pass)
 * Time: O(n) - two sequential passes
 * Space: O(n) - hash table stores up to n elements
 * 
 * Pass 1: Build a map from value → index
 * Pass 2: For each element, look up its complement
 */
function twoSumTwoPass(nums: number[], target: number): [number, number] | null {
    // Pass 1: Build the lookup table
    const valueToIndex = new Map<number, number>();
    for (let i = 0; i < nums.length; i++) {
        valueToIndex.set(nums[i], i);
    }
    
    // Pass 2: Find complements
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        const complementIndex = valueToIndex.get(complement);
        
        // Check: complement exists AND is not the same element
        if (complementIndex !== undefined && complementIndex !== i) {
            return [i, complementIndex];
        }
    }
    
    return null;
}
 
/**
 * Two Sum: Hash Table Approach (One-Pass)
 * Time: O(n) - single pass
 * Space: O(n) - hash table stores up to n elements
 * 
 * Key insight: As we iterate, we check if complement was seen BEFORE
 * This handles the "don't use same element twice" constraint naturally
 */
function twoSumOnePass(nums: number[], target: number): [number, number] | null {
    const valueToIndex = new Map<number, number>();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // Check if complement was seen in previous elements
        if (valueToIndex.has(complement)) {
            return [valueToIndex.get(complement)!, i];
        }
        
        // Add current element to the map (after checking!)
        valueToIndex.set(nums[i], i);
    }
    
    return null;
}
 
// Example walkthrough of one-pass:
// nums = [2, 7, 11, 15], target = 9
// i=0: complement = 9-2 = 7, map = {} → 7 not found → add 2:0 → map = {2:0}
// i=1: complement = 9-7 = 2, map = {2:0} → 2 found at index 0! return [0, 1]
 
console.log(twoSumOnePass([2, 7, 11, 15], 9)); // [0, 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

// Edge Case: Duplicates
// nums = [3, 3], target = 6
 
// Two-pass approach with duplicates:
// Pass 1: Build map → {3: 1} (second occurrence overwrites first!)
// Pass 2: i=0, complement=3, map[3]=1, 1 !== 0 → return [0, 1] ✓
 
// One-pass approach with duplicates:
// i=0: complement = 3, map = {} → not found → add 3:0 → map = {3:0}
// i=1: complement = 3, map = {3:0} → found at index 0! → return [0, 1] ✓
 
// Both work! But for different reasons:
// - Two-pass: We check complementIndex !== i, so overwriting is safe
// - One-pass: We find the PREVIOUS occurrence naturally
 
function twoSumDuplicatesSafe(nums: number[], target: number): [number, number] | null {
    const valueToIndex = new Map<number, number>();
    
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        
        // For duplicates summing to target, the complement IS the current value
        // But we check the map BEFORE adding, so we find the earlier index
        if (valueToIndex.has(complement)) {
            return [valueToIndex.get(complement)!, i];
        }
        
        valueToIndex.set(nums[i], i);
    }
    
    return null;
}
 
console.log(twoSumDuplicatesSafe([3, 3], 6)); // [0, 1] ✓

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Edge Case: Self-complement with only one occurrence
// nums = [3, 2, 4], target = 6
 
// One-pass trace:
// i=0: num=3, complement=6-3=3, map={} → 3 not found → add 3:0
// i=1: num=2, complement=6-2=4, map={3:0} → 4 not found → add 2:1  
// i=2: num=4, complement=6-4=2, map={3:0, 2:1} → 2 found! → return [1, 2]
 
// The 3 correctly doesn't match with itself because complement (3)
// isn't in the map when we're processing the 3.
 
// Counter-example where self-complement SHOULD match:
// nums = [3, 3, 2, 4], target = 6
// i=0: num=3, complement=3, map={} → not found → add 3:0
// i=1: num=3, complement=3, map={3:0} → found! → return [0, 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

/**
 * Two Sum II: Input is Sorted (Two Pointer Approach)
 * Time: O(n), Space: O(1)
 * 
 * Key insight: If sum is too small, move left pointer right
 *              If sum is too large, move right pointer left
 */
function twoSumSorted(nums: number[], target: number): [number, number] | null {
    let left = 0;
    let right = nums.length - 1;
    
    while (left < right) {
        const sum = nums[left] + nums[right];
        
        if (sum === target) {
            return [left, right];
        } else if (sum < target) {
            left++;  // Need larger sum, move left pointer right
        } else {
            right--; // Need smaller sum, move right pointer left
        }
    }
    
    return null;
}
 
// Example: nums = [2, 7, 11, 15], target = 9
// left=0 (2), right=3 (15): sum=17 > 9 → right--
// left=0 (2), right=2 (11): sum=13 > 9 → right--
// left=0 (2), right=1 (7): sum=9 = 9 → return [0, 1]
 
console.log(twoSumSorted([2, 7, 11, 15], 9)); // [0, 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

/**
 * Two Sum: Find All Pairs (by indices)
 * Time: O(n), Space: O(n)
 * 
 * Key insight: Store ALL indices for each value, not just one
 */
function twoSumAllPairs(nums: number[], target: number): [number, number][] {
    const result: [number, number][] = [];
    const valueToIndices = new Map<number, number[]>();
    
    // Build map: value → all indices where it appears
    for (let i = 0; i < nums.length; i++) {
        if (!valueToIndices.has(nums[i])) {
            valueToIndices.set(nums[i], []);
        }
        valueToIndices.get(nums[i])!.push(i);
    }
    
    // Find all pairs
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        const complementIndices = valueToIndices.get(complement) ?? [];
        
        for (const j of complementIndices) {
            // Only include pairs where i < j to avoid duplicates
            if (i < j) {
                result.push([i, j]);
            }
        }
    }
    
    return result;
}
 
// Example: nums = [1, 5, 3, 3, 3], target = 6
// Pairs: (1,5), (3,3), (3,3), (3,3) - but which indices?
console.log(twoSumAllPairs([1, 5, 3, 3, 3], 6));
// [[0,1], [2,3], [2,4], [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

/**
 * Two Sum: Count Unique Value Pairs
 * Time: O(n), Space: O(n)
 * 
 * Count pairs of VALUES (not indices) that sum to target
 */
function countTwoSumPairs(nums: number[], target: number): number {
    const freq = new Map<number, number>();
    
    // Count frequency of each value
    for (const num of nums) {
        freq.set(num, (freq.get(num) ?? 0) + 1);
    }
    
    let count = 0;
    const counted = new Set<number>();
    
    for (const [num, numFreq] of freq) {
        const complement = target - num;
        
        // Skip if we've already counted this pair
        if (counted.has(num)) continue;
        
        if (num === complement) {
            // Self-pairing: need at least 2 of the same value
            // Number of pairs = C(n,2) = n*(n-1)/2
            if (numFreq >= 2) {
                count += (numFreq * (numFreq - 1)) / 2;
            }
        } else if (freq.has(complement)) {
            // Cross-pairing: every occurrence of num can pair with
            // every occurrence of complement
            count += numFreq * freq.get(complement)!;
            counted.add(complement); // Mark complement as counted
        }
        
        counted.add(num);
    }
    
    return count;
}
 
// Example: nums = [1, 5, 3, 3, 3], target = 6
// Pairs: 1+5=6 (1 pair), 3+3=6 (3 choose 2 = 3 pairs) = 4 total
console.log(countTwoSumPairs([1, 5, 3, 3, 3], 6)); // 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

/**
 * TwoSum III - Data Structure Design
 * 
 * Supports:
 * - add(number): Add to the data structure
 * - find(target): Check if any pair sums to target
 */
class TwoSumStream {
    private freq = new Map<number, number>();
    
    /**
     * Add a number to the data structure
     * Time: O(1)
     */
    add(number: number): void {
        this.freq.set(number, (this.freq.get(number) ?? 0) + 1);
    }
    
    /**
     * Check if there exists any pair that sums to target
     * Time: O(n) where n is the number of unique values
     */
    find(target: number): boolean {
        for (const [num, count] of this.freq) {
            const complement = target - num;
            
            if (num === complement) {
                // Need at least 2 occurrences
                if (count >= 2) return true;
            } else {
                // Need complement to exist
                if (this.freq.has(complement)) return true;
            }
        }
        
        return false;
    }
}
 
// Usage
const ts = new TwoSumStream();
ts.add(1);
ts.add(3);
ts.add(5);
console.log(ts.find(4));  // true (1 + 3)
console.log(ts.find(7));  // false (no pair sums to 7... wait, 3+5=8, 1+5=6)
                          // Actually false - no pair sums to exactly 7
ts.add(4);
console.log(ts.find(7));  // true (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

/**
 * Three Sum: Find All Unique Triplets
 * 
 * Approach: Sort + Two Pointers (more efficient than hash-based for this problem)
 * Time: O(n²), Space: O(1) excluding output
 * 
 * Key insight: Fix one element, then find Two-Sum on the remaining sorted array
 */
function threeSum(nums: number[]): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    // Sorting enables two-pointer technique and easy duplicate skipping
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < n - 2; i++) {
        // Skip duplicates for the first element
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        // If smallest element is positive, no triplet can sum to 0
        if (nums[i] > 0) break;
        
        // Two-pointer Two-Sum for target = -nums[i]
        let left = i + 1;
        let right = n - 1;
        const target = -nums[i];
        
        while (left < right) {
            const sum = nums[left] + nums[right];
            
            if (sum === target) {
                result.push([nums[i], nums[left], nums[right]]);
                
                // Skip duplicates for second and third elements
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}
 
// Example
console.log(threeSum([-1, 0, 1, 2, -1, -4]));
// [[-1, -1, 2], [-1, 0, 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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

/**
 * K-Sum: Generalized Solution
 * Time: O(n^(k-1)) for k-sum
 * 
 * Recursively reduce k-sum to (k-1)-sum until we reach 2-sum (two pointers)
 */
function kSum(nums: number[], target: number, k: number): number[][] {
    nums.sort((a, b) => a - b);
    return kSumHelper(nums, target, k, 0);
}
 
function kSumHelper(
    nums: number[], 
    target: number, 
    k: number, 
    start: number
): number[][] {
    const result: number[][] = [];
    const n = nums.length;
    
    // Base case: 2-sum with two pointers
    if (k === 2) {
        let left = start;
        let right = n - 1;
        
        while (left < right) {
            const sum = nums[left] + nums[right];
            
            if (sum === target) {
                result.push([nums[left], nums[right]]);
                while (left < right && nums[left] === nums[left + 1]) left++;
                while (left < right && nums[right] === nums[right - 1]) right--;
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return result;
    }
    
    // Recursive case: reduce k-sum to (k-1)-sum
    for (let i = start; i <= n - k; i++) {
        // Skip duplicates
        if (i > start && nums[i] === nums[i - 1]) continue;
        
        // Pruning: if smallest k elements exceed target, break
        let minSum = 0;
        for (let j = 0; j < k; j++) minSum += nums[i + j];
        if (minSum > target) break;
        
        // Pruning: if nums[i] + largest (k-1) elements < target, skip
        let maxSum = nums[i];
        for (let j = 0; j < k - 1; j++) maxSum += nums[n - 1 - j];
        if (maxSum < target) continue;
        
        // Recurse: find (k-1)-sum for target - nums[i]
        const subResults = kSumHelper(nums, target - nums[i], k - 1, i + 1);
        
        for (const sub of subResults) {
            result.push([nums[i], ...sub]);
        }
    }
    
    return result;
}
 
// Example: 4-sum
console.log(kSum([1, 0, -1, 0, -2, 2], 0, 4));
// [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 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

/**
 * Find pair with given difference
 * 
 * If a - b = target, then:
 * - a = b + target (looking for larger element)
 * - b = a - target (looking for smaller element)
 * 
 * Time: O(n), Space: O(n)
 */
function findPairWithDifference(
    nums: number[], 
    target: number
): [number, number] | null {
    const seen = new Set<number>();
    
    // Handle negative target by taking absolute value
    // (difference is typically defined as positive)
    const diff = Math.abs(target);
    
    for (const num of nums) {
        // Check if num - diff exists (num is the larger element)
        if (seen.has(num - diff)) {
            return [num - diff, num];
        }
        
        // Check if num + diff exists (num is the smaller element)
        if (seen.has(num + diff)) {
            return [num, num + diff];
        }
        
        seen.add(num);
    }
    
    return null;
}
 
// Example: find pair with difference 3
console.log(findPairWithDifference([5, 20, 3, 2, 50, 80], 3)); // [2, 5] or [20, 23]?
// [2, 5] because 5 - 2 = 3

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

from typing import List, Optional, Tuple
 
def find_pair_with_product(
    nums: List[int], 
    target: int
) -> Optional[Tuple[int, int]]:
    """
    Find pair with given product.
    
    If a * b = target, then b = target / a (for a != 0)
    
    Time: O(n), Space: O(n)
    """
    if target == 0:
        # Special case: need a zero and any other element
        has_zero = False
        has_nonzero = False
        
        for num in nums:
            if num == 0:
                has_zero = True
            else:
                has_nonzero = True
            
            if has_zero and has_nonzero:
                return (0, nums[0] if nums[0] != 0 else nums[1])
        
        return None
    
    seen = set()
    
    for num in nums:
        if num == 0:
            continue  # Can't divide by zero
        
        if target % num == 0:  # Only check if divisible (integer pairs)
            complement = target // num
            if complement in seen:
                return (complement, num)
        
        seen.add(num)
    
    return None
 
 
# Example
print(find_pair_with_product([2, 4, 6, 8, 10], 24))  # (4, 6)
print(find_pair_with_product([2, 4, 6, 8, 10], 25))  # None (no integer pair)

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

/**
 * Find pair with given XOR
 * 
 * Key insight: If a XOR b = target, then a XOR target = b
 * (XOR is its own inverse!)
 * 
 * Time: O(n), Space: O(n)
 */
function findPairWithXOR(nums: number[], target: number): [number, number] | null {
    const seen = new Set<number>();
    
    for (const num of nums) {
        // The complement is: num XOR target
        // Because: if (a XOR b = target), then (a XOR target = b)
        const complement = num ^ target;
        
        if (seen.has(complement)) {
            return [complement, num];
        }
        
        seen.add(num);
    }
    
    return null;
}
 
// Example: find pair with XOR = 6
// 5 XOR 3 = 6 (binary: 101 XOR 011 = 110)
console.log(findPairWithXOR([5, 4, 10, 15, 7, 3], 6)); // [5, 3]