Day 8 – LeetCode Problems: Move Zeros, Union & Intersection, Missing Number

Today I practiced some common array manipulation patterns by solving several LeetCode problems using both brute-force and optimal approaches. I also reviewed XOR tricks and classic techniques like sum formulas for missing number questions.

---

LeetCode 283 – Move Zeroes

Goal: Move all 0s to the end while maintaining the order of non-zero elements.

---

Approach 1: Temp Vector (Brute)

void moveZeroes(vector<int>& nums) {
    vector<int> temp;
    for (int i : nums) if (i != 0) temp.push_back(i);

    for (int i = 0; i < temp.size(); i++)
        nums[i] = temp[i];

    for (int i = temp.size(); i < nums.size(); i++)
        nums[i] = 0;
}
// TC: O(n), SC: O(n)

---

Approach 2: Two Pointer Swapping (Optimal)

void moveZeroes(vector<int>& nums) {
    int i = 0;
    for (int j = 0; j < nums.size(); j++) {
        if (nums[j] != 0) {
            swap(nums[i], nums[j]);
            i++;
        }
    }
}
// TC: O(n), SC: O(1)

This method keeps all non-zero elements at the front and fills the rest with zeros through swapping.

---

Union and Intersection of Two Arrays

---

Union – Brute Force

vector<int> unionBrute(vector<int>& a, vector<int>& b) {
    set<int> s;
    for (int i : a) s.insert(i);
    for (int i : b) s.insert(i);

    return vector<int>(s.begin(), s.end());
}
// TC: O((n + m) log n), SC: O(n + m)

---

Union – Optimal (If Arrays Are Sorted)

vector<int> unionOptimal(vector<int>& a, vector<int>& b) {
    int i = 0, j = 0;
    vector<int> res;
    while (i < a.size() && j < b.size()) {
        if (a[i] < b[j]) res.push_back(a[i++]);
        else if (b[j] < a[i]) res.push_back(b[j++]);
        else {
            res.push_back(a[i]);
            i++; j++;
        }
    }
    while (i < a.size()) res.push_back(a[i++]);
    while (j < b.size()) res.push_back(b[j++]);
    return res;
}
// TC: O(n + m), SC: O(n + m)

---

Intersection – Brute Force

vector<int> intersectBrute(vector<int>& a, vector<int>& b) {
    vector<int> res;
    vector<bool> used(b.size(), false);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            if (a[i] == b[j] && !used[j]) {
                res.push_back(a[i]);
                used[j] = true;
                break;
            }
        }
    }
    return res;
}
// TC: O(n*m), SC: O(m)

---

Intersection – Optimal (If Arrays Are Sorted)

vector<int> intersectOptimal(vector<int>& a, vector<int>& b) {
    int i = 0, j = 0;
    vector<int> res;
    while (i < a.size() && j < b.size()) {
        if (a[i] == b[j]) {
            res.push_back(a[i]);
            i++; j++;
        } else if (a[i] < b[j]) {
            i++;
        } else {
            j++;
        }
    }
    return res;
}
// TC: O(n + m), SC: O(n + m)

---

LeetCode 268 – Missing Number

Array of size n, containing numbers from 0 to n. Find the missing one.

---

Approach 1: Brute Force

int missingNumber(vector<int>& nums) {
    for (int i = 0; i <= nums.size(); i++) {
        bool found = false;
        for (int j : nums)
            if (j == i) found = true;
        if (!found) return i;
    }
    return -1;
}
// TC: O(n²), SC: O(1)

---

Approach 2: Better – Use a Hash Map

int missingNumber(vector<int>& nums) {
    unordered_map<int, bool> seen;
    for (int num : nums) seen[num] = true;

    for (int i = 0; i <= nums.size(); i++)
        if (!seen[i]) return i;
    return -1;
}
// TC: O(n), SC: O(n)

---

Approach 3: Mathematical Summation

int missingNumber(vector<int>& nums) {
    int n = nums.size();
    int sum = n * (n + 1) / 2;
    int actualSum = accumulate(nums.begin(), nums.end(), 0);
    return sum - actualSum;
}
// TC: O(n), SC: O(1)

---

Approach 4: XOR Method

int missingNumber(vector<int>& nums) {
    int xor1 = 0, xor2 = 0, n = nums.size();

    for (int i = 0; i < n; i++) {
        xor1 ^= nums[i];
        xor2 ^= i;
    }
    xor2 ^= n;
    return xor1 ^ xor2;
}
// TC: O(n), SC: O(1)

---

Summary:

• Solved array problems involving shifting, frequency, and uniqueness

• Practiced both brute force and optimal strategies

• Reinforced XOR tricks and mathematical reasoning

• Understood union/intersection logic under both sorted and unsorted cases

• Felt confident solving and optimizing well-known LeetCode problems