짬뽕얼큰하게의 맨땅에 헤딩 :: '2025/02/04 글 목록

Maximum Ascending Subarray Sum

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

Leetcode Problem:

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:

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
블로그 이미지

짬뽕얼큰하게

,

Number of Senior Citizens

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

Leetcode Problem:

Summary

  • The problem requires to count the number of passengers who are strictly more than 60 years old based on their details.

Approach

  • The approach used is to iterate over the details array and check the age of each passenger by comparing the 11th character (gender) and 12th character (age) with the condition
  • If the gender is 'M' or 'O' and the age is greater than 60, or if the gender is 'F' and the age is 60 or greater, then the passenger is counted as a senior.

Complexity

  • O(n) where n is the number of passengers, as we are iterating over the details array once.

Explain

  • Here's a step-by-step explanation of the solution code: 1
  • Initialize a variable `ans` to store the count of seniors. 2
  • Iterate over the `details` array using a for loop. 3
  • Inside the loop, check the age of the current passenger by comparing the 11th character (gender) and 12th character (age) with the condition. 4
  • If the gender is 'M' or 'O' and the age is greater than 60, or if the gender is 'F' and the age is 60 or greater, then increment the `ans` variable. 5
  • Return the final count of seniors after iterating over the entire array.

Solution Code:


class Solution {
public:
    int countSeniors(vector& details) {
        int ans = 0;
        for(int i = 0 ; i < details.size(); i++){
            if(details[i][11] > '6'){
                ans++;
            } else if(details[i][11] =='6' && details[i][12] > '0'){
                ans++;
            }
        }
        return ans;
    }
};

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

Maximum Ascending Subarray Sum  (0) 2025.02.04
Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Filling Bookcase Shelves  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Filling Bookcase Shelves

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

Leetcode Problem:

Summary

  • The problem is to find the minimum possible height of a bookcase with given shelf width and a list of books, where each book has a thickness and a height.

Approach

  • Dynamic programming is used to solve this problem
  • The approach is to calculate the minimum possible height for each book and each shelf, and then choose the minimum height at each step.

Complexity

  • The time complexity of this solution is O(N^2), where N is the number of books
  • This is because there are two nested loops in the solution code.

Explain

  • The solution code uses a dynamic programming approach to solve the problem
  • It initializes an array dp of size 1001 to store the minimum possible height for each book and each shelf
  • Then, it iterates over each book and each shelf, and for each shelf, it calculates the minimum possible height by considering all possible combinations of books on the shelf
  • Finally, it returns the minimum possible height for the last book and the last shelf.

Solution Code:


class Solution {
public:
    int dp[1001];
    int minHeightShelves(vector>& books, int shelfWidth) {
        int N = books.size();
        for(int i = 1; i <= N; i++){
            int width = books[i-1][0];
            int height = books[i-1][1];
            dp[i] = dp[i-1] + height;
            for(int j = i -1; j > 0; j--){
                height = max(height, books[j-1][1]);
                width += books[j-1][0];
                if (width > shelfWidth) break;
                dp[i] = min(dp[j-1] + height, dp[i]);
            }
        }
        return dp[N];
    }
};

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

Range Sum of Sorted Subarray Sums  (0) 2025.02.04
Number of Senior Citizens  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Minimum Deletions to Make String Balanced

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

Leetcode Problem:

Summary

  • Find the minimum number of deletions needed to make a string of 'a's and 'b's balanced.

Approach

  • Use a greedy approach to count the minimum number of deletions
  • Iterate through the string, incrementing the count of 'b's and decrementing the count of 'a's when a 'b' is encountered after an 'a'
  • The number of deletions is the minimum between the current count of 'b's and 0.

Complexity

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

Explain

  • The provided C++ code initializes a variable to store the minimum number of deletions and another variable to count the number of 'b's encountered so far
  • It then iterates through the string, incrementing the 'b' count when a 'b' is encountered and decrementing the 'a' count when a 'b' is encountered after an 'a'
  • The number of deletions is the minimum between the current 'b' count and 0
  • This approach ensures that the minimum number of deletions is achieved by deleting the maximum number of 'a's after a 'b' has been encountered.

Solution Code:


class Solution {
public:
    int minimumDeletions(string s) {
        int ans = 0;
        int b_cnt = 0;
        for(int i = 0 ; i < s.size(); i++){
            if(s[i] == 'b'){
                b_cnt++;
            } else if (b_cnt > 0 && s[i] == 'a'){
                ans++;
                b_cnt--;
            }
        }
        return ans;
    }
};

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

Number of Senior Citizens  (0) 2025.02.04
Filling Bookcase Shelves  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Count Number of Teams

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

Leetcode Problem:

Summary

  • Count the number of teams that can be formed from a list of unique ratings.

Approach

  • The solution uses a two-pointer technique to count the number of teams that can be formed
  • It iterates over the list of ratings, and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating
  • The number of teams that can be formed with the current rating is then calculated by multiplying the number of ratings to its left and right that are less than and greater than the current rating, respectively
  • The total number of teams is then calculated by summing up the number of teams that can be formed for each rating.

Complexity

  • O(N^2) where N is the number of ratings.

Explain

  • The solution iterates over the list of ratings and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating
  • The number of teams that can be formed with the current rating is then calculated by multiplying the number of ratings to its left and right that are less than and greater than the current rating, respectively
  • The total number of teams is then calculated by summing up the number of teams that can be formed for each rating
  • This approach ensures that each rating is counted multiple times, but it is necessary to count the number of teams that can be formed for each rating
  • The time complexity of the solution is O(N^2) because the solution iterates over the list of ratings and for each rating, it counts the number of ratings to its left and right that are less than and greater than the current rating.

Solution Code:


class Solution {
public:
    int ans = 0;
    int numTeams(vector& rating) {
        int N = rating.size();
        for(int i = 1; i < N - 1; i++){
            int leftCnt1 = 0;
            int leftCnt2 = 0;
            int idx = i - 1;
            while(idx >= 0){
                if(rating[idx] < rating[i]){
                    leftCnt1++;
                }
                if(rating[idx] > rating[i]){
                    leftCnt2++;
                }
                idx--;
            }
            int rightCnt1 = 0;
            int rightCnt2 = 0;
            idx = i + 1;
            while(idx < N){
                if(rating[i] < rating[idx]){
                    rightCnt1++;
                }
                if(rating[i] > rating[idx]){
                    rightCnt2++;
                }
                idx++;
            }
            ans += leftCnt1 * rightCnt1;
            ans += leftCnt2 * rightCnt2;
        }
        return ans;
    }
};

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

Filling Bookcase Shelves  (0) 2025.02.04
Minimum Deletions to Make String Balanced  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
Find the City With the Smallest Number of Neighbors at a Threshold Distance  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Second Minimum Time to Reach Destination

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

Leetcode Problem:

Summary

  • The problem is to find the second minimum time it will take to go from vertex 1 to vertex n in a bi-directional connected graph with n vertices, given the edges, time, and change.

Approach

  • The approach used is to use a priority queue to keep track of the nodes to visit, and a visited array to keep track of the nodes that have been visited
  • The time complexity is O(n log n) due to the use of the priority queue.

Complexity

  • O(n log n)

Explain

  • The solution code uses a priority queue to keep track of the nodes to visit, and a visited array to keep track of the nodes that have been visited
  • The time complexity is O(n log n) due to the use of the priority queue
  • The code first initializes the priority queue with the first node (1) and its time (0)
  • Then, it enters a loop where it pops the node with the minimum time from the priority queue, and for each of its neighbors that have not been visited before, it adds them to the priority queue with their updated time
  • The loop continues until all nodes have been visited
  • Finally, it returns the minimum time that has been visited at least twice, which is the second minimum time.

Solution Code:


struct NODE {
    int num;
    int time;

    bool operator <(NODE &b){
        return time < b.time;
    }
};

template 
struct _heap{
    int size;
    T arr[80001];
    _heap(){
        size = 1;
    }
    bool cmp(T a, T b){
        return a < b;
    }
    bool empty(){
        return size == 1;
    }
    void push(T a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && cmp(arr[idx], arr[idx/2])){
            T tmp = arr[idx];
            tmp = arr[idx/2];
            arr[idx/2] = tmp;
            idx /= 2;
        }
    }
    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+1], arr[j])){
                j++;
            }
            if (cmp(arr[j], arr[i])){
                T tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i = j;
            } else{
                break;
            }
        }

        return ret;
    }
};

class Solution {
public:
    _heap h;
    vector visited[10001];
    vector adj[10001];
    int secondMinimum(int n, vector>& edges, int time, int change) {
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        visited[1].push_back(0);
        for(int i = 0 ; i < adj[1].size(); i++){
            int v = adj[1][i];
            h.push({v, time});
            visited[v].push_back(time);
        }
        int minCost = 1234567890;
        int minSecondCost = 1234567890;

        while(!h.empty()){
            NODE a = h.pop();
            if (a.num == n && a.time < minCost){
                minSecondCost = minCost;
                minCost = a.time;
            }
            if (a.num == n && a.time > minCost && minSecondCost > a.time){
                minSecondCost = a.time;
            }
            for(int i = 0 ; i < adj[a.num].size(); i++){
                int next = adj[a.num][i];
                if (visited[next].size() >= 2){
                    continue;
                }
                int cost = 0;
                if ((a.time / change)%2){
                    cost = (change - (a.time%change)) + a.time + time;
                } else {
                    cost = a.time + time;
                }

                if(visited[next].size() == 0){
                    visited[next].push_back(cost);
                } else{
                    if (visited[next][0] == cost){
                        continue;
                    }
                    visited[next].push_back(cost);
                }
                h.push({next, cost});
            }
        }
        return minSecondCost;
    }
};

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

Minimum Deletions to Make String Balanced  (0) 2025.02.04
Count Number of Teams  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
Find the City With the Smallest Number of Neighbors at a Threshold Distance  (0) 2025.02.04
Sort an Array  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Minimum Cost to Convert String I

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

Leetcode Problem:

Summary

  • Given two strings source and target, and two character arrays original and changed, find the minimum cost to convert source to target using any number of operations.

Approach

  • Dynamic programming is used to find the minimum cost
  • The cost of changing each character in source to the corresponding character in target is calculated and stored in a 2D array minCost
  • Then, the minimum cost of changing each character in source to any character in target is calculated using the Floyd-Warshall algorithm
  • Finally, the minimum cost to convert source to target is calculated by summing up the minimum cost of changing each character in source to the corresponding character in target.

Complexity

  • O(n^3), where n is the length of the strings source and target.

Explain

  • The solution first initializes a 2D array minCost with all elements set to 1234567890
  • Then, it calculates the minimum cost of changing each character in source to the corresponding character in target and stores it in minCost
  • After that, it uses the Floyd-Warshall algorithm to calculate the minimum cost of changing each character in source to any character in target
  • Finally, it calculates the minimum cost to convert source to target by summing up the minimum cost of changing each character in source to the corresponding character in target.

Solution Code:


class Solution {
public:
    long long minCost[26][26];
    long long minimumCost(string source, string target, vector& original, vector& changed, vector& cost) {
        for(int i = 0; i < 26; i++){
            for(int j = 0 ; j < 26; j++){
                minCost[i][j] = 1234567890;
            }
        }

        for(int i = 0 ; i < original.size(); i++){
            int a = original[i] -'a';
            int b = changed[i] - 'a';
            if (minCost[a][b] > cost[i]){
                minCost[a][b] = cost[i];
            }
        }

        for(int k = 0 ; k < 26; k++){
            for(int i = 0 ; i < 26; i++){
                if (k == i) continue;
                for(int j = 0 ; j < 26; j++){
                    if(k == j || i == j) continue;
                    if (minCost[i][j] <= minCost[i][k] + minCost[k][j]){
                        continue;
                    }
                    minCost[i][j] = minCost[i][k] + minCost[k][j];
                }
            }
        }
        long long ans = 0;
        for(int i = 0 ; i < source.size(); i++){
            int a = source[i] - 'a';
            int b = target[i] - 'a';
            if (a == b) continue;
            if(minCost[a][b] == 1234567890) return -1;
            ans += minCost[a][b];
        }
        return ans;
    }
};

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

Count Number of Teams  (0) 2025.02.04
Second Minimum Time to Reach Destination  (0) 2025.02.04
Find the City With the Smallest Number of Neighbors at a Threshold Distance  (0) 2025.02.04
Sort an Array  (0) 2025.02.04
Sort the Jumbled Numbers  (0) 2025.02.04
블로그 이미지

짬뽕얼큰하게

,

Find the City With the Smallest Number of Neighbors at a Threshold Distance

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

Leetcode Problem:

Summary

  • Find the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold.

Approach

  • The solution uses Floyd-Warshall algorithm to find the shortest path between all pairs of cities, then iterates through each city to count the number of cities that are reachable within the distanceThreshold
  • The city with the smallest count that has the greatest number is returned.

Complexity

  • O(n^3)

Explain

  • The solution first initializes a 2D array dis to store the shortest distance between each pair of cities
  • It then iterates through each edge in the edges array and updates the dis array
  • After that, it uses Floyd-Warshall algorithm to find the shortest path between all pairs of cities
  • Finally, it iterates through each city and counts the number of cities that are reachable within the distanceThreshold
  • The city with the smallest count that has the greatest number is returned.

Solution Code:


class Solution {
public:
        int findTheCity(int n, vector>& edges, int distanceThreshold) {
        vector> dis(n, vector(n, 10001));
        int res = 0, smallest = n;
        for (auto& e : edges)
            dis[e[0]][e[1]] = dis[e[1]][e[0]] = e[2];
        for (int i = 0; i < n; ++i)
            dis[i][i] = 0;
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < n; ++j)
                if (dis[i][j] <= distanceThreshold)
                    ++count;
            if (count <= smallest) {
                res = i;
                smallest = count;
            }
        }
        return res;
    }
};

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

Second Minimum Time to Reach Destination  (0) 2025.02.04
Minimum Cost to Convert String I  (0) 2025.02.04
Sort an Array  (0) 2025.02.04
Sort the Jumbled Numbers  (0) 2025.02.04
Longest Strictly Increasing or Strictly Decreasing Subarray  (0) 2025.02.03
블로그 이미지

짬뽕얼큰하게

,

Sort an Array

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

Leetcode Problem:

Summary

  • Sort an array of integers in ascending order without using built-in O(nlog(n)) time complexity and smallest space complexity possible.

Approach

  • The approach used is a modified merge sort algorithm
  • The array is divided into two halves until each subarray contains only one element, and then the subarrays are merged back together in sorted order.

Complexity

  • O(nlog(n))

Explain

  • The solution code uses a modified merge sort algorithm to sort the array
  • The merge function takes three parameters: the left index, the right index, and the current index
  • It compares the elements at the left and right indices and swaps them if necessary
  • The merge_sort function recursively divides the array into two halves until each subarray contains only one element, and then it merges the subarrays back together in sorted order
  • The time complexity of the solution is O(nlog(n)) because the merge sort algorithm has a time complexity of O(nlog(n)) and the space complexity is O(n) because the temporary array has a size of n.

Solution Code:


class Solution {
public:
    void merge(vector& nums, int l , int mid, int r){
        int i = l;
        int j = mid + 1;
        int cur = i;
        int tmp[50001];
        while(i <= mid && j <= r){
            if (nums[i] <= nums[j]){
                tmp[cur++] = nums[i++];
            } else {
                tmp[cur++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[cur++] = nums[i++];
        }
        for(i = l; i < cur; i++){
            nums[i] = tmp[i];
        }
    }
    void merge_sort(vector& nums, int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid+1, r);
        merge(nums, l, mid, r);
    }
    vector sortArray(vector& nums) {
        merge_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

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

Minimum Cost to Convert String I  (0) 2025.02.04
Find the City With the Smallest Number of Neighbors at a Threshold Distance  (0) 2025.02.04
Sort the Jumbled Numbers  (0) 2025.02.04
Longest Strictly Increasing or Strictly Decreasing Subarray  (0) 2025.02.03
Sort Array by Increasing Frequency  (0) 2025.02.03
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/02   »
일 월 화 수 목 금 토
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

티스토리툴바