Day 11 – Longest Consecutive Sequence, Matrix Set Zeros, Rotate Matrix

Today was focused on array and matrix problems involving space-time tradeoffs, hashing with sets, and in-place transformation using tricks like transpose and marking.

---

LeetCode 128 – Longest Consecutive Sequence

---

1. Brute Force – Sort and Count

int longestConsecutive(vector<int>& nums) {
    if (nums.empty()) return 0;
    sort(nums.begin(), nums.end());
    int longest = 1, count = 1;

    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] == nums[i - 1]) continue; // skip duplicates
        if (nums[i] == nums[i - 1] + 1) {
            count++;
        } else {
            longest = max(longest, count);
            count = 1;
        }
    }
    return max(longest, count);
}
// TC: O(n log n) (due to sorting)
// SC: O(1)

---

2. Better – Using Hash Map to Check Previous

int longestConsecutive(vector<int>& nums) {
    unordered_map<int, int> map;
    for (int x : nums) map[x] = 1;

    int maxStreak = 0;
    for (auto [num, _] : map) {
        if (map.find(num - 1) == map.end()) {
            int curr = num, count = 1;
            while (map.find(curr + 1) != map.end()) {
                count++;
                curr++;
            }
            maxStreak = max(maxStreak, count);
        }
    }
    return maxStreak;
}
// TC: O(n) average, O(n²) worst-case due to unbalanced hash lookups
// SC: O(n)

---

3. Optimal – Unordered Set

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> st(nums.begin(), nums.end());
    int longest = 0;

    for (int num : nums) {
        if (!st.count(num - 1)) {
            int curr = num;
            int length = 1;
            while (st.count(curr + 1)) {
                curr++;
                length++;
            }
            longest = max(longest, length);
        }
    }
    return longest;
}
// TC: O(n)
// SC: O(n)

---

LeetCode 73 – Set Matrix Zeroes

---

1. Brute Force – Mark With Placeholder

void setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (matrix[i][j] == 0)
                for (int k = 0; k < rows; k++) if (matrix[k][j] != 0) matrix[k][j] = -1;
                for (int k = 0; k < cols; k++) if (matrix[i][k] != 0) matrix[i][k] = -1;

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (matrix[i][j] == -1) matrix[i][j] = 0;
}
// TC: O((n * m)(n + m)) -> very high
// SC: O(1) but uses dirty marking (-1)

---

2. Better – Use Two Extra Arrays

void setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    vector<int> row(rows, 1), col(cols, 1);

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (matrix[i][j] == 0) row[i] = col[j] = 0;

    for (int i = 0; i < rows; i++)
        for (int j = 0; j < cols; j++)
            if (row[i] == 0 || col[j] == 0) matrix[i][j] = 0;
}
// TC: O(n * m)
// SC: O(n + m)

---

3. Optimal – Use First Row & Column as Markers

void setZeroes(vector<vector<int>>& matrix) {
    int rows = matrix.size(), cols = matrix[0].size();
    bool firstRow = false, firstCol = false;

    for (int i = 0; i < rows; i++) if (matrix[i][0] == 0) firstCol = true;
    for (int j = 0; j < cols; j++) if (matrix[0][j] == 0) firstRow = true;

    for (int i = 1; i < rows; i++)
        for (int j = 1; j < cols; j++)
            if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0;

    for (int i = 1; i < rows; i++)
        for (int j = 1; j < cols; j++)
            if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0;

    if (firstRow) for (int j = 0; j < cols; j++) matrix[0][j] = 0;
    if (firstCol) for (int i = 0; i < rows; i++) matrix[i][0] = 0;
}
// TC: O(n * m)
// SC: O(1)

---

LeetCode 48 – Rotate Image by 90 Degrees

---

1. Brute Force – Use New Matrix

vector<vector<int>> rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    vector<vector<int>> res(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            res[j][n - 1 - i] = matrix[i][j];
    return res;
// TC: O(n²), SC: O(n²)

---

2. Optimal – Transpose + Reverse Rows

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            swap(matrix[i][j], matrix[j][i]);

    for (int i = 0; i < n; i++)
        reverse(matrix[i].begin(), matrix[i].end());
}
// TC: O(n²), SC: O(1)

---

Rotate 180 Degrees – Reverse Rows + Reverse Columns

void rotate180(vector<vector<int>>& matrix) {
    reverse(matrix.begin(), matrix.end());
    for (int i = 0; i < matrix.size(); i++)
        reverse(matrix[i].begin(), matrix[i].end());
}
// TC: O(n²), SC: O(1)

---