Day 53: Competitive Programming Journal

Date: November 18, 2024
Hello Everyone,

Today marks Day 53 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Find the row with the maximum number of 1s in a binary matrix and Rearrange a string such that no two adjacent characters are the same.

1. Find the row with the maximum number of 1s in a binary matrix:
Problem:
Given a binary matrix, find the row that contains the maximum number of 1s.

Explanation:

• Use a two-pointer approach, where we start from the rightmost column and move leftwards.
• If we find a 1, we move left to narrow the possible rows.
• If we find a 0, we move downward, skipping those rows as they can’t contain 1s further to the left.

Implementation:

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

    int maxRow = -1, maxCount = 0;
    int j = cols - 1;

    for (int i = 0; i < rows; ++i) {
        while (j >= 0 && matrix[i][j] == 1) {
            --j; 
        }
        int countOnes = cols - j - 1;
        if (countOnes > maxCount) {
            maxCount = countOnes;
            maxRow = i;
        }
    }

    return maxRow;
}

2. Rearrange a string such that no two adjacent characters are the same:
Problem:
Given a string, rearrange its characters such that no two adjacent characters are the same.

Explanation:

• Count the frequency of each character.
• Use a max-heap to always place the most frequent character first, ensuring that no two adjacent characters are the same.
• If at any point, we can't place the most frequent character, it’s impossible to rearrange the string accordingly.

Implementation:

string rearrangeString(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    priority_queue<pair<int, char>> maxHeap;
    for (auto &entry : freq) {
        maxHeap.push({entry.second, entry.first});
    }

    string result;
    while (!maxHeap.empty()) {
        auto [count, ch] = maxHeap.top(); maxHeap.pop();
        if (result.empty() || result.back() != ch) {
            result += ch;
            if (--count > 0) {
                maxHeap.push({count, ch});
            }
        } else {
            if (maxHeap.empty()) {
                return "";
            }
            auto [nextCount, nextCh] = maxHeap.top(); maxHeap.pop();
            result += nextCh;
            if (--nextCount > 0) {
                maxHeap.push({nextCount, nextCh});
            }
            maxHeap.push({count, ch});
        }
    }

    return result;
}

Reflection:

Today’s problems tested my understanding of binary search and greedy algorithms. The first problem, finding the row with the maximum number of 1s, was a good exercise in searching and condition checking, while the second problem on rearranging a string required understanding of frequency counts and using a max-heap to ensure no two adjacent characters are the same. Both problems were insightful and helped strengthen my problem-solving skills.

Stay tuned for more updates, and happy coding!