'2025/02 글 목록 (14 Page)

Find the Number of Distinct Colors Among the Balls

알고리즘 2025. 2. 7. 23:35

Leetcode Problem:
Find the Number of Distinct Colors Among the Balls

Summary

Given a limit and a 2D array of queries, find the number of distinct colors among the balls after each query.

Approach

The solution uses two unordered maps to keep track of the color count and the current color of each ball
It iterates over the queries, updating the color count and current color of each ball, and pushes the number of distinct colors to the result vector.

Complexity

O(n), where n is the number of queries

Explain

The solution starts by initializing two unordered maps, colorCnt to store the count of each color and curColor to store the current color of each ball
It also initializes a variable colornum to store the number of distinct colors
Then, it iterates over the queries, updating the color count and current color of each ball
If the current color of a ball is the same as its query color, it pushes the current number of distinct colors to the result vector and continues to the next query
If the current color of a ball is not the same as its query color, it decrements the count of the current color and increments the count of the query color
Finally, it pushes the updated number of distinct colors to the result vector.

Solution Code:


class Solution {
public:
    vector queryResults(int limit, vector>& queries) {
        unordered_map colorCnt;
        unordered_map curColor;
        vector ans;
        int colornum = 0;
        for(int i = 0 ; i < queries.size(); i++){
            int idx = queries[i][0];
            int color = queries[i][1];
            if(curColor[idx] == color){
                ans.push_back(colornum);
                continue;
            }
            if (colorCnt[curColor[idx]] > 0){
                colorCnt[curColor[idx]]--;
                if(colorCnt[curColor[idx]] == 0){
                    colornum--;
                }
            }
            if(colorCnt[color] == 0){
                colornum++;
            }
            curColor[idx] = color;
            colorCnt[color]++;
             
            ans.push_back(colornum);
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Number of Days to Disconnect Island (0)	2025.02.09
Regions Cut By Slashes (0)	2025.02.09
Tuple with Same Product (0)	2025.02.07
Check if One String Swap Can Make Strings Equal (0)	2025.02.05
Magic Squares In Grid (1)	2025.02.05

짬뽕얼큰하게

,

Tuple with Same Product

알고리즘 2025. 2. 7. 00:14

Leetcode Problem:
Tuple with Same Product

Summary

Given an array of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where a, b, c, and d are elements of the array and a!= b!= c!= d.

Approach

The approach used is to first filter out duplicate numbers from the input array
Then, for each pair of numbers in the filtered array, calculate their product and store them in a vector
Finally, count the number of tuples that have the same product by iterating over the vector and using a variable to keep track of the current product and the count of tuples with the same product.

Complexity

O(n^2 log n) where n is the length of the input array

Explain

The code first initializes a boolean array to keep track of duplicate numbers
It then iterates over the input array and pushes each number into the boolean array if it's not already present
This step is necessary to filter out duplicate numbers
After that, the code sorts the filtered array and iterates over it to calculate the products of each pair of numbers
The products are stored in a vector
Finally, the code counts the number of tuples that have the same product by iterating over the vector and using a variable to keep track of the current product and the count of tuples with the same product
The time complexity of this approach is O(n^2 log n) due to the sorting step.

Solution Code:


class Solution {
public:
    bool num[10001];
    int tupleSameProduct(vector& nums) {
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            if(num[nums[i]]){
                continue;
            }
            nums2.push_back(nums[i]);
            num[nums[i]] = true;
        }
        sort(nums2.begin(), nums2.end());
        vector nums3;
        for(int i = 0 ; i < nums2.size(); i++){
            for(int j = i+1 ; j < nums2.size(); j++){
                nums3.push_back(nums2[i] * nums2[j]);
            }
        }
        int ans = 0;
        sort(nums3.begin(), nums3.end());
        int cnt = 1;
        int cur = nums3[0];
        for(int i = 1 ; i < nums3.size();i++){
            cout << nums3[i] << endl;
            if(cur != nums3[i]){
                if(cnt >= 2){
                    ans += (cnt * (cnt - 1))/2 * 8;
                }
                cnt = 0;
            }
            cnt++;
            cur = nums3[i];
        }
        if(cnt >= 2){
            ans += (cnt * (cnt - 1))/2 * 8;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Regions Cut By Slashes (0)	2025.02.09
Find the Number of Distinct Colors Among the Balls (0)	2025.02.07
Check if One String Swap Can Make Strings Equal (0)	2025.02.05
Magic Squares In Grid (1)	2025.02.05
Spiral Matrix III (0)	2025.02.05

짬뽕얼큰하게

,

Check if One String Swap Can Make Strings Equal

알고리즘 2025. 2. 5. 21:35

Leetcode Problem:
Check if One String Swap Can Make Strings Equal

Summary

Given two strings of equal length, determine if it is possible to make both strings equal by performing at most one string swap on exactly one of the strings.

Approach

This solution works by first finding all the indices where the two strings differ
If there are no differences, the strings are already equal, so the function returns true
If there are exactly two differences, the function checks if swapping the characters at these indices would result in equal strings
If so, the function returns true; otherwise, it returns false.

Complexity

O(n), where n is the length of the input strings, because the solution makes a single pass through the strings to find the differences.

Explain

The solution uses a vector to store the indices where the two strings differ
It then checks if there are exactly two differences
If so, it checks if swapping the characters at these indices would result in equal strings by comparing the characters at the two indices in both strings
If the characters are the same, the function returns true; otherwise, it returns false.

Solution Code:


class Solution {
public:
    vector diffIdx;
    bool areAlmostEqual(string s1, string s2) {
        for(int i = 0 ; i < s1.size(); i++){
            if(s1[i] != s2[i]){
                diffIdx.push_back(i);
            }
        }
        if(diffIdx.size() == 0) return true;
        if(diffIdx.size() != 2) return false;
        if(s1[diffIdx[0]] != s2[diffIdx[1]]){
            return false;
        }
        if(s1[diffIdx[1]] != s2[diffIdx[0]]){
            return false;
        }
        return true;
    }
};

'알고리즘' 카테고리의 다른 글

Find the Number of Distinct Colors Among the Balls (0)	2025.02.07
Tuple with Same Product (0)	2025.02.07
Magic Squares In Grid (1)	2025.02.05
Spiral Matrix III (0)	2025.02.05
Integer to English Words (0)	2025.02.05

짬뽕얼큰하게

,

Magic Squares In Grid

알고리즘 2025. 2. 5. 08:50

Leetcode Problem:
Magic Squares In Grid

Summary

Count the number of 3x3 magic square subgrids in a given grid.

Approach

The approach used is to iterate over the grid and for each possible 3x3 subgrid, check if it is a magic square by verifying the sums of rows, columns, and diagonals
If all conditions are met, increment the counter.

Complexity

O(R*C*(R*C)) where R is the number of rows and C is the number of columns in the grid.

Explain

The solution iterates over the grid and checks each 3x3 subgrid
For each subgrid, it checks if all numbers are distinct and within the range 1-9
Then, it calculates the sums of rows, columns, and diagonals and checks if they are all equal
If all conditions are met, it increments the counter
The time complexity is O(R*C*(R*C)) due to the nested loops and calculations.

Solution Code:


class Solution {
public:
    int numMagicSquaresInside(vector>& grid) {
        int ans = 0;
        if (grid.size() < 3 || grid[0].size() < 3) return 0;
        for(int i = 0 ; i < grid.size() - 2; i++){
            for(int j = 0 ; j < grid[i].size() - 2; j++){
                int cnt = 0;
                int sum = 0;
                bool visited[10] = {false};
                for(int r =i; r < i + 3; r++){
                    for(int c = j; c < j + 3; c++){
                        if(grid[r][c] < 1 || grid[r][c] >= 10 || visited[grid[r][c]]) break;
                        cnt++;
                        visited[grid[r][c]] = true;
                    }
                }
                int sumArr[8] = {0};
                if (cnt == 9){
                    for(int k = 0 ; k < 3; k++){
                        sumArr[0] += grid[i][j+k];
                        sumArr[1] += grid[i+1][j+k];
                        sumArr[2] += grid[i+2][j+k];
                        sumArr[3] += grid[i+k][j];
                        sumArr[4] += grid[i+k][j+1];
                        sumArr[5] += grid[i+k][j+2];
                        sumArr[6] += grid[i+k][j+k];
                        sumArr[7] += grid[i+k][j+2-k];
                    }
                    bool isMagicGrid = true;
                    for(int k = 1 ; k < 8; k++){
                        if (sumArr[k] != sumArr[0]){
                            isMagicGrid = false;
                            break;
                        }
                    }
                    if (isMagicGrid){
                        ans++;
                    }
                }
            }
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Tuple with Same Product (0)	2025.02.07
Check if One String Swap Can Make Strings Equal (0)	2025.02.05
Spiral Matrix III (0)	2025.02.05
Integer to English Words (0)	2025.02.05
Minimum Number of Pushes to Type Word II (0)	2025.02.05

짬뽕얼큰하게

,

Spiral Matrix III

알고리즘 2025. 2. 5. 08:47

Leetcode Problem:
Spiral Matrix III

Summary

Find the positions of a 2D grid in a clockwise spiral shape.

Approach

The solution uses a while loop to traverse the grid in a clockwise spiral shape
It starts at the given start position and moves in a direction (right, down, left, up) for a specified number of steps
The direction is updated after each step, and the position is added to the result list if it is within the grid boundaries.

Complexity

O(rows * cols)

Explain

The solution uses four arrays `dy` and `dx` to represent the possible directions (up, down, left, right) in the grid
The `ans_cnt` variable keeps track of the number of positions visited, and the `cnt` variable keeps track of the number of steps in the current direction
The `dir` variable keeps track of the current direction
The solution uses a while loop to traverse the grid, and it adds the current position to the result list if it is within the grid boundaries.

Solution Code:


class Solution {
public:
    vector> spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        vector> ans;
        int dy[] = {0, 1, 0, -1};
        int dx[] = {1, 0, -1, 0};
        int ans_cnt = 0;
        int cnt = 1;
        int dir = 0;
        ans.push_back({rStart, cStart});
        ans_cnt++;
        while(ans_cnt < rows * cols){
            for(int i = 0 ; i < 2; i++){
                for(int j = 0 ; j < cnt; j++){
                    rStart += dy[dir];
                    cStart += dx[dir];
                    if (rStart < 0 || rStart >= rows || cStart < 0 || cStart >= cols){
                        continue;
                    }
                    ans.push_back({rStart, cStart});
                    ans_cnt++;
                }
                dir = (dir + 1) % 4;
            }
            cnt++;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Check if One String Swap Can Make Strings Equal (0)	2025.02.05
Magic Squares In Grid (1)	2025.02.05
Integer to English Words (0)	2025.02.05
Minimum Number of Pushes to Type Word II (0)	2025.02.05
Kth Distinct String in an Array (0)	2025.02.05

짬뽕얼큰하게

,

Integer to English Words

알고리즘 2025. 2. 5. 08:43

Leetcode Problem:
Integer to English Words

Summary

Convert a non-negative integer to its English words representation.

Approach

The approach used is to recursively break down the number into smaller parts (thousands, millions, billions) and then convert each part to words using a combination of arrays and helper functions.

Complexity

O(log n) where n is the number of digits in the input number

Explain

The solution code uses three arrays to store the words for thousands, millions, and billions
It also uses a helper function `getUnderHndred` to convert numbers less than 100 to words
The `numberToWords` function recursively breaks down the input number into smaller parts and then combines the words for each part to form the final result.

Solution Code:


class Solution {
public:
    string digitOf1000[5] = {
        "",
        " Thousand",
        " Million",
        " Billion"

    };
    string digitOf10[11] = {
        "",
        " Ten",
        " Twenty",
        " Thirty",
        " Forty",
        " Fifty",
        " Sixty",
        " Seventy",
        " Eighty",
        " Ninety"
    };
    string underTwenty[21] = {
        "",
        " One",
        " Two",
        " Three",
        " Four",
        " Five",
        " Six",
        " Seven",
        " Eight",
        " Nine",
        " Ten",
        " Eleven",
        " Twelve",
        " Thirteen",
        " Fourteen",
        " Fifteen",
        " Sixteen",
        " Seventeen",
        " Eighteen",
        " Nineteen"
    };
    string getUnderHndred(int num){
        if (num < 20){
            return underTwenty[num];
        }
        string s = "";
        if (num / 10 > 0){
            s += digitOf10[num/10];
        }
        if (num %10 > 0){
            s += underTwenty[num % 10];
        }
        return s;
    }

    string numberToWords(int num) {
        string res = "";
        int cnt = 0;
        if (num == 0) return "Zero";
        while(num){
            string s = "";
            int num2 = (num % 1000);
            if ( num2 / 100){
                s += underTwenty[num2/100] + " Hundred";
            }
            s += getUnderHndred(num2 % 100);
            if (s.compare("") != 0)
                res = s + digitOf1000[cnt] + res;
            num /= 1000;
            cnt++;
        }
        return res.substr(1);
    }
};

'알고리즘' 카테고리의 다른 글

Magic Squares In Grid (1)	2025.02.05
Spiral Matrix III (0)	2025.02.05
Minimum Number of Pushes to Type Word II (0)	2025.02.05
Kth Distinct String in an Array (0)	2025.02.05
Maximum Ascending Subarray Sum (0)	2025.02.04

짬뽕얼큰하게

,

Minimum Number of Pushes to Type Word II

알고리즘 2025. 2. 5. 08:40

Leetcode Problem:
Minimum Number of Pushes to Type Word II

Summary

Given a string of lowercase English letters, find the minimum number of times the keys will be pushed to type the string after remapping the keys on a telephone keypad.

Approach

The approach used is to first count the frequency of each letter in the string, then sort the letters based on their frequency and map them to the keys in a way that minimizes the number of pushes required.

Complexity

O(n log n) where n is the number of unique letters in the string

Explain

The code first counts the frequency of each letter in the string using an array `word_cnt`
Then it sorts the letters based on their frequency using a merge sort algorithm
After sorting, it maps the letters to the keys in a way that minimizes the number of pushes required
The `merge` function is used to merge two sorted subarrays into a single sorted subarray
The `merge_sort` function is used to recursively sort the letters
The `minimumPushes` function is the main function that calculates the minimum number of pushes required.

Solution Code:


class Solution {
public:
    int word_cnt[26];
    int sortedAlphabet[26];
    int tmp[26];
    void merge(int l, int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        while(i <= mid && j <= r){
            if(word_cnt[sortedAlphabet[i]] > word_cnt[sortedAlphabet[j]]){
                tmp[cur++] = sortedAlphabet[i++];
            } else {
                tmp[cur++] = sortedAlphabet[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = sortedAlphabet[i++];
        }
        for(i = l; i < cur; i++){
            sortedAlphabet[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);
    }
    int minimumPushes(string word) {
        int min_cnt = 0;
        for(int i = 0 ; i < word.size(); i++){
            word_cnt[word[i] - 'a']++;
        }
        for(int i = 0 ; i < 26; i++){
            sortedAlphabet[i] = i;
        }
        merge_sort(0, 25);
        int buttonCnt = 0;
        int ans = 0;
        for(int i = 0 ; i < 26; i++){
            int c = sortedAlphabet[i];
            if (word_cnt[c] == 0) break;
            int click_cnt = buttonCnt / 8 + 1;
            ans += click_cnt*word_cnt[c];
            buttonCnt++;
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Spiral Matrix III (0)	2025.02.05
Integer to English Words (0)	2025.02.05
Kth Distinct String in an Array (0)	2025.02.05
Maximum Ascending Subarray Sum (0)	2025.02.04
Range Sum of Sorted Subarray Sums (0)	2025.02.04

짬뽕얼큰하게

,

Kth Distinct String in an Array

알고리즘 2025. 2. 5. 08:37

Leetcode Problem:
Kth Distinct String in an Array

Summary

Given an array of strings and an integer k, return the kth distinct string present in the array
If there are fewer than k distinct strings, return an empty string.

Approach

The approach used is to count the frequency of each string in the array using an unordered map
Then, iterate through the array again to find the kth distinct string
If k is greater than the number of distinct strings, return an empty string.

Complexity

O(n + m) where n is the size of the array and m is the number of distinct strings

Explain

First, we create an unordered map to store the frequency of each string in the array
We then initialize a counter K to keep track of the number of distinct strings
We iterate through the array again, and for each string, we check if its frequency is 1
If it is, we increment the counter K
If K equals k, we return the current string
If we finish iterating through the array and K is still less than k, we return an empty string.

Solution Code:


class Solution {
public:
    string kthDistinct(vector& arr, int k) {
        unordered_map m;
        for(int i = 0 ; i < arr.size(); i++){
            m[arr[i]]++;
        }
        int K = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(m[arr[i]] == 1){
                K++;
                if(k == K) return arr[i];
            }
        }
        return "";
    }
};

'알고리즘' 카테고리의 다른 글

Integer to English Words (0)	2025.02.05
Minimum Number of Pushes to Type Word II (0)	2025.02.05
Maximum Ascending Subarray Sum (0)	2025.02.04
Range Sum of Sorted Subarray Sums (0)	2025.02.04
Number of Senior Citizens (0)	2025.02.04

짬뽕얼큰하게

,

Maximum Ascending Subarray Sum

알고리즘 2025. 2. 4. 23:50

Leetcode Problem:
Maximum Ascending Subarray Sum

Summary

Find the maximum possible sum of an ascending subarray in a given array of positive integers.

Approach

The approach used is to initialize variables to store the maximum sum and the current sum of the ascending subarray
Then, iterate over the array from the second element to the last element
If the current element is less than or equal to the previous element, reset the current sum to 0
Otherwise, add the current element to the current sum and update the maximum sum if necessary.

Complexity

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

Explain

The provided solution uses Kadane's algorithm with a twist to find the maximum ascending subarray sum
It initializes variables `ans` and `sum` to store the maximum sum and the current sum of the ascending subarray, respectively
Then, it iterates over the array from the second element to the last element
If the current element is less than or equal to the previous element, it resets the current sum to 0
Otherwise, it adds the current element to the current sum and updates the maximum sum if necessary
The time complexity of this solution is O(n), where n is the number of elements in the array.

Solution Code:


class Solution {
public:
    vector st;
    int maxAscendingSum(vector& nums) {
        int ans = nums[0];
        int sum = nums[0];
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] <= nums[i-1]){
                sum = 0;
            }
            sum += nums[i];
            ans = max(ans, sum);
        }
        return ans;
    }
};

'알고리즘' 카테고리의 다른 글

Minimum Number of Pushes to Type Word II (0)	2025.02.05
Kth Distinct String in an Array (0)	2025.02.05
Range Sum of Sorted Subarray Sums (0)	2025.02.04
Number of Senior Citizens (0)	2025.02.04
Filling Bookcase Shelves (0)	2025.02.04

짬뽕얼큰하게

,

Range Sum of Sorted Subarray Sums

알고리즘 2025. 2. 4. 09:08

Leetcode Problem:
Range Sum of Sorted Subarray Sums

Summary

Given an array of positive integers, compute the sum of all non-empty continuous subarrays, sort them, and return the sum of a specific range in the new array.

Approach

The approach is to first compute the sum of all non-empty continuous subarrays, then sort them, and finally return the sum of the numbers in the specified range in the sorted array.

Complexity

O(n^2 log n) due to sorting, where n is the number of elements in the input array.

Explain

The solution code first initializes an empty array to store the subarray sums and a variable to store the sum of the current subarray
It then iterates over the input array, adding each number to the current sum and pushing the sum to the array
After each number is added, it also computes the sum of all possible subarrays starting from the current number and pushes these sums to the array
Finally, it sorts the array and computes the sum of the numbers in the specified range.

Solution Code:


#define MOD 1000000007
class Solution {
public:
    int rangeSum(vector& nums, int n, int left, int right) {
        vector arr;
        long long sum = 0;
        for(int i = 0 ; i < nums.size(); i++){
            sum += nums[i];
            sum %= MOD;
            arr.push_back(sum);
            long long sum2 = 0;
            for(int j = i+1 ; j < nums.size(); j++){
                sum2 += nums[j];
                sum2 %= MOD;
                arr.push_back(sum2);
            }
        }
        sort(arr.begin(), arr.end());
        long long sum3 = 0;
        for(int i = left -1; i < right; i++){
            sum3 += arr[i];
            sum3 %= MOD;
        }
        return sum3;
    }
};

'알고리즘' 카테고리의 다른 글

Kth Distinct String in an Array (0)	2025.02.05
Maximum Ascending Subarray Sum (0)	2025.02.04
Number of Senior Citizens (0)	2025.02.04
Filling Bookcase Shelves (0)	2025.02.04
Minimum Deletions to Make String Balanced (0)	2025.02.04

짬뽕얼큰하게

,

일	월	화	수	목	금	토
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28

'2025/02'에 해당되는 글 176건

Leetcode Problem: Find the Number of Distinct Colors Among the Balls

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Tuple with Same Product

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Check if One String Swap Can Make Strings Equal

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Magic Squares In Grid

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Spiral Matrix III

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Integer to English Words

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Minimum Number of Pushes to Type Word II

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Kth Distinct String in an Array

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Maximum Ascending Subarray Sum

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

Leetcode Problem: Range Sum of Sorted Subarray Sums

Summary

Approach

Complexity

Explain

Solution Code:

'알고리즘' 카테고리의 다른 글

공지사항

카테고리

태그목록

글 보관함

달력

링크

짬뽕얼큰하게

LATEST FROM OUR BLOG

LATEST COMMENTS

Leetcode Problem:
Find the Number of Distinct Colors Among the Balls

Leetcode Problem:
Tuple with Same Product

Leetcode Problem:
Check if One String Swap Can Make Strings Equal

Leetcode Problem:
Magic Squares In Grid

Leetcode Problem:
Spiral Matrix III

Leetcode Problem:
Integer to English Words

Leetcode Problem:
Minimum Number of Pushes to Type Word II

Leetcode Problem:
Kth Distinct String in an Array

Leetcode Problem:
Maximum Ascending Subarray Sum

Leetcode Problem:
Range Sum of Sorted Subarray Sums