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

Leetcode Problem:

• Take K of Each Character From Left and Right

Summary

• Given a string s consisting of the characters 'a', 'b', and 'c' and a non-negative integer k, find the minimum number of minutes needed to take at least k of each character.

Approach

• The approach used is to use a sliding window technique
• The window is initially set to the entire string
• If the count of each character in the window is greater than or equal to k, the window is moved to the right
• If the count of each character in the window is less than k, the window is moved to the left
• The minimum number of minutes is updated whenever a valid window is found.

Complexity

• O(N^2) where N is the length of the string

Explanation

• The solution first initializes a count array to keep track of the count of each character in the string
• It then iterates over the string and checks if the count of each character is greater than or equal to k
• If it is, the window is moved to the right
• If it is not, the window is moved to the left
• The minimum number of minutes is updated whenever a valid window is found
• The solution then returns the minimum number of minutes.

Solution Code:

class Solution {
public:
    int cnt[256];
    int takeCharacters(string s, int k) {
        int N = s.size();
        int ans= -1;
        int i;
        for(i = 0 ; i < N; i++){
            cnt[s[i]]++;
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = i+1;
                break;
            }
        }
        if(ans == -1) return -1;
        int r = N -1;
        while(i>=0){
            cnt[s[i]]--;
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = min(ans,i + N - r - 1);
                i--;
                continue;
            }
            while (r >= 0 && (cnt['a'] < k || cnt['b'] < k || cnt['c'] < k)){
                cnt[s[r]]++;
                r--;
            }
            if(cnt['a'] >= k && cnt['b'] >= k && cnt['c'] >= k){
                ans = min(ans, i + 1 + N - r -1);
            }

            i--;
        }
        
        return ans;
    }
};

Leetcode Problem:

• Maximum Sum of Distinct Subarrays With Length K

Summary

• Find the maximum subarray sum of all the subarrays of a given array that meet the conditions of having a length of k and all elements distinct.

Approach

• Use a sliding window approach with a hashmap to store the previous index of each number
• Iterate through the array, adding each number to the current sum and removing the number at the leftmost index of the window if it's out of the window
• If the window size is equal to k, update the maximum sum if the current sum is greater.

Complexity

• O(n * k) where n is the length of the array, because in the worst case we might have to check all numbers for each window size k.

Explanation

• The solution uses a sliding window approach with a hashmap to store the previous index of each number
• We initialize the hashmap and the maximum sum
• Then we iterate through the array, adding each number to the current sum and removing the number at the leftmost index of the window if it's out of the window
• If the window size is equal to k, we update the maximum sum if the current sum is greater
• We use a hashmap to store the previous index of each number to efficiently check if a number has been seen before in the current window.

Solution Code:

class Solution {
public:
    long long maximumSubarraySum(vector& nums, int k) {
        long long res = 0;
        unordered_map prev_idx;  // num -> prev index of num
        long long cur_sum = 0;
        
        int l = 0;
        
        for (int r = 0; r < nums.size(); r++) {
            cur_sum += nums[r];
            
            int i = -1;
            if (prev_idx.find(nums[r]) != prev_idx.end()) {
                i = prev_idx[nums[r]];
            }
            
            while (l <= i || r - l + 1 > k) {
                cur_sum -= nums[l];
                l++;
            }
            
            if (r - l + 1 == k) {
                res = max(res, cur_sum);
            }
            
            prev_idx[nums[r]] = r;
        }
        
        return res;
    }
};

Leetcode Problem:

• Defuse the Bomb

Summary

• A circular array code of length n and a key k are given
• The goal is to decrypt the code by replacing every number with the sum of the next k numbers if k is positive, the sum of the previous k numbers if k is negative, and 0 if k is 0.

Approach

• The approach used is to iterate through the array and for each element, calculate the sum of the next k numbers if k is positive, the sum of the previous k numbers if k is negative, and 0 if k is 0
• The sum is then appended to the result vector.

Complexity

• O(n * |k|) where n is the length of the code array and |k| is the absolute value of the key k.

Solution Code:

class Solution {
public:
    vector decrypt(vector& code, int k) {
        vector ans;
        int N = code.size();
        for(int i = 0 ; i < N; i++){
            int sum = 0;
            for(int j = 1; j <= abs(k); j++){
                int idx;
                if (k > 0){
                    idx = (i + j) % N;
                } else if(k < 0) {
                    idx = (i - j + N) % N;
                } else{
                    break;
                }
                sum += code[idx];
            }
            ans.push_back(sum);
        }
        return ans;
    }
};

Leetcode Problem:

• Shortest Subarray with Sum at Least K

Summary

• Given an integer array and an integer k, return the length of the shortest non-empty subarray with a sum of at least k.

Approach

• Use a deque to store the prefix sum and its corresponding end index
• Iterate through the array, updating the prefix sum and checking if it's greater than or equal to k
• If it is, update the result with the minimum length
• If the prefix sum minus the front element is greater than or equal to k, remove the front element from the deque
• If the back element's prefix sum is greater than the current prefix sum, remove it from the deque
• Finally, return the result or -1 if no such subarray exists.

Complexity

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

Explanation

• The time complexity is O(n) because we're doing a single pass through the array
• The space complexity is O(n) for storing the deque.

Solution Code:

class Solution {
public:
    int shortestSubarray(vector& nums, int k) {
        int res = INT_MAX;
        long long curSum = 0;
        deque> q; // (prefix_sum, end_idx)
        for(int r = 0; r < nums.size(); r++){
            curSum += nums[r];

            if(curSum >= k){
                res = min(res, r + 1);
            }

            while (!q.empty() && curSum - q.front().first >= k){
                auto [prefix, endIdx] = q.front();
                q.pop_front();
                res = min(res, r - endIdx);
            }
            while (!q.empty() && q.back().first > curSum) {
                q.pop_back();
            }
            q.push_back({curSum, r});
        }
        
        return res == INT_MAX ? -1 : res;
    }
};

Leetcode Problem:

• Find the Power of K-Size Subarrays I

Summary

• This solution is used to find the power of all subarrays of size k in a given array of integers
• The power of a subarray is defined as its maximum element if all its elements are consecutive and sorted in ascending order, otherwise -1.

Approach

• This solution uses a sliding window approach with two nested loops to check for consecutive elements
• It keeps track of the current window's start index, end index, and the count of consecutive elements
• If the count of consecutive elements equals k, the maximum element in the current window is added to the result array
• Otherwise, -1 is added.

Complexity

• O(n*k) where n is the size of the input array, k is the size of the subarray

Solution Code:

class Solution {
public:
    vector resultsArray(vector& nums, int k) {
        vector ans;
        int acd_cnt = 1;
        int cmp_num = nums[0];
        for(int i = 1 ; i < k ;i++){
            if(cmp_num + 1 == nums[i]){
                acd_cnt++;
            } else {
                acd_cnt = 1;
            }
            cmp_num = nums[i];
        }
        if(acd_cnt == k){
            ans.push_back(cmp_num);
        } else {
            ans.push_back(-1);
        }
        for(int i = k ; i < nums.size(); i++){
            if(cmp_num + 1 == nums[i]){
                acd_cnt++;
            } else {
                acd_cnt = 1;
            }
            if(acd_cnt >= k){
                ans.push_back(nums[i]);
            } else {
                ans.push_back(-1);
            }
            cmp_num = nums[i];
        }
        return ans;
    }
};

Leetcode Problem:

• Find Elements in a Contaminated Binary Tree

Summary

• The problem requires to recover a binary tree from a contaminated tree where all node values are -1 and then find if a target value exists in the recovered tree.

Approach

• The solution uses a helper function traversal to populate a boolean array s with the original values of the binary tree
• The traversal function is a depth-first search that assigns the original values to the nodes and marks them in the s array
• The find function simply checks the s array for the target value.

Complexity

• O(n), where n is the number of nodes in the tree, because each node is visited once during the traversal.

Explanation

• The solution uses a boolean array s of size 2000001 to keep track of the original values of the nodes
• The traversal function is a recursive depth-first search that assigns the original values to the nodes and marks them in the s array
• The find function simply checks the s array for the target value
• This approach ensures that the original values are recovered and can be used to check for the existence of a target value.

Solution Code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class FindElements {
public:
    bool s[2000001] = {0};
    void traversal(TreeNode* root, int val){
        if(root == nullptr) return;
        root->val = val;
        s[val] = true;
        traversal(root->left, val*2 + 1);
        traversal(root->right, val*2 + 2);
    }
    FindElements(TreeNode* root) {
        traversal(root, 0);
    }
    
    bool find(int target) {
        return s[target];
    }
};

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements* obj = new FindElements(root);
 * bool param_1 = obj->find(target);
 */

Leetcode Problem:

• Shortest Subarray to be Removed to Make Array Sorted

Summary

• Given an integer array, remove a subarray such that the remaining elements are non-decreasing and return the length of the shortest subarray to remove.

Approach

• The approach used is to find the first decreasing pair in the array and then try to find the longest subarray that can be removed without breaking the non-decreasing sequence
• If the first element is greater than or equal to the last element, we can return the length of the subarray that can be removed from the beginning
• Otherwise, we need to try to find the longest subarray that can be removed from the end.

Complexity

• O(n) where n is the size of the array

Explanation

• The solution starts by finding the first decreasing pair in the array
• If no such pair is found, it means the array is already non-decreasing, so we return 0
• Otherwise, we find the longest subarray that can be removed without breaking the non-decreasing sequence
• We do this by trying to find the longest subarray that can be removed from the end of the array
• If the first element is greater than or equal to the last element, we can return the length of the subarray that can be removed from the beginning
• Otherwise, we need to try to find the longest subarray that can be removed from the end
• We use two pointers, left and right, to find the longest subarray that can be removed
• We start by trying to find the longest subarray that can be removed from the end of the array
• If the current element is greater than or equal to the previous element, we move the right pointer to the previous element
• If the current element is less than the previous element, we move the left pointer to the previous element
• We repeat this process until we find the longest subarray that can be removed without breaking the non-decreasing sequence
• We then return the length of the subarray that can be removed.

Solution Code:

class Solution {
public:
    int findLengthOfShortestSubarray(vector& arr) {
        int left;
        for(left = 0 ; left < arr.size() - 1; left++){
            if(arr[left] > arr[left+1]){
                break;
            }
        }
        if (left == arr.size() - 1) return 0;
        
        int right;
        for(right = arr.size() - 1; right > 0; right--){
            if(arr[right-1] > arr[right]){
                break;
            }
        }
        if (arr[left] <= arr[right]) return right - left -1;
        int t = arr.size() - left -1;
        int ans = min(t, right);
        int i = 0;
        while (i <= left && right < arr.size()){
            if (arr[i] <= arr[right]){
                ans = min(ans, right - i - 1);
            }

            if (i+1 <= left && arr[i+1] <= arr[right]){
                i++;
            } else{
                right++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Minimized Maximum of Products Distributed to Any Store

Summary

• This problem requires finding the minimum possible maximum number of products given to any store when distributing products to specialty retail stores.

Approach

• The solution uses a binary search approach to find the minimum possible maximum number of products
• It starts by initializing two pointers, one at 1 and one at 100000, and then iteratively calculates the midpoint
• It then checks if the maximum number of products that can be given to each store is less than or equal to the total number of stores
• If it is, it updates the right pointer and the answer; otherwise, it updates the left pointer.

Complexity

• O(m log max(quantities[i]))

Explanation

• The solution works by using a binary search approach to find the minimum possible maximum number of products
• It starts by initializing two pointers, one at 1 and one at 100000, and then iteratively calculates the midpoint
• It then checks if the maximum number of products that can be given to each store is less than or equal to the total number of stores
• If it is, it updates the right pointer and the answer; otherwise, it updates the left pointer
• This approach ensures that the solution is efficient and can handle large inputs.

Solution Code:

class Solution {
public:
    int minimizedMaximum(int n, vector& quantities) {
        int ans = quantities[0];
        int l = 1;
        int r = 100000;
        while(l <= r){
            int mid = (l + r) / 2;
            int cnt = 0;
            for(int i = 0 ; i < quantities.size(); i++){
                cnt += quantities[i] / mid;
                if (quantities[i] % mid != 0){
                    cnt++;
                }
            }
            if (cnt <= n){
                r = mid - 1;
                ans = mid;
            } else {
                l = mid + 1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Count the Number of Fair Pairs

Summary

• The problem is to count the number of fair pairs in a given array of integers within a specified range.

Approach

• The solution uses a two-pointer technique to find the range of possible values for each pair, and then calculates the number of fair pairs by summing up the counts of pairs that fall within the specified range.

Complexity

• O(n log n + n log n) = O(n log n)

Explanation

• The solution first sorts the input array
• Then, for each element in the array, it uses two pointers (low and up) to find the range of possible values for the other element in the pair
• The low pointer is used to find the smallest possible value for the other element, and the up pointer is used to find the largest possible value
• The solution then calculates the number of fair pairs by summing up the counts of pairs that fall within the specified range.

Solution Code:

class Solution {
public:
    long long countFairPairs(vector& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        
        long long ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            int l = i+1;
            int r = nums.size() - 1;
            int low = 123456789;
            while(l <= r){
                int mid = (l + r ) / 2;
                if(nums[mid] + nums[i] >= lower){
                    r = mid - 1;
                    low = mid;
                }else{
                    l = mid + 1;
                }
            }
            l = i + 1;
            r = nums.size() - 1;
            int up = 0;
            while(l <= r){
                int mid = (l + r ) / 2;
                if(nums[mid] + nums[i] <= upper){
                    l = mid + 1;
                    up = mid;
                }else{
                    r = mid - 1;
                }
            }
            if(low<=up){
                ans += up - low + 1;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Most Beautiful Item for Each Query

Summary

• Given a 2D integer array of item prices and beauties, and a 0-indexed integer array of queries, determine the maximum beauty of an item whose price is less than or equal to each query.

Approach

• The solution uses a modified merge sort algorithm to sort the items based on their prices
• Then, it iterates over the sorted items and updates the beauty of each item if its price is less than the current query
• Finally, it uses a binary search approach to find the maximum beauty for each query.

Complexity

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

Explanation

• The modified merge sort algorithm sorts the items based on their prices and then updates the beauty of each item if its price is less than the current query
• This is done to ensure that the items are sorted in ascending order of their prices
• The binary search approach is used to find the maximum beauty for each query by finding the first item whose price is greater than the query and returning its beauty.

Solution Code:

struct _item{
    int price;
    int beauty;
};

class Solution {
public:
    _item arr[100001];
    _item tmp[100001];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = l;
        while(i <= mid & j <= r){
            if(arr[i].price < arr[j].price){
                tmp[cur++] = arr[i++];
            } else if (arr[i].price > arr[j].price){
                tmp[cur++] = arr[j++];
            } else{
                if(arr[i].beauty >= arr[j].beauty){
                    tmp[cur++] = arr[i++];
                } else {
                    tmp[cur++] = arr[j++];
                }
            }
        }
        while(i<= mid){
            tmp[cur++] = arr[i++];
        }
        for(i = l; i < cur; i++){
            arr[i] = tmp[i];
        }
    }
    void merge_sort(int l, int r){
        if(l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(l, mid);
        merge_sort(mid+1, r);
        merge(l, mid, r);
    }
    vector maximumBeauty(vector>& items, vector& queries) {
        for(int i = 0 ; i < items.size(); i++){
            arr[i].price = items[i][0];
            arr[i].beauty = items[i][1];
        }
        merge_sort(0, items.size() - 1);
        int maxBeauty = arr[0].beauty;
        for(int i = 1 ; i < items.size(); i++){
            if(arr[i].beauty < maxBeauty){
                arr[i].beauty = maxBeauty;
            } else {
                maxBeauty = arr[i].beauty;
            }
        }
        vector ansV;
        for(int i = 0 ; i < queries.size(); i++){
            int l = 0;
            int r = items.size() - 1;
            int ans = 0;
            while(l <= r){
                int mid = (l + r ) / 2;
                if (arr[mid].price > queries[i]){
                    r = mid - 1;
                    continue;
                }
                ans = arr[mid].beauty;
                l = mid + 1;
            }
            ansV.push_back(ans);
        }
        return ansV;
    }
};