'알고리즘'에 해당되는 글 277건

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;
    }
};

Leetcode Problem:

• Grid Game

Summary

• The problem is to find the minimum number of points collected by the second robot in a game where two robots play on a 2xN grid.

Approach

• The solution uses a two-pointer approach, keeping track of the sum of points in the first and second rows
• It iterates over the grid, updating the sums and finding the minimum maximum value at each step.

Complexity

• O(n)

Explanation

• The solution works by maintaining two variables, `firstRowSum` and `secondRowSum`, which represent the sum of points in the first and second rows, respectively
• Initially, `firstRowSum` is set to the sum of the first row, and `secondRowSum` is set to 0
• Then, it iterates over the grid, updating `firstRowSum` by subtracting the current element and `secondRowSum` by adding the current element
• At each step, it finds the minimum maximum value between `firstRowSum` and `secondRowSum` and updates `minimumSum` accordingly
• Finally, it returns `minimumSum` as the minimum number of points collected by the second robot.

Solution Code:

class Solution {
public:
    long long gridGame(vector>& grid) {
        long long firstRowSum = accumulate(begin(grid[0]), end(grid[0]), 0LL),
                  secondRowSum = 0;
        long long minimumSum = LONG_LONG_MAX;
        for (int turnIndex = 0; turnIndex < grid[0].size(); ++turnIndex) {
            firstRowSum -= grid[0][turnIndex];
            // Find the minimum maximum value out of firstRowSum and
            // secondRowSum.
            minimumSum = min(minimumSum, max(firstRowSum, secondRowSum));
            secondRowSum += grid[1][turnIndex];
        }
        return minimumSum;
    }
};

Leetcode Problem:

• First Completely Painted Row or Column

Summary

• Find the smallest index at which either a row or a column will be completely painted in the matrix.

Approach

• The approach used is to first map the array elements to their corresponding indices in the matrix
• Then, for each row and column, find the maximum index that has been painted so far
• The smallest of these maximum indices is the smallest index at which either a row or a column will be completely painted.

Complexity

• O(m*n) where m is the number of rows and n is the number of columns in the matrix.

Explanation

• The solution code first creates a mapping of array elements to their corresponding indices in the matrix
• Then, for each row and column, it finds the maximum index that has been painted so far by iterating over the elements of the row or column
• The smallest of these maximum indices is the smallest index at which either a row or a column will be completely painted
• This approach ensures that all rows and columns are considered, and the smallest index is found.

Solution Code:

class Solution {
public:
    int vtoi[100001];
    int firstCompleteIndex(vector& arr, vector>& mat) {
        for(int i = 0 ; i < arr.size(); i++){
            vtoi[arr[i]] = i;
        }
        int m = mat.size();
        int n = mat[0].size();
        for(int i = 0 ; i < m ; i++){
            for(int j = 0 ; j < n ; j++){
                mat[i][j] = vtoi[mat[i][j]];
            }
        }
        int ans = 100000;
        for(int i = 0 ; i < m; i++){
            int maxIdx = -1;
            for(int j = 0 ; j < n ; j++){
                maxIdx = max(maxIdx, mat[i][j]);
            }
            ans = min(ans, maxIdx);
        }
        for(int i = 0; i < n; i++){
            int maxIdx = -1;
            for(int j = 0; j < m; j++){
                maxIdx = max(maxIdx, mat[j][i]);
            }
            ans = min(ans, maxIdx);
        }
        return ans;
    }
};

Leetcode Problem:

• Trapping Rain Water II

Summary

• This solution calculates the volume of water that can be trapped in a given 2D elevation map after raining.

Approach

• The approach used in this solution is to simulate the process of rainwater trapping using a priority queue to process boundary cells in increasing height order
• It uses a breadth-first search (BFS) approach to explore neighboring cells and calculate the trapped water volume.

Complexity

• O(m*n*log(m*n))

Explanation

• The solution starts by initializing a priority queue with boundary cells and marking them as visited
• Then, it enters a loop where it pops the cell with the smallest height from the boundary, explores its neighboring cells, and calculates the trapped water volume
• The solution uses a helper function to check if a cell is valid and another helper function to compare cells based on height
• The time complexity is O(m*n*log(m*n)) due to the priority queue operations and the BFS exploration.

Solution Code:

class Solution {
public:
    int trapRainWater(vector>& heightMap) {
        // Direction arrays
        int dRow[4] = {0, 0, -1, 1};
        int dCol[4] = {-1, 1, 0, 0};

        int numOfRows = heightMap.size();
        int numOfCols = heightMap[0].size();

        vector> visited(numOfRows, vector(numOfCols, false));

        // Priority queue (min-heap) to process boundary cells in increasing
        // height order
        priority_queue boundary;

        // Add the first and last column cells to the boundary and mark them as
        // visited
        for (int i = 0; i < numOfRows; i++) {
            boundary.push(Cell(heightMap[i][0], i, 0));
            boundary.push(Cell(heightMap[i][numOfCols - 1], i, numOfCols - 1));
            // Mark left and right boundary cells as visited
            visited[i][0] = visited[i][numOfCols - 1] = true;
        }

        // Add the first and last row cells to the boundary and mark them as
        // visited
        for (int i = 0; i < numOfCols; i++) {
            boundary.push(Cell(heightMap[0][i], 0, i));
            boundary.push(Cell(heightMap[numOfRows - 1][i], numOfRows - 1, i));
            // Mark top and bottom boundary cells as visited
            visited[0][i] = visited[numOfRows - 1][i] = true;
        }

        int totalWaterVolume = 0;

        while (!boundary.empty()) {
            // Pop the cell with the smallest height from the boundary
            Cell currentCell = boundary.top();
            boundary.pop();

            int currentRow = currentCell.row;
            int currentCol = currentCell.col;
            int minBoundaryHeight = currentCell.height;

            // Explore all 4 neighboring cells
            for (int direction = 0; direction < 4; direction++) {
                int neighborRow = currentRow + dRow[direction];
                int neighborCol = currentCol + dCol[direction];

                // Check if the neighbor is within the grid bounds and not yet
                // visited
                if (isValidCell(neighborRow, neighborCol, numOfRows,
                                numOfCols) &&
                    !visited[neighborRow][neighborCol]) {
                    int neighborHeight = heightMap[neighborRow][neighborCol];

                    // If the neighbor's height is less than the current
                    // boundary height, water can be trapped
                    if (neighborHeight < minBoundaryHeight) {
                        totalWaterVolume += minBoundaryHeight - neighborHeight;
                    }

                    // Push the neighbor into the boundary with updated height
                    // (to prevent water leakage)
                    boundary.push(Cell(max(neighborHeight, minBoundaryHeight),
                                       neighborRow, neighborCol));
                    visited[neighborRow][neighborCol] = true;
                }
            }
        }

        return totalWaterVolume;
    }

private:
    // Struct to store the height and coordinates of a cell in the grid
    class Cell {
    public:
        int height;
        int row;
        int col;

        // Constructor to initialize a cell
        Cell(int height, int row, int col)
            : height(height), row(row), col(col) {}

        // Overload the comparison operator to make the priority queue a
        // min-heap based on height
        bool operator<(const Cell& other) const {
            // Reverse comparison to simulate a min-heap
            return height >= other.height;
        }
    };

    // Helper function to check if a cell is valid (within grid bounds)
    bool isValidCell(int row, int col, int numOfRows, int numOfCols) {
        return row >= 0 && col >= 0 && row < numOfRows && col < numOfCols;
    }
};

Leetcode Problem:

• Minimum Cost to Make at Least One Valid Path in a Grid

Summary

• Given an m x n grid, each cell with a sign pointing to the next cell to visit
• The goal is to find the minimum cost to make the grid have at least one valid path from the top-left to the bottom-right cell.

Approach

• A priority queue is used to store the nodes to be visited
• The priority queue is implemented using a binary heap data structure
• The cost of each node is used as the priority
• The algorithm starts by initializing the cost of all cells to a large value and then iteratively visits the node with the lowest cost, updating the cost of its neighbors and adding them to the priority queue if necessary.

Complexity

• O(MN log MN), where M and N are the dimensions of the grid.

Solution Code:

struct _node{
    int r;
    int c;
    int cost;
};

bool minHeap(_node& a, _node& b){
    return a.cost > b. cost;
}

struct _heap{
    _node arr[40001];
    int size;
    bool (*cmp)(_node& a, _node& b);
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx/2], arr[idx])){
            _node tmp = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = tmp;
            idx /= 2;
        }
    }
    _node pop(){
        _node ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j >= size) break;
            if(j+1 < size && cmp(arr[j], arr[j+1])){
                j++;
            }
            if(cmp(arr[i], arr[j])){
                _node tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
    _heap que;
    int cost[100][100];
public:
    int minCost(vector>& grid) {
        int M = grid.size();
        int N = grid[0].size();
        for(int i = 0 ; i < M; i++){
            for(int j = 0 ; j < N; j++){
                cost[i][j] = 200;
            }
        }
        que.cmp = minHeap;
        que.push({0, 0, 0});
        cost[0][0] = 0;
        int dy[] = {0, 0, 0, 1, -1};
        int dx[] = {0, 1, -1, 0, 0};
        while(!que.empty()){
            _node nod = que.pop();
            if(nod.r == (M - 1) && nod.c == (N - 1)){
                return nod.cost;
            }
            for(int i = 1; i <= 4; i++){
                int nr = nod.r + dy[i];
                int nc = nod.c + dx[i];
                if(nr < 0 || nr >= M || nc < 0 || nc >= N){
                    continue;
                }
                int c = nod.cost;
                if(i != grid[nod.r][nod.c]){
                    c++;
                }
                if(cost[nr][nc] <= c) continue;
                cost[nr][nc] = c;
                que.push({nr, nc, c});
            }
        }
        return -1;
    }
};

Leetcode Problem:

• Neighboring Bitwise XOR

Summary

• This problem is about determining whether a valid binary array can be formed from a given derived array.

Approach

• The approach used in the solution is to create a new array called original and fill it with the XOR of adjacent values in the derived array
• Then, check if the first and last elements of the original array are equal, which means a valid binary array can be formed from the derived array.

Complexity

• O(n) where n is the length of the derived array

Explanation

• The solution starts by pushing the first element of the derived array to the original array
• Then, it iterates over the derived array and pushes the XOR of the current element and the last element of the original array to the original array
• Finally, it checks if the first and last elements of the original array are equal, which means a valid binary array can be formed from the derived array.

Solution Code:

class Solution {
public:
    vector original;
    bool doesValidArrayExist(vector& derived) {
        int N = derived.size();
        derived.push_back(derived[0]);
        original.push_back(derived[0]);
        for(int i = 0 ; i < N; i++){
            original.push_back(derived[i] ^ original[i]);
        }
        return original[0] == original[N];
    }
};

Leetcode Problem:

• Check if Number is a Sum of Powers of Three

Summary

• Check if a number can be represented as the sum of distinct powers of three.

Approach

• The approach used is to generate a set of powers of three up to the given number, and then try to subtract each power from the number
• If the number can be reduced to zero, it means that the number can be represented as the sum of distinct powers of three.

Complexity

• O(log n) because the number of powers of three is logarithmic to the given number n.

Explanation

• The code generates a set of powers of three up to the given number n
• It then tries to subtract each power from n
• If n can be reduced to zero, it means that n can be represented as the sum of distinct powers of three
• The time complexity is O(log n) because the number of powers of three is logarithmic to n
• This is because each power of three is 3 times the previous one, so the number of powers grows logarithmically with n.

Solution Code:

class Solution {
public:
    
    bool checkPowersOfThree(int n) {
        vector powerSet;
        int pow = 1;
        while(pow <= n){
            powerSet.push_back(pow);
            pow *= 3;
        }
        for(int i = powerSet.size() - 1; i >= 0; i--){
            if(n > powerSet[i]){
                n -= powerSet[i];
            } else if (n < powerSet[i]){
                continue;   
            } else{
                return true;
            }
        }
        return false;
    }
};

Leetcode Problem:

• Bitwise XOR of All Pairings

Summary

• Given two arrays, nums1 and nums2, return the bitwise XOR of all pairings of integers between nums1 and nums2.

Approach

• The solution uses two nested loops to iterate over the elements of nums1 and nums2
• For each element in nums1, it XORs the element with all elements in nums2
• Similarly, for each element in nums2, it XORs the element with all elements in nums1
• The XOR operation is used to combine the pairings, and the result is returned.

Complexity

• O(n*m) where n is the size of nums1 and m is the size of nums2

Explanation

• The solution iterates over the elements of nums1 and nums2 using two nested loops
• For each element in nums1, it XORs the element with all elements in nums2 using a single loop
• Similarly, for each element in nums2, it XORs the element with all elements in nums1 using another single loop
• The XOR operation is associative and commutative, so the order of the loops does not matter
• The result of the XOR operation is the bitwise XOR of all pairings of integers between nums1 and nums2.

Solution Code:

class Solution {
public:
    int xorAllNums(vector& nums1, vector& nums2) {
        int n1 = (nums1.size()-1) % 2;
        int n2 = (nums2.size()-1) % 2;
        int ans = 0;
        for(int i = 0 ; i < nums1.size(); i++){
            for(int j = 0 ; j <= n2; j++){
                ans ^= nums1[i];
            }
        }
        for(int i = 0 ; i < nums2.size(); i++){
            for(int j = 0; j <= n1; j++){
                ans ^= nums2[i];
            }
        }
        return ans;
    }
};