짬뽕얼큰하게의 맨땅에 헤딩 :: 'LeetCode' 태그의 글 목록 (24 Page)

Minimum Difference Between Largest and Smallest Value in Three Moves

알고리즘 2025. 2. 2. 20:30

summary

  • Find the minimum difference between the largest and smallest value of an integer array after performing at most three moves.

approach

  • This solution uses a depth-first search (DFS) approach to try all possible moves and find the minimum difference
  • The DFS function recursively tries different moves and updates the minimum difference
  • The main function first sorts the array and then calls the DFS function with the initial minimum and maximum values.

complexity

  • O(n * 4^3) where n is the number of elements in the array

explain

  • The solution starts by sorting the input array
  • Then, it uses a DFS function to try all possible moves
  • The DFS function takes the current array, the current depth (which represents the number of moves made so far), the left and right indices of the current subarray
  • If the current depth is 3, it means we have made 3 moves, so it returns the difference between the maximum and minimum values in the current subarray
  • Otherwise, it recursively tries two possible moves: moving the left element to the right and moving the right element to the left
  • The minimum difference found by these two recursive calls is returned
  • The main function calls the DFS function with the initial minimum and maximum values and returns the result.

Solution Code:


int abs(int x){
    return x < 0 ? -x : x;
}
class Solution {
public:
    int dfs(vector&nums, int depth, int l, int r){
        if (depth == 3){
            return nums[r] - nums[l];
        }
        int res = dfs(nums, depth+1, l+1, r);
        res = min(res, dfs(nums, depth+1, l, r-1));
        return res;
    }
    int minDifference(vector& nums) {
        if (nums.size() <= 3) return 0;
        sort(nums.begin(), nums.end());
        int l = 0;
        int r = nums.size() - 1;
        return dfs(nums, 0, l, r);
    }
};

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

Find the Minimum and Maximum Number of Nodes Between Critical Points  (0) 2025.02.02
Merge Nodes in Between Zeros  (0) 2025.02.02
Intersection of Two Arrays II  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Intersection of Two Arrays II

알고리즘 2025. 2. 2. 20:26

summary

  • Given two integer arrays, return an array of their intersection
  • Each element in the result must appear as many times as it shows in both arrays.

approach

  • The approach used is to first count the occurrences of each element in the first array using an unordered map
  • Then, for each element in the second array, if it exists in the map and its count is greater than 0, decrement the count and add the element to the result array.

complexity

  • O(n + m) where n and m are the sizes of the input arrays

explain

  • The solution iterates over the first array to count the occurrences of each element in the unordered map
  • Then, it iterates over the second array to find elements that exist in the map and add them to the result array
  • This approach ensures that each element in the result appears as many times as it shows in both arrays.

Solution Code:


class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        vector answer;
        unordered_map cnt;
        for(int i = 0 ; i < nums1.size(); i++){
            cnt[nums1[i]]++;
        }
        for(int i = 0 ; i < nums2.size(); i++){
            if(cnt[nums2[i]]){
                cnt[nums2[i]]--;
                answer.push_back(nums2[i]);
            }
        }
        return answer;
    }
};

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

Merge Nodes in Between Zeros  (0) 2025.02.02
Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Three Consecutive Odds

알고리즘 2025. 2. 2. 20:17

summary

  • Given an integer array, return true if there are three consecutive odd numbers in the array, otherwise return false.

approach

  • The solution uses a counter to keep track of the number of consecutive odd numbers
  • It iterates over the array, incrementing the counter whenever it encounters an odd number and resetting it whenever it encounters an even number
  • If the counter reaches 3, it immediately returns true
  • If it iterates over the entire array without finding three consecutive odd numbers, it returns false.

complexity

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

explain

  • The solution has a time complexity of O(n) because it makes a single pass over the array
  • The space complexity is O(1) because it uses a constant amount of space to store the counter.

Solution Code:


class Solution {
public:
    bool threeConsecutiveOdds(vector& arr) {
        int cnt = 0;
        for(int i = 0 ; i < arr.size(); i++){
            if(arr[i] & 1){
                cnt++;
            } else {
                cnt = 0;
            }
            if (cnt >= 3) return true;
        }
        return false;
    }
};

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

Minimum Difference Between Largest and Smallest Value in Three Moves  (0) 2025.02.02
Intersection of Two Arrays II  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Remove Max Number of Edges to Keep Graph Fully Traversable

알고리즘 2025. 2. 2. 19:56

summary

  • This problem involves finding the maximum number of edges that can be removed from an undirected graph so that it can still be fully traversed by both Alice and Bob.

approach

  • The approach used in this solution is to first separate the edges into three types: Type 1 (can be traversed by Alice only), Type 2 (can be traversed by Bob only), and Type 3 (can be traversed by both Alice and Bob)
  • Then, we use disjoint sets to keep track of the connected components of the graph for each type of edge
  • We remove the maximum number of edges of Type 3 while ensuring that the graph remains fully traversable by both Alice and Bob.

complexity

  • O(n log n + m log m + n log n) where n is the number of nodes and m is the number of edges

explain

  • The solution starts by separating the edges into three types and initializing two disjoint sets for Alice and Bob
  • It then sorts the edges of each type by their type and uses the disjoint sets to keep track of the connected components of the graph
  • The solution then removes the maximum number of edges of Type 3 while ensuring that the graph remains fully traversable by both Alice and Bob
  • If the graph is not fully traversable, the solution returns -1
  • The time complexity is O(n log n + m log m + n log n) due to the sorting and disjoint set operations.

Solution Code:




class Solution {
public:
    int u1[100001];
    int u2[100001];
    
    vector> edgesType1;
    vector> edgesType2;
    static bool cmp1(vector &a, vector &b){
        return a[0] > b[0];
    }
    static bool cmp2(vector &a, vector &b){
        return a[0] > b[0];
    }
    int disjoint(int* u, int x){
        if(u[x] == x) return x;
        return u[x] = disjoint(u, u[x]);
    }
    int maxNumEdgesToRemove(int n, vector>& edges) {
        edgesType1.clear();
        edgesType2.clear();
        int edgeSize = edges.size();
        for(int i = 1; i <= n; i++){
            u1[i] = i;
            u2[i] = i;
        }
        for(int i = 0; i < edges.size(); i++){
            if(edges[i][0] == 1){
                edgesType1.push_back(edges[i]);
            } else if (edges[i][0] == 2){
                edgesType2.push_back(edges[i]);
            } else{
                edgesType1.push_back(edges[i]);
                edgesType2.push_back(edges[i]);
            }
        }
        sort(edgesType1.begin(), edgesType1.end(), cmp1);
        sort(edgesType2.begin(), edgesType2.end(), cmp2);

        int type3 = 0;
        int cnt = 0;
        for (int idx = 0 ; idx < edgesType1.size(); idx++) {
            int type = edgesType1[idx][0];
            int a = edgesType1[idx][1];
            int b = edgesType1[idx][2];
            if(disjoint(u1, a) == disjoint(u1, b)){
                continue;
            }
            cnt++; 
            u1[disjoint(u1, a)] = disjoint(u1, b);
            if (type == 3){
                type3 += 1;
            }
            if (cnt == n -1) break;
        }
        if (cnt != n-1) return -1;
        cnt = 0;
        for (int idx = 0 ; idx < edgesType2.size(); idx++) {
            int type = edgesType2[idx][0];
            int a = edgesType2[idx][1];
            int b = edgesType2[idx][2];
            if(disjoint(u2, a) == disjoint(u2, b)){
                continue;
            }
            cnt++; 
            u2[disjoint(u2, a)] = disjoint(u2, b);
            if (cnt == n -1) break;
        }
        if (cnt != n-1) return -1;

        return edges.size() - (n - 1) - (n - 1) + type3;
    }
};

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

Intersection of Two Arrays II  (0) 2025.02.02
Three Consecutive Odds  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
Special Array I  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Find Center of Star Graph

알고리즘 2025. 2. 2. 19:44

summary

  • Finding the Center of a Star Graph

approach

  • The solution iterates over each edge in the graph and increments the count of the nodes at each end of the edge
  • It then checks if the count of any node exceeds 1
  • If so, that node is the center of the star graph and the function returns it.

complexity

  • O(n)

explain

  • The time complexity of this solution is O(n) because in the worst case, we might have to iterate over all n edges
  • The space complexity is also O(n) because in the worst case, we might have to store the count of all n nodes.

Solution Code:


class Solution {
public:
    int findCenter(vector>& edges) {
        int cnt[100001] = {0};
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            cnt[a]++;
            cnt[b]++;
            if (cnt[a] >= 2) return a;
            if (cnt[b] >= 2) return b;
        }
        return 0;
    }
};

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

Three Consecutive Odds  (0) 2025.02.02
Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
Special Array I  (0) 2025.02.02
Check if Array Is Sorted and Rotated  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

알고리즘 2025. 2. 2. 19:16

summary

  • The problem is to find the size of the longest non-empty subarray in the given array of integers such that the absolute difference between any two elements of this subarray is less than or equal to the given limit.

approach

  • The approach used is to use a sliding window technique with a multiset data structure to store the elements of the subarray
  • The multiset is used to keep track of the minimum and maximum elements in the current subarray
  • The sliding window is expanded to the right by adding elements to the multiset and contracting the window from the left by removing elements from the multiset if the absolute difference between the minimum and maximum elements exceeds the limit.

complexity

  • O(N log N) due to the insertion and removal operations in the multiset, where N is the size of the input array.

explain

  • The solution code initializes two pointers, l and r, to the start of the array
  • It also initializes a multiset, multi, to store the elements of the subarray
  • The code then enters a loop where it expands the sliding window to the right by adding elements to the multiset and checking if the absolute difference between the minimum and maximum elements exceeds the limit
  • If it does, the code contracts the window from the left by removing elements from the multiset
  • The code keeps track of the maximum length of the subarray seen so far and returns it at the end.

Solution Code:


class Solution {
public:
    int longestSubarray(vector& nums, int limit) {
        int l = 0;
        int r = 0;
        multiset multi;
        int N = nums.size();
        int ans = 0;
        
        multi.insert(nums[0]);
        while(r < N){
            int last = *(multi.rbegin());
            int first = *(multi.begin());
            if (abs(last - first) <= limit){
                ans = max(ans, r-l+1);
                r++;
                if (r < N){
                    multi.insert(nums[r]);
                }
            } else{
                multi.erase(multi.find(nums[l]));
                l++;
            }
        }
        return ans;
    }
};

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

Remove Max Number of Edges to Keep Graph Fully Traversable  (0) 2025.02.02
Find Center of Star Graph  (0) 2025.02.02
Special Array I  (0) 2025.02.02
Check if Array Is Sorted and Rotated  (0) 2025.02.02
Making A Large Island  (0) 2025.02.02
블로그 이미지

짬뽕얼큰하게

,

Special Array I

알고리즘 2025. 2. 2. 10:28

summary

  • Check if an array is special, where every pair of adjacent elements contains two numbers with different parity.

approach

  • Use a flag variable to track the parity of the first element
  • Then, iterate through the array, updating the flag variable based on the parity of each element
  • If a pair of adjacent elements has the same parity, return false
  • Otherwise, return true if all pairs have different parity.

complexity

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

explain

  • The solution uses bitwise operations to check the parity of each element
  • The expression `nums[i] & 1` checks if the least significant bit of `nums[i]` is 1 (i.e., the number is odd)
  • The `flag ^ (nums[i] & 1)` expression updates the flag variable based on the parity of `nums[i]`
  • If `flag` and `nums[i]` have different parity, `flag` is set to the opposite parity
  • If they have the same parity, `flag` remains unchanged
  • The solution returns false as soon as it encounters a pair of adjacent elements with the same parity, and returns true otherwise.

Solution Code:


class Solution {
public:
    bool isArraySpecial(vector& nums) {
        bool flag = nums[0] & 1;
        for(int i = 1; i < nums.size(); i++){
            if(flag ^ (nums[i] & 1)){
                flag ^= 1;
            } else{
                return false;
            }
        }
        return true;
    }
};

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

Find Center of Star Graph  (0) 2025.02.02
Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
Check if Array Is Sorted and Rotated  (0) 2025.02.02
Making A Large Island  (0) 2025.02.02
Redundant Connection  (0) 2025.02.01
블로그 이미지

짬뽕얼큰하게

,

Check if Array Is Sorted and Rotated

알고리즘 2025. 2. 2. 09:20

summary

  • Given an array of integers, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions, otherwise return false.

approach

  • The approach used is to find the minimum element in the array and the index of the minimum element
  • Then, check if the array can be rotated such that the minimum element becomes the first element
  • If it can, return true, otherwise return false.

complexity

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

explain

  • The solution code first finds the minimum element in the array and its index
  • Then, it checks if the array can be rotated such that the minimum element becomes the first element
  • If it can, it means the array was originally sorted in non-decreasing order and then rotated some number of positions
  • If it cannot, it means the array was not rotated and therefore the array was not originally sorted in non-decreasing order.

Solution Code:


class Solution {
public:
    bool check(vector& nums) {
        int N = nums.size();
        int minIdx = 0;
        int minValue = 101;
        for(int i = 0; i 
            if(minValue> nums[i]){
                minIdx = i;
                minValue = nums[i];
            }
        }
        int idx = N - 1;
        while(idx >= 0 && minIdx != N-1 && nums[minIdx] == nums[idx]){
            idx--;
        }
        if(idx != N-1){
            minIdx = idx + 1;
        }
        int beforeVal = nums[minIdx];
        minIdx = (minIdx + 1) %N;
        int n = N;
        n--;
        while(n--){
            if(beforeVal > nums[minIdx]){
                return false;
            }
            beforeVal = nums[minIdx];
            minIdx = (minIdx + 1) %N;
        }
        return true;
    }
};

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

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit  (0) 2025.02.02
Special Array I  (0) 2025.02.02
Making A Large Island  (0) 2025.02.02
Redundant Connection  (0) 2025.02.01
프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
블로그 이미지

짬뽕얼큰하게

,

Making A Large Island

알고리즘 2025. 2. 2. 01:29

summary

  • This solution calculates the size of the largest island in a binary matrix after changing at most one 0 to 1.

approach

  • This solution first calculates the size of each island in the grid, then finds the maximum island size
  • After that, it finds the maximum island size that can be formed by connecting islands with at most one common cell.

complexity

  • O(n^4)

explain

  • The solution first calculates the size of each island in the grid by using DFS
  • Then it finds the maximum island size
  • After that, it finds the maximum island size that can be formed by connecting islands with at most one common cell
  • The time complexity is O(n^4) due to the nested loops in the DFS and the loop to find the maximum island size.

Solution Code:


class Solution {
public:
    int groups[62501];
    int groupSize;
    int R;
    int C;
    set aroundGroup[500][500];
    void calcGroupCnt(vector>& grid, int r, int c, int& cnt, int visited[500][500],int groupIdx){
        if(r < 0 || r >= R || c <0 || c >= C || visited[r][c] || grid[r][c] == 0){
            return;
        }
        visited[r][c] = groupIdx;
        cnt++;
        calcGroupCnt(grid, r+1, c, cnt, visited, groupIdx);
        calcGroupCnt(grid, r-1, c, cnt, visited, groupIdx);
        calcGroupCnt(grid, r, c+1, cnt, visited, groupIdx);
        calcGroupCnt(grid, r, c-1, cnt, visited, groupIdx);
    }
    int largestIsland(vector>& grid) {
        R = grid.size();
        C = grid[0].size();
        int visited[500][500] = {0};
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(grid[i][j] == 1 && visited[i][j] == 0){
                    int cnt = 0;
                    groupSize++;
                    calcGroupCnt(grid, i, j, cnt, visited, groupSize);
                    groups[groupSize] = cnt;
                }        
            }
        }
        int ans = 0;
        for(int i = 1 ; i <= groupSize; i++){
            ans = max(ans, groups[i]);
        }


        int dy[] = {1, 0, -1, 0};
        int dx[] = {0, 1, 0, -1};
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                if(visited[i][j]) continue;
                for(int d = 0; d < 4; d++){
                    int nr = i + dy[d];
                    int nc = j + dx[d];
                    if(nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc] == 0){
                        continue;
                    }
                    aroundGroup[i][j].insert(visited[nr][nc]);
                }
            }
        }
        for(int i = 0 ; i < R; i++){
            for(int j = 0 ; j < C; j++){
                int ans2 = 0;
                for(auto iter : aroundGroup[i][j]){
                    ans2 += groups[iter];
                }
                ans = max(ans, ans2 + 1);
            }
        }

        return ans;
    }
};

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

Special Array I  (0) 2025.02.02
Check if Array Is Sorted and Rotated  (0) 2025.02.02
Redundant Connection  (0) 2025.02.01
프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
블로그 이미지

짬뽕얼큰하게

,

Redundant Connection

알고리즘 2025. 2. 1. 19:59

summary

  • Find the edge that can be removed from a connected graph with n nodes and m edges to make it a tree.

approach

  • Use a union-find data structure to keep track of connected components in the graph
  • Iterate through the edges, and for each edge, check if the two nodes are in the same component
  • If they are, then the edge is the redundant one
  • Otherwise, union the two components.

complexity

  • O(n + m log n) due to the union-find operations, where n is the number of nodes and m is the number of edges.

explain

  • The solution uses a union-find data structure to keep track of connected components in the graph
  • The union-find data structure is initialized with each node as its own component
  • Then, for each edge, the solution checks if the two nodes are in the same component by calling the `disjoint` function
  • If they are, then the edge is the redundant one, and the solution returns it
  • Otherwise, the solution unions the two components by calling the `uf` function
  • The `disjoint` function is used to find the root of a node, and the `uf` function is used to union two components.

Solution Code:


class Solution {
public:
    int uf[1001];
    int disjoint(int x){
        if(x == uf[x]) return x;
        return uf[x] = disjoint(uf[x]);
    }
    vector findRedundantConnection(vector>& edges) {
        for(int i = 0 ; i <= 1000; i++){
            uf[i] = i;
        }
        vector ans;
        for(int i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            if(disjoint(a) != disjoint(b)){
                uf[disjoint(a)] = disjoint(b);
            } else{
                ans.push_back(a);
                ans.push_back(b);
            }
        }
        return ans;
    }
};

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

Check if Array Is Sorted and Rotated  (0) 2025.02.02
Making A Large Island  (0) 2025.02.02
프로그래머스 (PROGRAMMERS) 문자열압축  (0) 2021.01.18
프로그래머스 (Programmers) 입국심사  (0) 2021.01.12
프로그래머스 (Programmers) 가장 먼 노드  (0) 2021.01.11
블로그 이미지

짬뽕얼큰하게

,

공지사항

글 보관함

달력

«   2025/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 29 30

티스토리툴바