Array Tricks (Majority Element, Missing Number, Product Except Self)

Majority Element (LeetCode 169)

Boyer-Moore Voting Algorithm: Elements cancel each other out; the last remaining one is the majority element.

int majorityElement(int[] nums) {
    int count = 0, candidate = 0;
    for (int n : nums) {
        if (count == 0) candidate = n;
        count += (n == candidate) ? 1 : -1;
    }
    return candidate;
}

Complexity: O(n) time, O(1) space. Does not require verification if the problem guarantees a majority element.

Majority Element II (LeetCode 229): Find all elements that appear more than n/3 times (at most two). Use two candidates for voting.

Missing Number (LeetCode 268)

An array contains all integers from [0, n] except for one.

Mathematical Approach (Gauss Summation):

int missingNumber(int[] nums) {
    int n = nums.length;
    int expectedSum = n * (n + 1) / 2;
    int actualSum = 0;
    for (int num : nums) actualSum += num;
    return expectedSum - actualSum;
}

Bit Manipulation (XOR):

int missingNumberXor(int[] nums) {
    int result = nums.length;
    for (int i = 0; i < nums.length; i++) {
        // Numbers that appear twice (once as an index, once in the array) cancel out
        result ^= i ^ nums[i]; 
    }
    return result;
}

Product of Array Except Self (LeetCode 238)

Find the product of all elements except nums[i] in O(n) time, without using division and in O(1) extra space (excluding the output array).

int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];

    // 1. Calculate prefix products (products of all elements to the left)
    result[0] = 1;
    for (int i = 1; i < n; i++) result[i] = result[i - 1] * nums[i - 1];

    // 2. Multiply by suffix products (products of all elements to the right)
    int rightProduct = 1;
    for (int i = n - 1; i >= 0; i--) {
        result[i] *= rightProduct;
        rightProduct *= nums[i];
    }
    return result;
}

Philosophy: result[i] = (product of left side) * (product of right side). We achieve this through two passes over the array.

Find All Numbers Disappeared in an Array (LeetCode 448)

Use the array itself as a hash table by negating values at indices corresponding to the numbers seen.

List<Integer> findDisappearedNumbers(int[] nums) {
    // Treat values as indices and mark those indices by negating their values
    for (int num : nums) {
        int idx = Math.abs(num) - 1;
        if (nums[idx] > 0) nums[idx] *= -1;
    }
    
    List<Integer> result = new ArrayList<>();
    // Indices staying positive were never reached/seen
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) result.add(i + 1);
    }
    return result;
}

Find the Duplicate Number (LeetCode 287)

Given an array containing n+1 integers where each integer is between 1 and n. Find the duplicate in O(n) time and O(1) space.

Floyd's Tortoise and Hare (Cycle Detection): Treat the array as a Linked List where nums[i] is the "next" pointer.

int findDuplicate(int[] nums) {
    // Find intersection in the cycle
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    
    // Find the entrance to the cycle (the duplicate number)
    fast = 0;
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}