Single Number

Given a non-empty array of integers where every element appears twice except for one, find that single one using bitwise XOR.

The XOR operation has two critical properties: commutativity (a ^ b == b ^ a) and identity (x ^ x == 0 and x ^ 0 == x). Consequently, XORing all numbers in the array cancels out the pairs, leaving the unique number.

Time complexity: O(n), Space complexity: O(1).

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (const int& val : nums) {
            result ^= val;
        }
        return result;
    }
};

Majority Element

The majority element is the element that appears more than ⌊n/2⌋ times. The Boyer-Moore Voting Algorithm is an optimal approach that maintains a candidate and a counter.

When the counter is zero, the current element becomes the new candidate. If the current element matches the candidate, the counter increments; otherwise, it decrements. The candidate that survives this process is the majority element.

Time complexity: O(n), Space complexity: O(1).

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int tally = 0;
        
        for (const int& val : nums) {
            if (tally == 0) {
                candidate = val;
                tally = 1;
            } else if (candidate == val) {
                tally++;
            } else {
                tally--;
            }
        }
        return candidate;
    }
};

Sort Colors

Sort an array containing only 0s, 1s, and 2s in-place. A two-pass counting approach involves tallying the occurrences of each value and then overwriting the array.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0};
        
        for (int x : nums) {
            count[x]++;
        }
        
        int idx = 0;
        for (int i = 0; i < 3; ++i) {
            while (count[i]-- > 0) {
                nums[idx++] = i;
            }
        }
    }
};

Next Permutation

Rearrange numbers into the lexicographically next greater permutation. If such arrangement is not possible, it must rearrange it as the lowest possible order (sorted in ascending order).

The logic involves three steps:

1. Find the largest index i such that nums[i] < nums[i + 1]. If no such index exists, the permutation is the last one.
2. Find the largest index j greater than i such that nums[i] < nums[j].
3. Swap the value of nums[i] with that of nums[j].
4. Reverse the sequence from nums[i + 1] up to and including the final element.

Time complexity: O(n), Space complexity: O(1).

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        int k = n - 2;
        
        // Find the first decreasing element from the end
        while (k >= 0 && nums[k] >= nums[k + 1]) {
            k--;
        }
        
        if (k >= 0) {
            int l = n - 1;
            // Find the element just larger than nums[k]
            while (l >= 0 && nums[l] <= nums[k]) {
                l--;
            }
            swap(nums[k], nums[l]);
        }
        
        // Reverse the suffix
        reverse(nums.begin() + k + 1, nums.end());
    }
};

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive, prove that at least one duplicate number must exist. Assume that there is only one duplicate number, but it could be repeated more than once.

This problem maps perfectly to a linked list cycle detection (Floyd's Tortoise and Hare). Treat the array indices as nodes and nums[i] as pointers to the next node. Since there is a duplicate, a cycle exists.

The algorithm proceeds in two phases:

1. Intersection: Move a slow pointer one step and a fast pointer two steps until they meet inside the cycle.
2. Entrance: Reset one pointer to the start. Move both pointers one step at a time until they meet again at the cycle's entrance.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = 0;
        int fast = 0;
        
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);
        
        // Find the entrance to the cycle
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        
        return fast;
    }
};