'2025/03'에 해당되는 글 60건

Leetcode Problem:

• Alternating Groups II

Summary

• Find the number of alternating groups in a circle of red and blue tiles

Approach

• This solution uses a circular approach to find the alternating groups
• It first extends the colors array to make it circular, then it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups and increments the counter if a group is found.

Complexity

• O(N) where N is the number of tiles in the circle

Explanation

• The solution works by first extending the colors array to make it circular
• This is done by adding the first element to the end of the array
• Then, it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups by comparing the current color with the previous color
• If the colors are alternating, it increments the counter
• Finally, it returns the counter as the number of alternating groups

Solution Code:

class Solution {
public:
    int numberOfAlternatingGroups(vector& colors, int k) {
        int N = colors.size();
        for(int i = 0 ; i < N; i++){
            colors.push_back(colors[i]);
        }
        int cnt = 1;
        int cur = colors[0] ^ 1;
        int ans = 0;
        for(int i = 1; i < k; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            cur = colors[i] ^ 1;
        }
        if(cnt >= k){
            ans++;
        }
        for(int i = k; i < N + k - 1; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            if(cnt >= k){
                ans++;
            }
            cur = colors[i] ^ 1;
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Recolors to Get K Consecutive Black Blocks

Summary

• The problem is to find the minimum number of operations required to have at least k consecutive black blocks in a given string of blocks, where each block is either 'W' or 'B'.

Approach

• The solution uses a sliding window approach to track the number of consecutive black blocks
• It initializes a counter for the number of white blocks within the first k blocks and then slides the window to the right, updating the counter and the minimum number of operations required.

Complexity

• O(n), where n is the length of the string, as each character in the string is processed once.

Explanation

• The solution starts by initializing a counter for the number of white blocks within the first k blocks
• It then slides the window to the right, updating the counter and the minimum number of operations required
• If a white block is encountered within the window, the counter is decremented
• If a black block is encountered within the window, the counter is incremented
• The minimum number of operations required is updated at each step to reflect the current number of white blocks within the window.

Solution Code:

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int w = 0;
        for(int i = 0 ; i < k; i++){
            if(blocks[i] == 'W') w++;
        }
        int ans = w;
        for(int i = k; i < blocks.size(); i++){
            if(blocks[i - k] == 'W'){
                w--;
            }
            if(blocks[i] == 'W'){
                w++;
            }
            ans = min(ans, w);
        }
        return ans;
    }
};

Leetcode Problem:

• Closest Prime Numbers in Range

Summary

• Find two prime numbers within a given range with the minimum difference.

Approach

• Use the Sieve of Eratosthenes algorithm to generate prime numbers, then iterate through the range to find the pair with the minimum difference.

Complexity

• O(n log log n) due to the Sieve of Eratosthenes algorithm, where n is the upper bound of the range.

Explanation

• The Sieve of Eratosthenes algorithm is used to generate prime numbers up to the given upper bound
• Then, iterate through the range to find the pair of prime numbers with the minimum difference
• If no such pair exists, return [-1, -1].

Solution Code:

class Solution {
public:
    bool isPrime[1000001] = {false};
    vector closestPrimes(int left, int right) {
        for(int i = 2; i <= right; i++){
            isPrime[i] = true;
        }
        for(int i = 2; i*i <= right; i++){
            if(!isPrime[i]){
                continue;
            }
            for(int j = i *2; j <= right; j += i){
                isPrime[j] = false;
            }
        }
        
        vector ans;
        int beforePrime = 0;
        for(int i = left; i <= right; i++){
            if(!isPrime[i]){
                continue;    
            }
            if(ans.size() < 2){
                ans.push_back(i);
                beforePrime = i;
                continue;
            }
            else{
                if((ans[1] - ans[0]) > (i - beforePrime)){
                    ans[0] = beforePrime;
                    ans[1] = i;
                }
            }
            beforePrime = i;
        }
        if(ans.size() == 2) return ans;
        return {-1, -1};
    }
};

Leetcode Problem:

• Find Missing and Repeated Values

Summary

• Find the repeating and missing numbers in a 2D grid.

Approach

• Use a boolean array to track the presence of each number in the grid, then iterate through the array to find the repeating and missing numbers.

Complexity

• O(n^2) where n is the size of the grid

Explanation

• The solution first initializes a boolean array 'appear' of size n*n+1 to track the presence of each number
• It then iterates through the grid, setting the corresponding index in the 'appear' array to true for each number
• After that, it iterates through the 'appear' array and adds the index that is still false to the result vector
• This process finds the missing number
• The repeating number is found by iterating through the grid and adding the number to the result vector if it is already set to true in the 'appear' array.

Solution Code:

class Solution {
public:
    bool appear[2501] = {false,};
    vector findMissingAndRepeatedValues(vector>& grid) {
        int N = grid.size();
        vector ans;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(appear[grid[i][j]]){
                    ans.push_back(grid[i][j]);
                }
                appear[grid[i][j]] = true;
            }
        }
        for(int i = 1 ; i <= N*N; i++){
            if(!appear[i]){
                ans.push_back(i);
                return ans;
            }

        }
        return ans;
    }
};

Leetcode Problem:

• Count Total Number of Colored Cells

Summary

• Calculating the number of colored cells in a grid after n minutes

Approach

• The approach used is to calculate the number of colored cells in each minute and sum them up
• The number of colored cells in each minute is calculated as 2 times the number of odd-numbered cells that have not been colored yet
• The odd-numbered cells are calculated using the formula i * 2 + 1, where i is the current minute
• The initial number of odd-numbered cells is (i - 1) * 2 + 1, where i is 1
• The sum of colored cells in each minute is added to the total sum.

Complexity

• O(n)

Explanation

• The time complexity of the solution is O(n) because the solution iterates over each minute from 1 to n
• The space complexity is O(1) because the solution only uses a constant amount of space to store the variables i, odd, and sum.

Solution Code:

class Solution {
public:
    long long coloredCells(int n) {
        int i = 1;
        int odd = (i - 1) * 2 + 1;
        long long sum = 0;
        for( ; i < n; i++){
            sum += odd*2;
            odd = i * 2 + 1;
        }
        return sum + odd;
    }
};

Leetcode Problem:

• Shortest Common Supersequence

Summary

• Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.

Approach

• The approach used is dynamic programming
• We first create a 2D array dp where dp[i][j] represents the length of the shortest common supersequence of the first i characters of str1 and the first j characters of str2
• Then we construct the shortest common supersequence by tracing back the dp array.

Complexity

• O(n*m) where n and m are the lengths of str1 and str2 respectively.

Explanation

• The solution first initializes a 2D array dp of size (n+1) x (m+1) where n and m are the lengths of str1 and str2 respectively
• It then fills up the dp array using dynamic programming
• For each cell dp[i][j], if the current characters in str1 and str2 are the same, it increments the value by 1
• Otherwise, it takes the maximum value from the top and left cells
• After filling up the dp array, it constructs the shortest common supersequence by tracing back the dp array
• Finally, it appends any remaining characters from str1 and str2 to the supersequence.

Solution Code:

class Solution {
public:
    int dp[1001][1001];
    string shortestCommonSupersequence(string str1, string str2) {
        int cnt1 = 0;
        for(int i = 0 ; i < str1.size(); i++){
            for(int j = 0 ; j < str2.size(); j++){
                if(str1[i] == str2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        string s = "";
        int i = str1.size();
        int j = str2.size();
        while(i > 0 && j > 0){
            if(dp[i][j] == dp[i][j-1]){
                j--;
            } else if(dp[i][j] == dp[i-1][j]){
                i--;
            } else{
                s += str1[i-1];
                i--;
                j--;
            }
        }
        reverse(s.begin(), s.end());
        string res = "";
        int idx1 = 0;
        int idx2 = 0;
        for(int i = 0; i < s.size(); i++){
            while(str1[idx1] != s[i]){
                res += str1[idx1];
                idx1++;
            }
            while(str2[idx2] != s[i]){
                res += str2[idx2];
                idx2++;
            }
            res += s[i];
            idx1++;
            idx2++;
        }
        while(idx1 < str1.size()){
            res += str1[idx1++];
        }
        while(idx2 < str2.size()){
            res += str2[idx2++];
        }

        return res;
    }
};

Leetcode Problem:

• Make Lexicographically Smallest Array by Swapping Elements

Summary

• Given a 0-indexed array of positive integers and a positive integer limit, return the lexicographically smallest array that can be obtained by swapping any two indices if the absolute difference between the two elements is less than or equal to the limit.

Approach

• The solution uses a greedy approach to group the elements into subarrays based on their values
• It first sorts the array and then iterates through the sorted array to create subarrays
• Each subarray contains elements that are within the limit of each other
• Finally, it replaces each element in the original array with the smallest element in its corresponding subarray.

Complexity

• O(n log n) due to the sorting operation, where n is the number of elements in the array.

Solution Code:

class Solution {
public:
    vector lexicographicallySmallestArray(vector& nums, int limit) {
        vector> groups;
        unordered_map valToGrp;
        int numIdx = 0;
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            nums2.push_back(nums[i]);
        }
        sort(nums2.begin(), nums2.end());
        while(numIdx < nums2.size()){
            groups.push_back(vector ());
            long long minv = nums2[numIdx];
            long long maxv = nums2[numIdx];
            while(minv - limit <= nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                groups.back().push_back(nums2[numIdx]);
                valToGrp[nums2[numIdx]] = groups.size() - 1;
                numIdx++;
                if(numIdx >= nums2.size()) break;
                if(minv > nums2[numIdx] && nums2[numIdx] >= minv - limit){
                    minv = nums2[numIdx];
                }
                if(maxv < nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                    maxv = nums2[numIdx];
                }
            }
        }
        unordered_map groupIdx;
        for(int i = 0 ; i < nums.size(); i++){
            int idx = valToGrp[nums[i]];
            nums[i] = groups[idx][groupIdx[idx]];
            groupIdx[idx]++;
        }
        return nums;
    }
};

Leetcode Problem:

• Find Eventual Safe States

Summary

• Finding safe nodes in a directed graph

Approach

• Breadth-First Search (BFS) algorithm is used to detect safe nodes in the graph
• The graph is represented as an adjacency list, and a queue is used to keep track of nodes to visit
• Each node's out-degree is calculated and used to determine which nodes to add to the queue first.

Complexity

• O(N + E)

Explanation

• The solution starts by initializing variables to keep track of the graph, out-degrees, safe nodes, and an answer list
• It then iterates over the graph to calculate the out-degrees of each node and adds nodes with an out-degree of 0 to the queue
• The BFS algorithm is then used to traverse the graph, marking nodes as safe as they are visited
• Finally, the solution iterates over the graph again to add safe nodes to the answer list.

Solution Code:

class Solution {
public:
    vector eventualSafeNodes(vector>& G) {
        int N = G.size();
        vector> R(N);
        vector outdegree(N), safe(N), ans;
        queue q;
        for (int i = 0; i < N; ++i) {
            for (int v : G[i]) {
                R[v].push_back(i);
            }
            outdegree[i] = G[i].size();
            if (outdegree[i] == 0) q.push(i);
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            safe[u] = 1;
            for (int v : R[u]) {
                if (--outdegree[v] == 0) q.push(v);
            }
        }
        for (int i = 0; i < N; ++i) {
            if (safe[i]) ans.push_back(i);
        }
        return ans;
    }
};

Leetcode Problem:

• Count Servers that Communicate

Summary

• Counting servers that communicate with each other in a grid.

Approach

• This solution uses a breadth-first search (BFS) approach to traverse the grid and identify servers that can communicate with each other
• It uses a queue to keep track of nodes to visit and marks visited nodes to avoid revisiting them.

Complexity

• O(M*N + M*N) = O(2*M*N) due to the BFS traversal and marking of visited nodes.

Explanation

• The solution iterates over each cell in the grid
• If a cell contains a server (grid[i][j] == 1), it marks the cell as visited by setting it to 0 and adds it to a queue
• It then performs a BFS traversal, marking all connected servers as visited by setting them to 0
• The number of connected servers is stored in the variable 'cnt'
• If 'cnt' is greater than or equal to 2, it increments the 'ans' variable to count the servers that can communicate with each other.

Solution Code:

struct _node{
    int r;
    int c;
};
class Solution {
public:
    int countServers(vector>& grid) {
        int ans = 0;
        int M = grid.size();
        int N = grid[0].size();
        for(int i = 0 ; i < M; i++){
            for(int j = 0 ; j < N ;j++){
                queue<_node> que;
                if(grid[i][j]){
                    que.push({i, j});
                    grid[i][j] = 0;
                    int cnt = 1;
                    while(!que.empty()){
                        _node nod = que.front();
                        que.pop();
                        for(int k = 0 ; k < N; k++){
                            if(grid[nod.r][k]){
                                que.push({nod.r, k});
                                grid[nod.r][k] = 0;
                                cnt++;
                            }
                        }
                        for(int k = 0 ; k < M; k++){
                            if(grid[k][nod.c]){
                                que.push({k, nod.c});
                                grid[k][nod.c] = 0;
                                cnt++;
                            }
                        }
                    }
                    if(cnt >= 2) ans += cnt;
                }
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Map of Highest Peak

Summary

• Find an assignment of heights for a given map of land and water cells such that the maximum height in the matrix is maximized.

Approach

• Breadth-First Search (BFS) algorithm is used to traverse the water cells and assign heights to them
• The BFS algorithm starts from the water cells and explores all adjacent cells level by level, ensuring that the height difference between adjacent cells is at most 1.

Complexity

• O(MN)

Explanation

• The BFS algorithm works by maintaining a queue of nodes to visit, where each node represents a water cell
• For each water cell, we explore all its adjacent cells (up, down, left, right) and assign the next available height
• We continue this process until all water cells have been visited.

Solution Code:

struct _node{
    int r;
    int c;
};
class Solution {
public:
    queue<_node> que;
    vector> ans;
    vector> highestPeak(vector>& isWater) {
        int M = isWater.size();
        int N = isWater[0].size();
        for(int i = 0 ; i < M; i++){
            ans.push_back(vector());
            for(int j = 0 ; j < N; j++){
                ans[i].push_back(-1);
                if(isWater[i][j]){
                    que.push({i, j});
                    ans[i][j] = 0;
                }
            }
        }
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        while(!que.empty()){
            _node nod = que.front();
            que.pop();
            for(int i = 0; i < 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= M || nc < 0 || nc >= N || ans[nr][nc] != -1){
                    continue;
                }
                ans[nr][nc] = ans[nod.r][nod.c] + 1;
                que.push({nr, nc});
            }
        }
        return ans;
    }
};