'분류 전체보기'에 해당되는 글 290건

Leetcode Problem:

• Maximum Count of Positive Integer and Negative Integer

Summary

• Given a sorted array of integers, return the maximum between the number of positive integers and the number of negative integers.

Approach

• The approach used is to simply iterate through the array and count the number of positive and negative integers
• Then, return the maximum of the two counts.

Complexity

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

Explanation

• The solution iterates through the array once, using a single loop to count the number of positive and negative integers
• The time complexity is linear because it only needs to examine each element once
• The space complexity is O(1) because it only uses a constant amount of space to store the counts.

Solution Code:

class Solution {
public:
    int maximumCount(vector& nums) {
        int minus = 0;
        int plus = 0;
        for(int i = 0 ; i < nums.size(); i++){
            if(nums[i] < 0){
                minus++;
            }else if (nums[i] > 0){
                plus++;
            }
        }
        return max(minus, plus);
    }
};

Leetcode Problem:

• Number of Substrings Containing All Three Characters

Summary

• The problem is to find the number of substrings in a given string that contain all three characters 'a', 'b', and 'c' at least once.

Approach

• The solution uses a sliding window approach with two pointers, 'l' and 'r', to track the current substring
• It iterates over the string with 'r' and expands the window to the right
• When all three characters are found in the window, it shrinks the window from the left until all characters are found again.

Complexity

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

Explanation

• The solution uses a 1D array 'cnt' to count the occurrences of each character
• The 'all_include' function checks if all three characters are present in the 'cnt' array
• The 'numberOfSubstrings' function iterates over the string with 'r' and expands the window to the right
• When all three characters are found in the window, it adds the number of substrings that can be formed with the current window to the 'ans' variable
• The window is then shrunk from the left until all characters are found again.

Solution Code:

class Solution {
    int cnt[256] = {0};
public:
    bool all_include(){
        return cnt['a'] > 0 && cnt['b'] > 0 && cnt['c'] > 0;
    }
    int numberOfSubstrings(string s) {
        int l = 0;
        int r = 0;
        int ans = 0;
        while(r < s.size()){
            cnt[s[r]]++;

            while(all_include() && l < r){
                ans += s.size() - r;
                cnt[s[l]]--;
                l++;
            }

            r++;

        }
        return ans;
    }
};

Leetcode Problem:

• Count of Substrings Containing Every Vowel and K Consonants II

Summary

• Count the number of substrings in a given word that contain every vowel at least once and exactly k consonants.

Approach

• Sliding Window Technique with Hash Map, using two helper functions to track vowel and consonant counts.

Complexity

• O(n^2), where n is the length of the word, due to nested loops in the sliding window approach.

Solution Code:

class Solution {
public:
    long countOfSubstrings(string word, int k) {
        return atLeastK(word, k) - atLeastK(word, k + 1);
    }

private:
    long atLeastK(string word, int k) {
        long numValidSubstrings = 0;
        int start = 0;
        int end = 0;
        // Keep track of counts of vowels and consonants.
        unordered_map vowelCount;
        int consonantCount = 0;

        // Start sliding window.
        while (end < word.length()) {
            // Insert new letter.
            char newLetter = word[end];

            // Update counts.
            if (isVowel(newLetter)) {
                vowelCount[newLetter]++;
            } else {
                consonantCount++;
            }

            // Shrink window while we have a valid substring.
            while (vowelCount.size() == 5 and consonantCount >= k) {
                numValidSubstrings += word.length() - end;
                char startLetter = word[start];
                if (isVowel(startLetter)) {
                    if (--vowelCount[startLetter] == 0) {
                        vowelCount.erase(startLetter);
                    }
                } else {
                    consonantCount--;
                }
                start++;
            }

            end++;
        }

        return numValidSubstrings;
    }

    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};

Leetcode Problem:

• Alternating Groups II

Summary

• Find the number of alternating groups in a circle of red and blue tiles

Approach

• This solution uses a circular approach to find the alternating groups
• It first extends the colors array to make it circular, then it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups and increments the counter if a group is found.

Complexity

• O(N) where N is the number of tiles in the circle

Explanation

• The solution works by first extending the colors array to make it circular
• This is done by adding the first element to the end of the array
• Then, it iterates through the array in two passes: one from the start and one from the middle of the array
• In each pass, it checks for the presence of alternating groups by comparing the current color with the previous color
• If the colors are alternating, it increments the counter
• Finally, it returns the counter as the number of alternating groups

Solution Code:

class Solution {
public:
    int numberOfAlternatingGroups(vector& colors, int k) {
        int N = colors.size();
        for(int i = 0 ; i < N; i++){
            colors.push_back(colors[i]);
        }
        int cnt = 1;
        int cur = colors[0] ^ 1;
        int ans = 0;
        for(int i = 1; i < k; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            cur = colors[i] ^ 1;
        }
        if(cnt >= k){
            ans++;
        }
        for(int i = k; i < N + k - 1; i++){
            if(cur == colors[i]){
                cnt++;
            }else{
                cnt = 1;
            }
            if(cnt >= k){
                ans++;
            }
            cur = colors[i] ^ 1;
        }
        return ans;
    }
};

Leetcode Problem:

• Minimum Recolors to Get K Consecutive Black Blocks

Summary

• The problem is to find the minimum number of operations required to have at least k consecutive black blocks in a given string of blocks, where each block is either 'W' or 'B'.

Approach

• The solution uses a sliding window approach to track the number of consecutive black blocks
• It initializes a counter for the number of white blocks within the first k blocks and then slides the window to the right, updating the counter and the minimum number of operations required.

Complexity

• O(n), where n is the length of the string, as each character in the string is processed once.

Explanation

• The solution starts by initializing a counter for the number of white blocks within the first k blocks
• It then slides the window to the right, updating the counter and the minimum number of operations required
• If a white block is encountered within the window, the counter is decremented
• If a black block is encountered within the window, the counter is incremented
• The minimum number of operations required is updated at each step to reflect the current number of white blocks within the window.

Solution Code:

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int w = 0;
        for(int i = 0 ; i < k; i++){
            if(blocks[i] == 'W') w++;
        }
        int ans = w;
        for(int i = k; i < blocks.size(); i++){
            if(blocks[i - k] == 'W'){
                w--;
            }
            if(blocks[i] == 'W'){
                w++;
            }
            ans = min(ans, w);
        }
        return ans;
    }
};

Leetcode Problem:

• Closest Prime Numbers in Range

Summary

• Find two prime numbers within a given range with the minimum difference.

Approach

• Use the Sieve of Eratosthenes algorithm to generate prime numbers, then iterate through the range to find the pair with the minimum difference.

Complexity

• O(n log log n) due to the Sieve of Eratosthenes algorithm, where n is the upper bound of the range.

Explanation

• The Sieve of Eratosthenes algorithm is used to generate prime numbers up to the given upper bound
• Then, iterate through the range to find the pair of prime numbers with the minimum difference
• If no such pair exists, return [-1, -1].

Solution Code:

class Solution {
public:
    bool isPrime[1000001] = {false};
    vector closestPrimes(int left, int right) {
        for(int i = 2; i <= right; i++){
            isPrime[i] = true;
        }
        for(int i = 2; i*i <= right; i++){
            if(!isPrime[i]){
                continue;
            }
            for(int j = i *2; j <= right; j += i){
                isPrime[j] = false;
            }
        }
        
        vector ans;
        int beforePrime = 0;
        for(int i = left; i <= right; i++){
            if(!isPrime[i]){
                continue;    
            }
            if(ans.size() < 2){
                ans.push_back(i);
                beforePrime = i;
                continue;
            }
            else{
                if((ans[1] - ans[0]) > (i - beforePrime)){
                    ans[0] = beforePrime;
                    ans[1] = i;
                }
            }
            beforePrime = i;
        }
        if(ans.size() == 2) return ans;
        return {-1, -1};
    }
};

Leetcode Problem:

• Find Missing and Repeated Values

Summary

• Find the repeating and missing numbers in a 2D grid.

Approach

• Use a boolean array to track the presence of each number in the grid, then iterate through the array to find the repeating and missing numbers.

Complexity

• O(n^2) where n is the size of the grid

Explanation

• The solution first initializes a boolean array 'appear' of size n*n+1 to track the presence of each number
• It then iterates through the grid, setting the corresponding index in the 'appear' array to true for each number
• After that, it iterates through the 'appear' array and adds the index that is still false to the result vector
• This process finds the missing number
• The repeating number is found by iterating through the grid and adding the number to the result vector if it is already set to true in the 'appear' array.

Solution Code:

class Solution {
public:
    bool appear[2501] = {false,};
    vector findMissingAndRepeatedValues(vector>& grid) {
        int N = grid.size();
        vector ans;
        for(int i = 0 ; i < N; i++){
            for(int j = 0 ; j < N; j++){
                if(appear[grid[i][j]]){
                    ans.push_back(grid[i][j]);
                }
                appear[grid[i][j]] = true;
            }
        }
        for(int i = 1 ; i <= N*N; i++){
            if(!appear[i]){
                ans.push_back(i);
                return ans;
            }

        }
        return ans;
    }
};

Leetcode Problem:

• Count Total Number of Colored Cells

Summary

• Calculating the number of colored cells in a grid after n minutes

Approach

• The approach used is to calculate the number of colored cells in each minute and sum them up
• The number of colored cells in each minute is calculated as 2 times the number of odd-numbered cells that have not been colored yet
• The odd-numbered cells are calculated using the formula i * 2 + 1, where i is the current minute
• The initial number of odd-numbered cells is (i - 1) * 2 + 1, where i is 1
• The sum of colored cells in each minute is added to the total sum.

Complexity

• O(n)

Explanation

• The time complexity of the solution is O(n) because the solution iterates over each minute from 1 to n
• The space complexity is O(1) because the solution only uses a constant amount of space to store the variables i, odd, and sum.

Solution Code:

class Solution {
public:
    long long coloredCells(int n) {
        int i = 1;
        int odd = (i - 1) * 2 + 1;
        long long sum = 0;
        for( ; i < n; i++){
            sum += odd*2;
            odd = i * 2 + 1;
        }
        return sum + odd;
    }
};

Leetcode Problem:

• Shortest Common Supersequence

Summary

• Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences.

Approach

• The approach used is dynamic programming
• We first create a 2D array dp where dp[i][j] represents the length of the shortest common supersequence of the first i characters of str1 and the first j characters of str2
• Then we construct the shortest common supersequence by tracing back the dp array.

Complexity

• O(n*m) where n and m are the lengths of str1 and str2 respectively.

Explanation

• The solution first initializes a 2D array dp of size (n+1) x (m+1) where n and m are the lengths of str1 and str2 respectively
• It then fills up the dp array using dynamic programming
• For each cell dp[i][j], if the current characters in str1 and str2 are the same, it increments the value by 1
• Otherwise, it takes the maximum value from the top and left cells
• After filling up the dp array, it constructs the shortest common supersequence by tracing back the dp array
• Finally, it appends any remaining characters from str1 and str2 to the supersequence.

Solution Code:

class Solution {
public:
    int dp[1001][1001];
    string shortestCommonSupersequence(string str1, string str2) {
        int cnt1 = 0;
        for(int i = 0 ; i < str1.size(); i++){
            for(int j = 0 ; j < str2.size(); j++){
                if(str1[i] == str2[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                } else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
        string s = "";
        int i = str1.size();
        int j = str2.size();
        while(i > 0 && j > 0){
            if(dp[i][j] == dp[i][j-1]){
                j--;
            } else if(dp[i][j] == dp[i-1][j]){
                i--;
            } else{
                s += str1[i-1];
                i--;
                j--;
            }
        }
        reverse(s.begin(), s.end());
        string res = "";
        int idx1 = 0;
        int idx2 = 0;
        for(int i = 0; i < s.size(); i++){
            while(str1[idx1] != s[i]){
                res += str1[idx1];
                idx1++;
            }
            while(str2[idx2] != s[i]){
                res += str2[idx2];
                idx2++;
            }
            res += s[i];
            idx1++;
            idx2++;
        }
        while(idx1 < str1.size()){
            res += str1[idx1++];
        }
        while(idx2 < str2.size()){
            res += str2[idx2++];
        }

        return res;
    }
};

Leetcode Problem:

• Make Lexicographically Smallest Array by Swapping Elements

Summary

• Given a 0-indexed array of positive integers and a positive integer limit, return the lexicographically smallest array that can be obtained by swapping any two indices if the absolute difference between the two elements is less than or equal to the limit.

Approach

• The solution uses a greedy approach to group the elements into subarrays based on their values
• It first sorts the array and then iterates through the sorted array to create subarrays
• Each subarray contains elements that are within the limit of each other
• Finally, it replaces each element in the original array with the smallest element in its corresponding subarray.

Complexity

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

Solution Code:

class Solution {
public:
    vector lexicographicallySmallestArray(vector& nums, int limit) {
        vector> groups;
        unordered_map valToGrp;
        int numIdx = 0;
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            nums2.push_back(nums[i]);
        }
        sort(nums2.begin(), nums2.end());
        while(numIdx < nums2.size()){
            groups.push_back(vector ());
            long long minv = nums2[numIdx];
            long long maxv = nums2[numIdx];
            while(minv - limit <= nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                groups.back().push_back(nums2[numIdx]);
                valToGrp[nums2[numIdx]] = groups.size() - 1;
                numIdx++;
                if(numIdx >= nums2.size()) break;
                if(minv > nums2[numIdx] && nums2[numIdx] >= minv - limit){
                    minv = nums2[numIdx];
                }
                if(maxv < nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                    maxv = nums2[numIdx];
                }
            }
        }
        unordered_map groupIdx;
        for(int i = 0 ; i < nums.size(); i++){
            int idx = valToGrp[nums[i]];
            nums[i] = groups[idx][groupIdx[idx]];
            groupIdx[idx]++;
        }
        return nums;
    }
};