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

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

Leetcode Problem:

• Minimize XOR

Summary

• Find the positive integer x such that x has the same number of set bits as num2 and the value x XOR num1 is minimal.

Approach

• The solution uses a two-step approach
• First, it counts the number of set bits in num1 and num2 using a helper function
• Then, it adjusts num1 to have the same number of set bits as num2 by shifting bits to the right and/or left until the difference is zero
• The final result is the adjusted num1.

Complexity

• O(log max(num1, num2))

Explanation

• The time complexity is O(log max(num1, num2)) because in the worst case, we need to shift bits up to 32 places to the right (for a 32-bit integer)
• The space complexity is O(1) because we only use a constant amount of space to store the result and the temporary variables.

Solution Code:

class Solution {
public:
    int bitCount(int n){
        int cnt = 0;
        while(n){
            cnt++;
            n &= n-1;
        }
        return cnt;
    }
    int minimizeXor(int num1, int num2) {
        int bit1 = bitCount(num1);
        int bit2 = bitCount(num2);
        int x = num1;
        int diff = bit2 - bit1;
        if(diff == 0) return num1;
        else if(diff > 0){
            long long offset = 1;
            while(diff){
                if((offset & x) == 0){
                    diff--;
                }
                x |= offset;
                offset <<= 1;
            }
        } else{
            diff = -diff;
            while(diff--){
                x &= x - 1;
            }
        }
        return x;
    }
};

Leetcode Problem:

• Find the Prefix Common Array of Two Arrays

Summary

• Find the prefix common array of two integer permutations

Approach

• The approach is to use bitwise operations to count the common elements in both permutations
• The idea is to treat each permutation as a subset of numbers from 1 to n, where n is the length of the permutations
• We use a binary number to represent each subset, where each bit corresponds to a number from 1 to n
• We then use bitwise operations to count the common elements in both subsets.

Complexity

• O(n log n) due to the bitCount function, where n is the length of the permutations

Explanation

• The solution works by iterating over each element in both permutations and updating the subset numbers for each permutation
• For each element, we use bitwise operations to count the common elements in both subsets
• The bitCount function is used to count the number of bits set in a binary number, which represents the count of common elements
• The result is a vector of integers representing the prefix common array.

Solution Code:

class Solution {
public:
    int bitCount(unsigned long long num){
        int cnt = 0;
        while(num){
            cnt++;
            num &= num-1;
        }
        return cnt;
    }
    vector findThePrefixCommonArray(vector& A, vector& B) {
        unsigned long long subsetA = 0;
        unsigned long long subsetB = 0;
        vector ans;
        for(int i = 0 ; i < A.size(); i++){
            subsetA |= 1ULL << A[i];
            subsetB |= 1ULL << B[i];
            ans.push_back(bitCount(subsetA & subsetB));
        }
        return  ans;
    }
};

Leetcode Problem:

• Construct K Palindrome Strings

Summary

• Given a string s and an integer k, return true if all characters in s can be used to construct non-empty k palindrome strings or false otherwise.

Approach

• This solution uses a frequency count array to store the frequency of each character in the string
• It then checks the number of characters with odd frequencies, which are the characters that can only appear in one palindrome
• If the number of such characters is less than or equal to k, it means that all characters can be used to construct k palindrome strings.

Complexity

• O(n) where n is the length of the string, because we are iterating over the string twice (to count frequencies and to check odd frequencies).

Explanation

• We start by checking if the length of the string is less than k
• If it is, we return false because we cannot construct k palindrome strings
• We then create a frequency count array cnt of size 128 to store the frequency of each character in the string
• We iterate over the string and increment the count of each character in the array
• We then iterate over the characters 'a' to 'z' and count the number of characters with odd frequencies
• If this number is less than or equal to k, we return true because we can construct k palindrome strings
• Otherwise, we return false.

Solution Code:

class Solution {
public:
    bool canConstruct(string s, int k) {
        if(s.size() < k) return false;
        int cnt[128];
        for(char c: s){
            cnt[c]++;
        }
        int odd = 0;
        for(int i = 'a'; i <= 'z'; i++){
            odd += cnt[i] & 1;
        }
        return odd <= k;
    }
};