DILI #14: I lied....

Apprently the week after holiday is quite a busy week, for me at least. So, I couldn't keep my promise on the note-taking app as I couldn't really find time.... But as a compensation, let's do some LeetCodes!!!!

Problem 1: Longest Repeating Character Replacement

Solving this problem was not hard (as the method to this was spoiled on NeetCode). Using the sliding windows technique, I couold solve this quite neatly. Also, because it only required me to give the length of the longest substring with repeating letters after the replacement, I didn't need actually modify the string; I only need to keep track of the certain variables like: number of the most repeated digit in the window(maxCount) and the two positions of the window(left and right).

And when this condition is satisfied: right - left + 1 - maxCount = k, that is a candidate for our final result. Finally, I just need to see if that candidate is longer than the last repeatedy until the window ends.

Soure Code:

class Solution {
public:
    int characterReplacement(string s, int k) {
        vector<int> count(26);
        int maxCount = 0;

        int l = 0;
        int r = 0;
        int res = 0;

        while(r < s.size()){
            count[s[r] - 'A']++;
            maxCount = max(maxCount, count[s[r] - 'A']);
            if(r - l + 1 - maxCount > k){
                count[s[l] - 'A']--;
                l++;
            }
            res = max(res, r - l + 1);
            r++;
        }
        return res;
    }
};

Problem 2: Pacific Atlantic Water Flow

This was another fun problem. But different from last time, the only help I had was it was a problem using Graph. Thanks NeetCode. Anyways. This problem give you a 2-D grid with each cells are mountains of an island and the value is the height.

Given that it's gonna rain, and water flow from mountains with higher heights to lower or equal heights, which mountain or cell has water that can make it to both the Pacific Ocean and the Atlantic Ocean. Look at the image below.

So, working from a cell and see if it's gonna reach both ocean is not gonna get you anywhere. Believe me, I tried. It's gonna take an excessive amount of time. So, let works backwards and start from the oceans. And the water logic will just literally flow backwards as in our waterway will flow from low-height mountains to high-height mountains.

From the image, the North and West is touching Pacific, while South and East is touching Atlantic. So we just need to navigate paths from those cells using DFS and keep track of what cells are visited. Which ever cells are visited by both the "Pacific path" and the "Atlantic path" is the cell we are looking far.

Source Code:

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();
        vector<vector<int>> res;

        vector<vector<bool>> pac(m, vector<bool> (n));
        vector<vector<bool>> atl(m, vector<bool> (n));

        for(int i = 0; i < m; i++){
            dfs(heights,pac,i,0,m,n);
            dfs(heights,atl,i,n-1,m,n);
        }
        for(int j = 0; j < n; j++){
            dfs(heights,pac,0,j,m,n);
            dfs(heights,atl,m-1,j,m,n);
        }
        for(int i = 0; i < m;i++){
            for(int j = 0; j < n;j++){
                if(pac[i][j] && atl[i][j]){
                    res.push_back({i,j});
                }
            }
        }
        return res;
    }
private:
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int i, int j, int m, int n){
        visited[i][j] = true;
        if(i > 0 && !visited[i-1][j] && heights[i-1][j] >= heights[i][j])
            dfs(heights, visited, i-1,j,m,n);
        if(i < m-1 && !visited[i+1][j] && heights[i+1][j] >= heights[i][j])
            dfs(heights, visited, i+1,j,m,n);
        if(j > 0 && !visited[i][j-1] && heights[i][j-1] >= heights[i][j])
            dfs(heights, visited, i,j-1,m,n);
        if(j < n-1 && !visited[i][j+1] && heights[i][j+1] >= heights[i][j])
            dfs(heights, visited, i,j+1,m,n);
    }
};

Are 2 problems all I've done? No, I've done at least like 3... But those 2 are most fascinating to me of how different thought processes they needed. One is to find when to move the window and how to make the best of each evaluation and one is working backwards.

With that, I shall conclude today's week blog. As always, all advices are welcomed. Cya next week! Peace!

REFERENCES:
LeetCode... that's it!