Day 9 – Consecutive Ones, Unique Element, Subarray Sums, and Two Sum

Today I practiced several key problems involving frequency, prefix sums, and subarrays using both brute-force and optimized approaches. These problems are common in coding rounds and help reinforce hashing, XOR logic, and two-pointer patterns.

---

LeetCode 485 – Max Consecutive Ones

Problem:

Count the maximum number of consecutive 1s in a binary array.

int findMaxConsecutiveOnes(vector<int>& nums) {
    int count = 0, maxCount = 0;
    for (int n : nums) {
        if (n == 1) count++;
        else count = 0;
        maxCount = max(maxCount, count);
    }
    return maxCount;
}
// TC: O(n), SC: O(1)

---

LeetCode 136 – Single Number (All appear twice except one)

1. Brute Force

int singleNumber(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        int count = 0;
        for (int j = 0; j < nums.size(); j++)
            if (nums[i] == nums[j]) count++;
        if (count == 1) return nums[i];
    }
    return -1;
}
// TC: O(n²), SC: O(1)

---

2. Better – Hash Map

int singleNumber(vector<int>& nums) {
    unordered_map<int, int> freq;
    for (int n : nums) freq[n]++;

    for (auto [key, val] : freq)
        if (val == 1) return key;
    return -1;
}
// TC: O(n), SC: O(n)

---

3. Optimal – XOR

int singleNumber(vector<int>& nums) {
    int x = 0;
    for (int n : nums) x ^= n;
    return x;
}
// TC: O(n), SC: O(1)

XOR cancels out pairs: a ^ a = 0, and 0 ^ x = x

---

Longest Subarray with Sum K

1. Brute Force – 3 Loops

int maxLen(vector<int>& nums, int k) {
    int n = nums.size(), maxLen = 0;
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) {
            int sum = 0;
            for (int l = i; l <= j; l++) sum += nums[l];
            if (sum == k) maxLen = max(maxLen, j - i + 1);
        }
    return maxLen;
}
// TC: O(n³), SC: O(1)

---

2. Naive – 2 Loops

int maxLen(vector<int>& nums, int k) {
    int n = nums.size(), maxLen = 0;
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) maxLen = max(maxLen, j - i + 1);
        }
    }
    return maxLen;
// TC: O(n²), SC: O(1)

---

3. Better – Prefix Sum with Hashing

int maxLen(vector<int>& nums, int k) {
    unordered_map<int, int> mp;  // sum -> first index
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.size(); i++) {
        sum += nums[i];
        if (sum == k) maxLen = i + 1;
        if (mp.find(sum - k) != mp.end())
            maxLen = max(maxLen, i - mp[sum - k]);
        if (mp.find(sum) == mp.end()) mp[sum] = i;
    }
    return maxLen;
}
// TC: O(n), SC: O(n)

---

4. Two Pointer – Only Works for All Positive Elements

int maxLenPositives(vector<int>& nums, int k) {
    int i = 0, j = 0, sum = 0, maxLen = 0;
    int n = nums.size();
    while (j < n) {
        sum += nums[j];
        while (sum > k) {
            sum -= nums[i];
            i++;
        }
        if (sum == k)
            maxLen = max(maxLen, j - i + 1);
        j++;
    }
    return maxLen;
}
// TC: O(n), SC: O(1)

---

LeetCode 1 – Two Sum (Yes/No and Index Variant)

---

1. Brute Force – Check All Pairs

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

---

2. Better – Hash Map

bool twoSumExists(vector<int>& nums, int target) {
    unordered_set<int> s;
    for (int num : nums) {
        if (s.count(target - num)) return true;
        s.insert(num);
    }
    return false;
}
// TC: O(n), SC: O(n)

Index Variant:

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> mp;
    for (int i = 0; i < nums.size(); i++) {
        if (mp.count(target - nums[i]))
            return {mp[target - nums[i]], i};
        mp[nums[i]] = i;
    }
    return {-1, -1};
}
// TC: O(n), SC: O(n)

---

3. Two Pointer – Only Works When Array is Sorted

bool twoSumSorted(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int i = 0, j = nums.size() - 1;
    while (i < j) {
        int sum = nums[i] + nums[j];
        if (sum == target) return true;
        else if (sum < target) i++;
        else j--;
    }
    return false;
}
// TC: O(n log n) (due to sorting), SC: O(1)

---

Summary:

• Solved key LeetCode problems using brute force, hashing, two-pointer, and XOR tricks

• Revisited prefix sum with hashmap — useful for variable length subarrays

• Gained clarity on when two-pointer method applies (sorted arrays, positives only)

• Applied XOR to find unique elements optimally

• Practiced writing both yes/no and index-returning versions of Two Sum