'LeetCode'에 해당되는 글 281건

Leetcode Problem:

• Check if Grid can be Cut into Sections

Summary

• Problem: Determine if it is possible to make two horizontal or two vertical cuts on an n x n grid such that each cut contains at least one rectangle and every rectangle belongs to exactly one section.

Approach

• The solution uses a two-dimensional approach, trying both horizontal and vertical cuts
• It sorts the rectangles by their starting coordinate in the given dimension and tracks the furthest ending coordinate seen so far
• It then checks for gaps between rectangles where a cut can be made
• The solution returns true if at least two gaps are found, indicating that valid cuts can be made.

Complexity

• O(n log n) due to sorting the rectangles, where n is the number of rectangles.

Explanation

• The solution first tries both horizontal and vertical cuts using the `checkCuts` function, which takes a 2D array of rectangles and a dimension (0 for horizontal cuts and 1 for vertical cuts) as input
• The `checkCuts` function sorts the rectangles by their starting coordinate in the given dimension and tracks the furthest ending coordinate seen so far
• It then checks for gaps between rectangles where a cut can be made
• The function returns true if at least two gaps are found, indicating that valid cuts can be made.

Solution Code:

class Solution {
public:
    bool checkValidCuts(int n, vector>& rectangles) {
        // Try both horizontal and vertical cuts
        return checkCuts(rectangles, 0) || checkCuts(rectangles, 1);
    }

private:
    // Check if valid cuts can be made in a specific dimension
    bool checkCuts(vector>& rectangles, int dim) {
        int gapCount = 0;

        // Sort rectangles by their starting coordinate in the given dimension
        sort(rectangles.begin(), rectangles.end(),
             [dim](const vector& a, const vector& b) {
                 return a[dim] < b[dim];
             });

        // Track the furthest ending coordinate seen so far
        int furthestEnd = rectangles[0][dim + 2];

        for (size_t i = 1; i < rectangles.size(); i++) {
            vector& rect = rectangles[i];

            // If current rectangle starts after the furthest end we've seen,
            // we found a gap where a cut can be made
            if (furthestEnd <= rect[dim]) {
                gapCount++;
            }

            // Update the furthest ending coordinate
            furthestEnd = max(furthestEnd, rect[dim + 2]);
        }

        // We need at least 2 gaps to create 3 sections
        return gapCount >= 2;
    }
};

Leetcode Problem:

• Count Days Without Meetings

Summary

• Given a positive integer days representing the total number of days an employee is available for work, and a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive), return the count of days when the employee is available for work but no meetings are scheduled.

Approach

• The approach used is to first sort the meetings array, then initialize two pointers l and r to the start and end of the first meeting respectively
• Then, iterate over the rest of the meetings and update the end of the last meeting that ends earliest
• Finally, add the available days before the first meeting and after the last meeting to the answer.

Complexity

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

Solution Code:

class Solution {
public:
    int countDays(int days, vector>& meetings) {
        sort(meetings.begin(), meetings.end());
        int l = meetings[0][0];
        int r = meetings[0][1];
        int ans = 0;
        ans += l - 1;
        for(int i = 1 ; i < meetings.size(); i++){
            int ll = meetings[i][0];
            int rr = meetings[i][1];
            cout << ll << " " << rr << endl;
            if(r < ll){
                ans += ll - r - 1;
            }
            r = max(r, rr);
        }
        ans += days - r;
        return ans;
    }
};

Leetcode Problem:

• Count the Number of Complete Components

Summary

• This is a problem about finding the number of complete connected components in a graph.

Approach

• The approach used in the solution code is to use a disjoint set data structure to keep track of the connected components in the graph
• The code first initializes the disjoint set data structure and then iterates over the edges in the graph
• For each edge, it checks if the two vertices are in the same connected component
• If they are not, it merges the two components by attaching the root of one component to the root of the other component
• The code also keeps track of the number of edges in each component
• Finally, it checks each component to see if it is complete by checking if the number of edges in the component is equal to the number of ways to choose two vertices from the component (i.e., n*(n-1)/2)
• If a component is not complete, it is removed from the set of components
• The final answer is the number of complete components remaining in the set.

Complexity

• O(n*m*log(n)) where n is the number of vertices and m is the number of edges in the graph.

Explanation

• The code first initializes the disjoint set data structure and the edge count array
• It then iterates over the edges in the graph and checks if the two vertices are in the same connected component
• If they are not, it merges the two components by attaching the root of one component to the root of the other component
• The code also keeps track of the number of edges in each component
• Finally, it checks each component to see if it is complete by checking if the number of edges in the component is equal to the number of ways to choose two vertices from the component (i.e., n*(n-1)/2)
• If a component is not complete, it is removed from the set of components
• The final answer is the number of complete components remaining in the set.

Solution Code:

class Solution {
public:
    int uf[51];
    int edgeCnt[51] = {0};
    int groupCnt[51] = {0};
    int disjointSet(int x){
        if (x == uf[x]) return x;
        return uf[x] = disjointSet(uf[x]);
    }
    int countCompleteComponents(int n, vector>& edges) {
        if (n == 1) return 1;
        set ans;
        for(int i = 0 ; i < n; i++){
            uf[i] = i;
            groupCnt[i] = 1;
        }
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(disjointSet(a) != disjointSet(b)){
                groupCnt[disjointSet(b)] += groupCnt[disjointSet(a)];
                groupCnt[disjointSet(a)] = 0;
                edgeCnt[disjointSet(b)] += edgeCnt[disjointSet(a)];
                edgeCnt[disjointSet(b)] += 1;
                edgeCnt[disjointSet(a)] = 0;
                uf[disjointSet(a)] = disjointSet(b);
            }else{
                edgeCnt[disjointSet(b)] += 1;
            }
        }
        for(int i = 0 ; i < n; i++){
            if(ans.find(disjointSet(i)) == ans.end()){
                ans.insert(disjointSet(i));
            }
        }
        cout << "answer size: " << ans.size() << endl;
        vector removeList;
        for(auto idx : ans){
            int n = groupCnt[disjointSet(idx)];
            int e = edgeCnt[disjointSet(idx)];
            cout << n << " " << e << endl;
            if((n*(n-1)/2) != e){
                removeList.push_back(idx);
            }
        }
        for(int i = 0 ; i < removeList.size(); i++){
            ans.erase(removeList[i]);
        }
        return ans.size();
    }
};

Leetcode Problem:

• Find All Possible Recipes from Given Supplies

Summary

• Find all the recipes that can be created with the given ingredients and supplies.

Approach

• Breadth-First Search (BFS) algorithm is used to traverse the graph of recipes and ingredients
• The algorithm starts by initializing a queue with all the recipes and a set of available supplies
• Then, it iteratively pops a recipe from the queue, checks if all its ingredients are available, and if so, adds it to the set of available supplies and the result list
• If not, it pushes the recipe back into the queue to be processed later.

Complexity

• O(N + M) where N is the number of recipes and M is the total number of ingredients

Explanation

• The algorithm uses a queue to keep track of the recipes to be processed and a set to keep track of the available supplies
• It iterates over the recipes and checks if all their ingredients are available
• If they are, it adds the recipe to the set of available supplies and the result list
• If not, it pushes the recipe back into the queue to be processed later
• This process continues until all recipes have been processed or the queue is empty.

Solution Code:

class Solution {
public:
    queue que;
    set supply;
    vector findAllRecipes(vector& recipes, vector>& ingredients, vector& supplies) {
        int N = recipes.size();
        
        for(int i = 0 ; i < N; i++){
            que.push(i);
        }
        for(int i = 0 ; i < supplies.size(); i++){
            supply.insert(supplies[i]);
        }
        vector ans;
        int cnt = 0;
        while(!que.empty() && cnt < N){
            int idx = que.front();
            que.pop();
            bool success = true;
            for(int i = 0; i < ingredients[idx].size(); i++){
                if(supply.find(ingredients[idx][i]) == supply.end()){
                    success = false;
                    break;
                }
            }
            if(success){
                supply.insert(recipes[idx]);
                ans.push_back(recipes[idx]);
                cnt = -1;
                N--;
            } else{
                que.push(idx);
            }
            cnt++;
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Cost Walk in Weighted Graph

Summary

• Find the minimum cost of a walk between two nodes in an undirected weighted graph.

Approach

• Disjoint Set Union (DSU) algorithm is used to find the minimum cost of a walk between two nodes in an undirected weighted graph
• The DSU algorithm is used to find the set that each node belongs to and the minimum cost of the walk is calculated by performing a bitwise AND operation on the weights of the edges in the same set.

Complexity

• O(n + m log n), where n is the number of nodes and m is the number of edges.

Explanation

• The solution code first initializes the DSU array and the groupWeight array
• Then it iterates over the edges and updates the groupWeight array by performing a bitwise AND operation on the weights of the edges in the same set
• Finally, it iterates over the queries and calculates the minimum cost of the walk for each query by performing a bitwise AND operation on the weights of the edges in the same set.

Solution Code:

class Solution {
public:
    int uf[100001];
    int groupWeight[100001];
    int disjointSet(int x){
        if(x == uf[x]) return x;
        return uf[x] = disjointSet(uf[x]);
    }
    vector minimumCost(int n, vector>& edges, vector>& query) {
        for(int i = 0 ; i < n ;i++){
            uf[i] = i;
            groupWeight[i] = 0x0FFFFFFF;
        }
        for(int i = 0; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            int w = edges[i][2];
            int ww = groupWeight[disjointSet(a)] & groupWeight[disjointSet(b)] & w;
            uf[disjointSet(a)] = disjointSet(b);
            groupWeight[disjointSet(a)] = ww;
        }
        vector ans;
        for(int i = 0 ; i < query.size(); i++){
            int s = query[i][0];
            int e = query[i][1];
            if(disjointSet(s) == disjointSet(e)){
                ans.push_back(groupWeight[disjointSet(s)]);
            }else{
                ans.push_back(-1);
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Operations to Make Binary Array Elements Equal to One I

Summary

• Given a binary array, find the minimum number of operations to make all elements equal to 1 by flipping 3 consecutive elements at a time.

Approach

• The approach is to iterate through the array and flip 3 consecutive elements at a time until no more flips are possible
• If a 3 consecutive elements cannot be found, return -1.

Complexity

• O(n), where n is the number of elements in the array

Explanation

• The solution iterates through the array and checks if the current element and the next two elements are 0
• If they are, it flips them and increments the answer
• This process continues until no more flips are possible
• If at any point a 3 consecutive elements cannot be found, the function returns -1.

Solution Code:

class Solution {
public:
    int minOperations(vector& nums) {
        int ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] == 0){
                for(int j = i; j < i + 3; j++){
                    if(j >= nums.size()) return -1;
                    nums[j] ^= 1;
                }
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Split Linked List in Parts

Summary

• Given a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

Approach

• The approach used is to first store the values of the linked list in a vector
• Then, for each part, create a new linked list with the required number of nodes
• The remaining nodes are then added to the next part.

Complexity

• O(n), where n is the number of nodes in the linked list

Explanation

• The solution starts by storing the values of the linked list in a vector
• This is done to easily access the values of the linked list
• Then, for each part, a new linked list is created with the required number of nodes
• The remaining nodes are then added to the next part
• This process is repeated for each part, until all parts have been created
• The time complexity of the solution is O(n), where n is the number of nodes in the linked list, because each node is visited once
• The space complexity is also O(n), because in the worst case, all nodes are stored in the vector.

Solution Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    vector splitListToParts(ListNode* head, int k) {
        ListNode* ptr = head;
        vector arr;
        vector ans;
        while(ptr){
            arr.push_back(ptr->val);
            ptr = ptr->next;
        }
        int N = arr.size();
        int more = arr.size() % k;
        int arrIdx = 0;
        for(int i = 0 ; i < k ; i++){
            ListNode* tmp = nullptr;
            ListNode* ptr;
            for(int j = 0; j < N / k; j++){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
            }
            if (more){
                if (tmp == nullptr) {
                    tmp = new ListNode(arr[arrIdx++]);
                    ptr = tmp;
                } else{
                    ptr->next = new ListNode(arr[arrIdx++]);
                    ptr = ptr->next;
                }
                more--;
            }
            ans.push_back(tmp);
        }

        return ans;
    }
};

Leetcode Problem:

• Longest Nice Subarray

Summary

• The problem is to find the length of the longest nice subarray in a given array of positive integers.

Approach

• The approach used is to use a sliding window technique, where we keep expanding the window to the right as long as the bitwise AND of the current prefix sum and the next element is 0
• If the condition is not met, we shrink the window from the left.

Complexity

• O(n), where n is the number of elements in the array.

Explanation

• The solution code initializes two pointers, l and r, to the start of the array
• It also initializes a variable, prefixSum, to keep track of the bitwise AND of the current prefix sum and the next element
• The code then enters a loop where it checks if the bitwise AND of the current prefix sum and the next element is 0
• If it is, the code adds the next element to the prefix sum and moves the right pointer to the right
• If it is not, the code subtracts the leftmost element from the prefix sum and moves the left pointer to the right
• The code keeps track of the maximum length of the nice subarray and returns it at the end.

Solution Code:

class Solution {
public:
    int longestNiceSubarray(vector& nums) {
        int l = 0;
        int r = 0;
        int prefixSum = 0;
        int ans = 0;
        while(l < nums.size() && r < nums.size()){
            if((prefixSum & nums[r]) == 0){
                prefixSum += nums[r];
                r++;
                ans = max(ans, r - l);
            }else{
                prefixSum -= nums[l];
                l++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Divide Array Into Equal Pairs

Summary

• Check if an array of integers can be divided into pairs of equal numbers.

Approach

• Count the occurrences of each number in the array and check if all counts are even
• If any count is odd, return false
• Otherwise, return true.

Complexity

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

Explanation

• The solution first counts the occurrences of each number in the array using an array cnt
• Then, it checks if all counts are even by iterating from 1 to 500
• If any count is odd, it returns false
• Otherwise, it returns true.

Solution Code:

class Solution {
public:
    int cnt[501] = {0};
    bool divideArray(vector& nums) {
        for(int n : nums){
            cnt[n]++;
        }
        for(int i = 1; i <= 500; i++){
            if(cnt[i] &1){
                return false;
            }
        }
        return true;
    }
};

Leetcode Problem:

• Minimum Time to Repair Cars

Summary

• Find the minimum time to repair all cars given the ranks of mechanics and the total number of cars.

Approach

• Binary Search: The solution uses binary search to find the minimum time to repair all cars
• It initializes two pointers, l and r, to the minimum and maximum possible times
• It then calculates the midpoint and checks if the number of cars that can be repaired within the time limit is less than or equal to the total number of cars
• If it is, it updates the minimum time and moves the left pointer to the right
• Otherwise, it updates the maximum time and moves the right pointer to the left
• This process continues until the two pointers meet, and the minimum time is returned.

Complexity

• O(n log m) where n is the number of mechanics and m is the maximum rank

Explanation

• The solution first initializes two pointers, l and r, to the minimum and maximum possible times
• It then calculates the midpoint and checks if the number of cars that can be repaired within the time limit is less than or equal to the total number of cars
• If it is, it updates the minimum time and moves the left pointer to the right
• Otherwise, it updates the maximum time and moves the right pointer to the left
• This process continues until the two pointers meet, and the minimum time is returned
• The time complexity is O(n log m) because the solution uses binary search, which has a time complexity of O(log m), and it needs to iterate over the mechanics, which takes O(n) time.

Solution Code:

class Solution {
public:
    long long repairCars(vector& ranks, int cars) {
        long long l = 0;
        long long r = 100000000000000;
        long long ans = 0;
        while(l <= r){
            long long mid = (l + r ) / 2;
            long long repairCar = 0;
            for(int i = 0 ; i < ranks.size(); i++){
                long long tmp = mid/ranks[i];
                repairCar += sqrt(tmp);
            }
            if(repairCar < cars){
                l = mid + 1;
            } else{
                ans = mid;
                r = mid - 1;
            }
        }
        return ans;
    }
};