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

Count Number of Bad Pairs

알고리즘 2025. 2. 9. 09:45

Leetcode Problem:

Summary

  • The problem requires to find the total number of bad pairs in a given integer array
  • A bad pair is defined as a pair of indices (i, j) where i < j and j - i!= nums[j] - nums[i].

Approach

  • The approach used in the solution is to first modify the input array by adding the difference between the current index and the total length of the array to each element
  • This is done to simplify the calculation of bad pairs
  • Then, a hashmap is used to store the frequency of each modified element
  • Finally, the total number of bad pairs is calculated by subtracting the sum of the first 'N' natural numbers (where N is the length of the array) from the total possible pairs and subtracting the sum of the frequencies of each modified element multiplied by the frequency minus one divided by two.

Complexity

  • O(N) where N is the length of the input array

Explain

  • The solution starts by modifying the input array by adding the difference between the current index and the total length of the array to each element
  • This is done to simplify the calculation of bad pairs
  • Then, a hashmap is used to store the frequency of each modified element
  • The total number of bad pairs is calculated by subtracting the sum of the first 'N' natural numbers (where N is the length of the array) from the total possible pairs and subtracting the sum of the frequencies of each modified element multiplied by the frequency minus one divided by two
  • This is because a pair is bad if the difference between the two elements is not equal to the difference between their indices
  • By using the hashmap, we can efficiently count the number of bad pairs.

Solution Code:


class Solution {
public:
    unordered_map map;
    long long countBadPairs(vector& nums) {
        int N = nums.size();
        for(int i = 0 ; i < N; i++){
            nums[i] += N - i;
        }
        for(int i = 0 ; i < N; i++){
            map[nums[i]]++;
        }
        long long cnt = 0;
        for(auto iter : map){
            if(iter.second >= 2){
                cnt += ((iter.second) * (iter.second-1)) >> 1;
            }
        }
        return (((long long)N * (N-1)) >> 1) - cnt;
    }
};

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

Ugly Number II  (0) 2025.02.10
Maximum Distance in Arrays  (0) 2025.02.10
Find K-th Smallest Pair Distance  (0) 2025.02.09
Combination Sum II  (0) 2025.02.09
Kth Largest Element in a Stream  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

Find K-th Smallest Pair Distance

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

Leetcode Problem:

Summary

  • Find the kth smallest distance among all pairs of integers in an array.

Approach

  • Binary Search: The solution uses a binary search approach to find the kth smallest distance
  • It sorts the array and then uses two pointers (l and r) to represent the range of possible distances
  • The solution iterates through the range, calculating the number of pairs that have a distance less than or equal to the current mid value
  • If the number of pairs is greater than or equal to k, the solution updates the answer and moves the right pointer to the left
  • Otherwise, it moves the left pointer to the right.

Complexity

  • O(N log N + log k) where N is the length of the array
  • The sorting operation takes O(N log N) time, and the binary search takes O(log k) time.

Explain

  • The solution first sorts the array in ascending order
  • It then initializes two pointers, l and r, to represent the range of possible distances
  • The solution iterates through the range, calculating the number of pairs that have a distance less than or equal to the current mid value
  • If the number of pairs is greater than or equal to k, the solution updates the answer and moves the right pointer to the left
  • Otherwise, it moves the left pointer to the right
  • The solution repeats this process until the left pointer is greater than the right pointer
  • The final answer is the smallest distance that results in k pairs.

Solution Code:


class Solution {
public:
    int smallestDistancePair(vector& nums, int k) {
        sort(nums.begin(), nums.end());
        int N = nums.size();
        int l = 0;
        int r = 1000000;
        int ans = 0;
        while(l <= r ){
            int mid = (l + r) / 2;
            int left = 0;
            int right = 0;
            int cnt = 0;
            int beforeRight = 0;
            while(right < N){
                while(right < N && nums[right] - nums[left] <= mid){
                    right++;
                }
                int NN = right - left;
                cnt += (NN * (NN-1))/2;
                if (left != 0){
                    NN = (beforeRight - left);
                    cnt -= (NN * (NN-1))/2;
                }
                beforeRight = right;
                while(left < right && nums[right] - nums[left] > mid){
                    left++;
                }
            }
            if (cnt >= k){
                if (cnt == k){
                    ans = mid;
                }
                ans = mid;
                r = mid - 1;
            } else{
                l = mid + 1;
            }
        }
        return ans;
    }
};

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

Maximum Distance in Arrays  (0) 2025.02.10
Count Number of Bad Pairs  (0) 2025.02.09
Combination Sum II  (0) 2025.02.09
Kth Largest Element in a Stream  (0) 2025.02.09
Minimum Number of Days to Disconnect Island  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

Combination Sum II

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

Leetcode Problem:

Summary

  • Find all unique combinations in candidates where the candidate numbers sum to target.

Approach

  • Depth-First Search (DFS) with backtracking, utilizing a counter array to track the availability of each candidate number.

Complexity

  • O(N * target), where N is the number of candidates

Explain

  • The solution uses a DFS approach with backtracking to explore all possible combinations
  • It maintains a counter array to track the availability of each candidate number
  • The dfs function recursively tries to add each candidate number to the current combination, and backtracks if the sum exceeds the target or if the candidate number is no longer available
  • The solution also ensures that duplicate combinations are not included by using a history array to keep track of the candidate numbers added to the current combination.

Solution Code:


class Solution {
public:
    int cnt[31];
    void dfs(vector>& ans, vector& history, int cur, int sum, int target){
        if(sum == target){
            vector tmp;
            for(int i = 0 ; i < history.size(); i++){
                tmp.push_back(history[i]);
            }
            ans.push_back(tmp);
            return;
        }
        if (sum > target) return;

        for(int i = cur; i <= target; i++){
            if(cnt[i] <= 0) continue;
            cnt[i]--;
            history.push_back(i);
            dfs(ans, history, i, sum + i, target);
            cnt[i]++;
            history.pop_back();
        }
    }
    vector> combinationSum2(vector& candidates, int target) {
        for(int i = 0 ; i < candidates.size(); i++){
            if (candidates[i] > 30) continue;
            cnt[candidates[i]]++;
        }
        vector> ans;
        vector history;
        dfs(ans, history, 0, 0, target);
        return ans;
    }
};

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

Count Number of Bad Pairs  (0) 2025.02.09
Find K-th Smallest Pair Distance  (0) 2025.02.09
Kth Largest Element in a Stream  (0) 2025.02.09
Minimum Number of Days to Disconnect Island  (0) 2025.02.09
Regions Cut By Slashes  (0) 2025.02.09
블로그 이미지

짬뽕얼큰하게

,

Kth Largest Element in a Stream

알고리즘 2025. 2. 9. 08:45

Leetcode Problem:

Summary

  • Implement a class to track the kth highest test score from applicants in real-time.

Approach

  • Use two heaps, a min heap and a max heap, to store the scores
  • The max heap stores the k largest scores, and the min heap stores the remaining scores
  • When a new score is added, if the min heap is not full, push the score into the min heap
  • If the min heap is full and the new score is larger than the smallest score in the min heap, pop the smallest score from the min heap and push the new score into the min heap
  • If the new score is smaller than the smallest score in the min heap, push the new score into the max heap
  • The kth highest score is the top of the max heap.

Complexity

  • O(log n) for push and pop operations, where n is the number of scores.

Explain

  • The provided C++ code implements the KthLargest class using two heaps, a min heap and a max heap
  • The min heap stores the k largest scores, and the max heap stores the remaining scores
  • When a new score is added, if the min heap is not full, push the score into the min heap
  • If the min heap is full and the new score is larger than the smallest score in the min heap, pop the smallest score from the min heap and push the new score into the min heap
  • If the new score is smaller than the smallest score in the min heap, push the new score into the max heap
  • The kth highest score is the top of the max heap
  • The time complexity of the push and pop operations is O(log n), where n is the number of scores.

Solution Code:


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

class KthLargest {
public:
    _heap minHeap;
    _heap maxHeap;
    int K;
    vector tmp;
    KthLargest(int k, vector& nums) {
        K = k;
        minHeap.setCmp(minCmp);
        maxHeap.setCmp(maxCmp);
        for(int i = 0 ; i < nums.size(); i++){
            maxHeap.push(nums[i]);
        }
        while(k--){
            if (!maxHeap.empty())
                minHeap.push(maxHeap.pop());
        }
    }
    
    int add(int val) {
        if (minHeap.size <= K){
           minHeap.push(val); 
        }
        else if (minHeap.arr[1] < val){
            maxHeap.push(minHeap.pop());
            minHeap.push(val);
        } else {
            maxHeap.push(val);
        }
        
        return minHeap.arr[1];
    }
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest* obj = new KthLargest(k, nums);
 * int param_1 = obj->add(val);
 */

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

Find K-th Smallest Pair Distance  (0) 2025.02.09
Combination Sum II  (0) 2025.02.09
Minimum Number of Days to Disconnect Island  (0) 2025.02.09
Regions Cut By Slashes  (0) 2025.02.09
Find the Number of Distinct Colors Among the Balls  (0) 2025.02.07
블로그 이미지

짬뽕얼큰하게

,

Minimum Number of Days to Disconnect Island

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

Leetcode Problem:

Summary

  • This is a problem of finding the minimum number of days to disconnect a grid of land and water cells.

Approach

  • The solution uses a breadth-first search (BFS) approach to find the number of islands in the grid, and then iteratively tries to disconnect the islands by changing the land cells to water cells
  • The time complexity is O(R*C) for the BFS and O(R*C) for the iterative process, resulting in a total time complexity of O(R*C).

Complexity

  • O(R*C)

Explain

  • The solution first defines the grid size and the map of land and water cells
  • It then defines a helper function to perform BFS and find the number of islands
  • The main function iteratively tries to disconnect the islands by changing the land cells to water cells, and returns the minimum number of days required to disconnect the grid
  • The time complexity is dominated by the BFS and iterative process, which is O(R*C) for each call
  • The space complexity is also O(R*C) for the visited matrix and the recursive call stack.

Solution Code:


class Solution {
public:
    int R;
    int C;
    vector> map;
    void fill(int r, int c, bool visited[][31]){
        if (r < 0 || r >= R || c < 0 || c >= C || map[r][c] == 0 || map[r][c] == 3 || visited[r][c]){
            return;
        }
        visited[r][c]  = true;
        fill(r + 1, c, visited);
        fill(r, c + 1, visited);
        fill(r - 1, c, visited);
        fill(r, c - 1, visited);
    }
    int getIsland(){
        bool visited[31][31];
        int cnt = 0;
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                visited[i][j] = false;
            }
        }
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(map[i][j] == 1 && !visited[i][j]){
                    cnt++;
                    fill(i, j, visited);
                }
            }
        }
        return cnt;
    }
    bool closeWater(int r, int c){
        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        for(int i = 0 ;i  < 4; i++){
            int nr = r + dy[i];
            int nc = c + dx[i];
            if(nr < 0 || nr >= R || nc < 0 || nc >= C){
                return true;
            }
            if (map[nr][nc] == 0){
                return true;
            }
        }
        return false;
    }
    int minDays(vector>& grid) {
        R = grid.size();
        C = grid[0].size();
        map = grid;
        int ans = 0;
        int island_cnt = getIsland();
        while(island_cnt == 1){
            for(int i = 0 ; i < R; i++){
                for(int j = 0 ; j < C; j++){
                    if(map[i][j] == 0) continue;
                    map[i][j] = 0;
                    int tmpCnt = getIsland();
                    if(tmpCnt != 1) return ans + 1;
                    map[i][j] = 1;
                }
            }
           
            return 2;
        }
        
        return ans;
    }
};

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

Combination Sum II  (0) 2025.02.09
Kth Largest Element in a Stream  (0) 2025.02.09
Regions Cut By Slashes  (0) 2025.02.09
Find the Number of Distinct Colors Among the Balls  (0) 2025.02.07
Tuple with Same Product  (0) 2025.02.07
블로그 이미지

짬뽕얼큰하게

,

Regions Cut By Slashes

알고리즘 2025. 2. 9. 08:36

Leetcode Problem:

Summary

  • Given an n x n grid represented as a string array, return the number of regions.

Approach

  • The solution uses a 3D array to store the visited states of the grid cells
  • It then uses a recursive DFS function to fill in the visited states of the neighboring cells
  • The number of regions is incremented each time a new region is found.

Complexity

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

Explain

  • The solution first converts the input grid into a 3D array where each cell represents a state in the DFS
  • The states are defined as follows: - 0: not visited - 1: visited - 2: outside the grid The solution then uses a recursive DFS function to fill in the visited states of the neighboring cells
  • If a cell is not visited and is outside the grid, it increments the number of regions and marks the cell as visited
  • Finally, it returns the number of regions.

Solution Code:


class Solution {
public:
    int map[128][128];
    bool visited[128][128];
    int R, C;
    int ans = 0;
    void fill(int r, int c){
        if (r < 0 || r >= R || c < 0 || c >= C || map[r][c] == 1 || visited[r][c]){
            return;
        }
        visited[r][c] = true;
        fill(r + 1, c);
        fill(r, c + 1);
        fill(r - 1, c);
        fill(r, c - 1);
    }
    int regionsBySlashes(vector& grid) {
        R = grid.size();
        C = grid[0].length();
        for(int r = 0 ; r < R; r++){
            for(int c = 0; c < C; c++){
                if (grid[r][c] == '/'){
                    map[3*r][3*c+2] = 1;
                    map[3*r+1][3*c+1] = 1;
                    map[3*r+2][3*c] = 1;
                } else if (grid[r][c] == '\\'){
                    map[3*r][3*c] = 1;
                    map[3*r+1][3*c+1] = 1;
                    map[3*r+2][3*c+2] = 1;

                }
            }
        }
        R *= 3;
        C *= 3;
        for(int r = 0 ; r < R; r++){
            for(int c = 0 ; c < C; c++){
                if (map[r][c] == 0 && !visited[r][c]) {
                    fill(r, c);
                    ans++;
                }
            }
        }
        return ans;
    }
};

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

Kth Largest Element in a Stream  (0) 2025.02.09
Minimum Number of Days to Disconnect Island  (0) 2025.02.09
Find the Number of Distinct Colors Among the Balls  (0) 2025.02.07
Tuple with Same Product  (0) 2025.02.07
Check if One String Swap Can Make Strings Equal  (0) 2025.02.05
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   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

티스토리툴바