'Algorithm'에 해당되는 글 244건

Leetcode Problem:

• Max Chunks To Make Sorted

Summary

• Given an integer array representing a permutation of the integers in the range [0, n - 1], find the largest number of chunks we can make to sort the array.

Approach

• We use two pointers, one from the end of the array and one from the beginning, to track the maximum element seen so far in each chunk
• We also use a stack to store the elements of the current chunk
• The time complexity of this approach is O(n), where n is the length of the input array.

Complexity

• O(n)

Explanation

• We initialize a rightMin array to keep track of the maximum element seen so far in each chunk
• We iterate through the array from right to left, and for each element, we check if the stack is empty
• If it is, we push the current element onto the stack and set the rightMin value to the current index
• If the stack is not empty and the current element is less than the top of the stack, we push the current element onto the stack and set the rightMin value to the top of the stack
• If the current element is greater than or equal to the top of the stack, we set the rightMin value to the top of the stack
• We then iterate through the array from left to right, and for each element, we update the leftMax value to be the maximum of the current leftMax value and the current element
• We then check if the leftMax value is less than or equal to the rightMin value
• If it is, we increment the ans variable by 1
• Finally, we return the ans variable, which represents the largest number of chunks we can make to sort the array.

Solution Code:

class Solution {
public:
    int rightMin[10];
    vector st;
    int maxChunksToSorted(vector& arr) {
        int ans = 0;
        for(int i = arr.size()-1; i >= 0; i--){
            if(st.empty()){
                st.push_back(arr[i]);
                rightMin[i] = arr.size();
            } else if(arr[i] < st.back()){
                rightMin[i] = st.back();
                st.push_back(arr[i]);
            } else{
                rightMin[i] = st.back();
            }
        }
        int leftMax = 0;
        for(int i = 0 ; i < arr.size(); i++){
            leftMax = max(leftMax, arr[i]);
            if(leftMax <= rightMin[i]){
                ans++;
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Final Prices With a Special Discount in a Shop

Summary

• Given an integer array prices where prices[i] is the price of the ith item in a shop, find the final price for each item considering a special discount.

Approach

• The solution uses a stack to keep track of the prices of items that have not been discounted yet
• It iterates through the prices array in reverse order, and for each item, it checks if there is a smaller item in the stack that can provide a discount
• If a discount is found, it is applied to the current item, and the updated price is pushed onto the stack
• If no discount is found, the current price is pushed onto the stack as is.

Complexity

• O(n), where n is the number of items in the prices array, because each item is processed once.

Explanation

• The solution uses a stack to efficiently find the smallest price that can provide a discount for each item
• It starts by iterating through the prices array in reverse order, and for each item, it checks if there is a smaller item in the stack that can provide a discount
• If a discount is found, it is applied to the current item, and the updated price is pushed onto the stack
• This process continues until the stack is empty, at which point the current item's price is pushed onto the stack as is
• This approach ensures that each item is processed only once and that the stack is always in the correct order to find the smallest price that can provide a discount.

Solution Code:

class Solution {
public:
    vector st;
    vector finalPrices(vector& prices) {
        for(int i = prices.size() - 1; i >= 0 ; i--){
            while(st.size() != 0 && st.back() > prices[i]){
                st.pop_back();
            }
            if(st.size() == 0){
                st.push_back(prices[i]);
            } else{
                prices[i] -= st.back();
                st.push_back(prices[i] + st.back());
            }
        }
        return prices;
    }
};

Leetcode Problem:

• Construct String With Repeat Limit

Summary

• Construct a new string using the characters of s such that no letter appears more than repeatLimit times in a row, and return the lexicographically largest possible string.

Approach

• The approach used is to first count the frequency of each character in s
• Then, we start with the largest possible character and keep adding it to the result string until we reach the repeatLimit limit
• If we encounter a character that is already at the limit, we remove the last occurrence of that character from the result string and replace it with the next character in the sorted order.

Complexity

• O(n log n) where n is the length of s, due to the sorting operation.

Solution Code:

class Solution {
public:
    vector arr;
    int charCnt[256];
    string repeatLimitedString(string s, int repeatLimit) {
        for(int i = 0 ; i < s.size(); i++){
            charCnt[s[i]]++;
        }
        for(int i = 'z'; i >= 'a'; i--){
            while(charCnt[i]--){
                arr.push_back(i);
            }
        }
        int repeat = 1;
        int beforeChar = arr[0];
        int j = 0;
        for(int i = 1 ; i < arr.size(); i++){
            if(beforeChar == arr[i]){
                repeat++;
            } else {
                repeat = 1;
                beforeChar = arr[i];
            }
            if(repeat > repeatLimit){
                if (j <= i){
                    j = i + 1;
                }
                while(j < arr.size() && beforeChar == arr[j]){
                    j++;
                }
                if(j >= arr.size()){
                    arr[i] = 0;
                    break;
                }
                char t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                beforeChar = arr[i];
                repeat = 1;
                j++;
            }
        }
        string ans = "";
        for(int i = 0 ; i < arr.size(); i++){
            if(arr[i] == 0) break;
            ans += arr[i];
        }
        return ans;
    }
};

Leetcode Problem:

• Final Array State After K Multiplication Operations I

Summary

• This solution performs k operations on the input array nums
• In each operation, it finds the minimum value in nums and replaces it with the minimum value multiplied by a given multiplier.

Approach

• The solution uses a min-heap data structure to efficiently find the minimum value in the array
• It first pushes all elements of the array into the heap
• Then, it performs k operations by popping the minimum element from the heap, multiplying it by the multiplier, and pushing it back into the heap
• This process is repeated k times to achieve the final state of the array.

Complexity

• O(k log n) where n is the size of the input array, as each operation involves popping from the heap and pushing back into the heap, which takes log n time, and k operations are performed.

Explanation

• The solution uses a min-heap to efficiently find the minimum element in the array
• The min-heap is implemented using a binary heap data structure
• The cmp function used to compare elements in the heap is defined as a lambda function that compares the indices of the elements in the array if the values are equal
• This ensures that the smallest index is always at the root of the heap
• The getFinalState function first pushes all elements of the input array into the heap
• Then, it performs k operations by popping the minimum element from the heap, multiplying it by the multiplier, and pushing it back into the heap
• This process is repeated k times to achieve the final state of the array.

Solution Code:

struct _node{
    int idx;
    int val;
};

template 
struct _heap{
    int size;
    T arr[101];
    function cmp;
    _heap(){
        size = 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx >> 1], arr[idx])){
            T t = arr[idx >> 1];
            arr[idx >> 1] = arr[idx];
            arr[idx] = t;
            idx >>= 1;
        }
    }
    T pop(){
        T 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])){
                T t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    vector getFinalState(vector& nums, int k, int multiplier) {
        h.cmp = [&nums](int a, int b){
            if(nums[a] != nums[b]){
                return nums[a] > nums[b];
            }
            return a > b;
        };
        for(int i = 0 ; i < nums.size(); i++){
            h.push(i);
        }
        while(k--){
            int idx = h.pop();
            nums[idx] *= multiplier;
            h.push(idx);
        }
        return nums;
    }
};

Leetcode Problem:

• Maximum Average Pass Ratio

Summary

• Given a 2D array of classes and extra students, find the maximum average pass ratio after assigning the extra students.

Approach

• We use a max heap to store the classes, where the pass ratio of each class is used as the comparison key
• We start by pushing all classes into the heap
• Then, we pop the class with the lowest pass ratio and push a new class with the increased pass ratio until we have assigned all extra students
• Finally, we calculate the average pass ratio by summing the pass ratios of all classes and dividing by the number of classes.

Complexity

• O(n log n + m log n) where n is the number of classes and m is the number of extra students

Explanation

• The time complexity of the solution is O(n log n + m log n) because we push all classes into the heap in O(n log n) time and pop the class with the lowest pass ratio in O(log n) time, and we repeat this process m times
• The space complexity is O(n) because we store all classes in the heap.

Solution Code:

struct _node{
    int pass;
    int total;
};
struct _heap{
    _node arr[100002];
    int size;
    function cmp;
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx/2], arr[idx])){
            _node t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            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 t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};
class Solution {
public:
    _heap h;
    double getRatio(_node classs){
        double pass = classs.pass;
        double total = classs.total;
        return pass / total;
    }
    double diffRatio(_node a){
        double ratio1 = getRatio(a);
        double ratio2 = getRatio({a.pass+1, a.total+1});
        return ratio2 - ratio1;
    }
    double maxAverageRatio(vector>& classes, int extraStudents) {
        h.cmp = [&](_node a, _node b) {
            double diffRatio1 = diffRatio(a);
            double diffRatio2 = diffRatio(b);
            return diffRatio1 < diffRatio2;
        };
        for(int i = 0 ; i < classes.size(); i++){
            h.push({classes[i][0], classes[i][1]});
        }
        while(extraStudents--){
            _node clas = h.pop();
            h.push({clas.pass+1, clas.total+1});
        }
        double sum = 0;
        while(!h.empty()){
            sum += getRatio(h.pop());
        }
        return sum / classes.size();
    }
};

Leetcode Problem:

• Maximum Absolute Sum of Any Subarray

Summary

• Given an integer array, find the maximum absolute sum of any subarray.

Approach

• Use two pointers to track the maximum and minimum prefix sum, then return the maximum of the two absolute values.

Complexity

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

Explanation

• The solution works by iterating over the array twice, once to find the maximum prefix sum and once to find the minimum prefix sum
• The maximum prefix sum is updated whenever a positive number is encountered, and the minimum prefix sum is updated whenever a negative number is encountered
• The maximum of the two absolute values is then returned as the result.

Solution Code:

class Solution {
public:
    int maxAbsoluteSum(vector& nums) {
        int r = 0;
        int l = 0;
        int plusMax = 0;
        int prefixSum = 0;
        for(int num : nums){
            prefixSum += num;
            if(prefixSum < 0) prefixSum = 0;
            plusMax = max(plusMax, prefixSum);
        }

        int minusMin = 0;
        prefixSum = 0;
        for(int num:nums){
            prefixSum += num;
            if(prefixSum > 0) prefixSum = 0;
            minusMin = min(minusMin, prefixSum);
        }
        return plusMax > abs(minusMin) ? plusMax : abs(minusMin);
    }
};

Leetcode Problem:

• Number of Sub-arrays With Odd Sum

Summary

• Find the number of subarrays with an odd sum in a given array of integers.

Approach

• The solution uses a prefix sum approach to keep track of the current sum of the subarray
• It also uses two counters, evenCount and oddCount, to keep track of the number of subarrays with even and odd sums respectively
• The time complexity is O(n) where n is the size of the array.

Complexity

• O(n)

Explanation

• The solution iterates over the array and for each element, it checks if the prefix sum is odd or even
• If it's odd, it increments the oddCount and adds the evenCount to the answer
• If it's even, it increments the evenCount and adds the oddCount to the answer
• The answer is then taken modulo MOD to prevent overflow
• The solution returns the final answer.

Solution Code:

class Solution {
public:
    #define MOD 1000000007
    int numOfSubarrays(vector& arr) {
        
        long long prefixSum = 0;
        int evenCount = 1;
        int oddCount = 0;
        int ans = 0;
        for(int i = 0 ; i < arr.size(); i++){
            prefixSum += arr[i];

            if(prefixSum & 1){
                oddCount++;
                ans += evenCount;
            } else{
                evenCount++;
                ans += oddCount;
            }
            ans %= MOD;
        }
        return ans;
    }
};

Leetcode Problem:

• Continuous Subarrays

Summary

• This problem requires finding the total number of continuous subarrays in a given array where the absolute difference between any two elements in the subarray is less than or equal to 2.

Approach

• The approach used here is to use two heaps, a min heap and a max heap, to keep track of the indices of the smallest and largest elements in the current window
• The window is expanded by pushing the next element into the heaps and shrinking the window by popping elements from the heaps until the difference between the largest and smallest elements exceeds 2
• The total number of continuous subarrays is then calculated by summing up the size of the window for each possible window size.

Complexity

• O(n log n) due to the heap operations

Solution Code:

class Solution {
public:
    struct _heap{
        function cmp;
        int arr[100002];
        int size;
        _heap(){
            size = 1;
        }
        void push(int a){
            arr[size++] = a;
            int idx = size - 1;
            while(idx > 1 && !cmp(arr[idx/2], arr[idx])){
                int t = arr[idx/2];
                arr[idx/2] = arr[idx];
                arr[idx] = t;
                idx/=2;
            }
        }
        int pop(){
            int 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])){
                    int t = arr[i];
                    arr[i] = arr[j];
                    arr[j] = t;
                    i = j;
                } else{
                    break;
                }
            }
            return ret;
        }
        int top(){
            return arr[1];
        }
        bool empty(){
            return size == 1;
        }
    };
    long long continuousSubarrays(vector& nums) {
        long long sum = 0;
        long long l = 0;
        long long r = 0;
        _heap minHeap;
        _heap maxHeap;
        minHeap.cmp = [&nums](int a, int b) { return nums[a] < nums[b] ;};
        maxHeap.cmp = [&nums](int a, int b) { return nums[a] > nums[b] ;};
        while(r < nums.size()){
            minHeap.push(r);
            maxHeap.push(r);
            
            while(l < r && nums[maxHeap.top()] - nums[minHeap.top()] > 2){
                l++;
                while(!minHeap.empty() && minHeap.top() < l){
                    minHeap.pop();
                }
                while(!maxHeap.empty() && maxHeap.top() < l){
                    maxHeap.pop();
                }
            }
            sum += r - l + 1;
            r++;
        }
        return sum;
    }
};

Leetcode Problem:

• Find Score of an Array After Marking All Elements

Summary

• Given an array of positive integers, apply a scoring algorithm where the smallest unmarked integer is chosen, added to the score, and its adjacent elements are marked
• The process is repeated until all elements are marked.

Approach

• A priority queue (implemented as a heap) is used to store the unmarked elements along with their indices
• The heap is updated after each iteration to reflect the newly marked elements
• The algorithm iterates until the heap is empty, at which point the final score is returned.

Complexity

• O(n log n) due to the heap operations (insertion and deletion)

Solution Code:

struct _node{
    int idx;
    int val;
};

bool _cmp(_node a, _node b){
    if(a.val != b.val) return a.val < b.val;
    return a.idx < b.idx;
}

struct _heap{
    _node arr[100002];
    int size;
    _heap(){
        size = 1;
    }
    void push(_node a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && _cmp(arr[idx], arr[idx/2])){
            _node tmp = arr[idx/2];
            arr[idx/2] = arr[idx];
            arr[idx] = tmp;
            idx >>= 1;
        }
    }
    _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+1], arr[j])){
                j++;
            }
            if(_cmp(arr[j], arr[i])){
                _node t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;

            } else {
                break;
            }
        }

        return ret;

    }
    bool empty(){
        return size == 1;
    }
    _node peek(){
        return arr[1];
    }
};

class Solution {
public:
    _heap h;
    _heap remove;
    bool removed[100002];
    long long findScore(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            h.push({i, nums[i]});
        }
        long long sum = 0;
        while(!h.empty()){
            while(!h.empty() && h.peek().val == remove.peek().val && 
                                h.peek().idx == remove.peek().idx){
                remove.pop();
                h.pop();
            }
            if(h.empty()) break;
            _node nod = h.pop();
            cout << nod.val << endl;
            sum += nod.val;
            if(nod.idx -1 >= 0 && !removed[nod.idx-1]){
                removed[nod.idx-1] = true;
                remove.push({nod.idx-1, nums[nod.idx-1]});
            }
            if(nod.idx+1 < nums.size()  && !removed[nod.idx+1]){
                removed[nod.idx+1] = true;
                remove.push({nod.idx+1, nums[nod.idx+1]});
            }
        }
        return sum;
    }
};

Leetcode Problem:

• Take Gifts From the Richest Pile

Summary

• The problem requires to find the number of gifts remaining after k seconds, where each second, the maximum pile is chosen and its size is reduced to the floor of its square root.

Approach

• A heap data structure is used to store the number of gifts in each pile
• The pop operation is used to choose the maximum pile and reduce its size to the floor of its square root
• The process is repeated for k seconds.

Complexity

• O(n log n) due to the heap operations, where n is the number of piles.

Explanation

• The provided solution code first initializes a heap with the number of gifts in each pile
• Then, it enters a loop that runs for k seconds
• In each iteration, it pops the maximum pile from the heap, reduces its size to the floor of its square root, and pushes it back into the heap
• Finally, it calculates the total number of gifts remaining by summing up the sizes of all piles in the heap.

Solution Code:

struct _heap{
    int arr[1002];
    int size;
    _heap(){
        size = 1;
    }
    void push(int a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx] > arr[idx/2]){
            int t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx/=2;
        }
    }
    int pop(){
        int ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if(j>= size) break;
            if(j+1 < size && arr[j] < arr[j+1]){
                j++;
            }
            if(arr[i] < arr[j]){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            } else {
                break;
            }
        }


        return ret;
    }
};

class Solution {
public:
    _heap h;
    long long pickGifts(vector& gifts, int k) {
        for(int i = 0 ; i < gifts.size(); i++){
            h.push(gifts[i]);
        }
        while(k--){
            int gift = h.pop();
            int i = 1;
            while(i*i <= gift) i++;
            i--;
            h.push(i);
        }
        long long sum = 0;
        for(int i = 1; i < h.size; i++){
            sum += h.arr[i];
        }
        return sum;
    }
};