'2025/02/13'에 해당되는 글 11건

Leetcode Problem:

• Minimum Operations to Exceed Threshold Value II

Summary

• Find the minimum number of operations to make all elements in the array greater than or equal to k.

Approach

• Use a min-heap data structure to efficiently remove the two smallest elements from the array and add their minimum value times 2 plus their maximum value back into the array.

Complexity

• O(n log n) due to the heap operations, where n is the size of the input array.

Solution Code:

struct _heap{
    long long arr[400002];
    int size;
    _heap(){
        size = 1;
    }
    void push(long long a){
        arr[size++] = a;
        int idx = size - 1;
        while(idx > 1 && arr[idx/2] > arr[idx]){
            long long t = arr[idx];
            arr[idx] = arr[idx/2];
            arr[idx/2] = t;
            idx /= 2;
        }
    }
    long long pop(){
        long long ret = arr[1];
        arr[1] = arr[--size];
        int i = 1;
        while(true){
            int j = i * 2;
            if (j >= size) break;
            if(j + 1 < size && arr[j] > arr[j + 1]){
                j++;
            }
            if(arr[i] > arr[j]){
                long long t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                i = j;
            }else{
                break;
            }
        }
        return ret;
    }
    bool empty(){
        return size == 1;
    }
};

class Solution {
public:
    _heap pq;
    int minOperations(vector& nums, int k) {
        for(int i = 0 ; i < nums.size(); i++){
            pq.push(nums[i]);
        }
        int cnt = 0;
        while(!pq.empty()){
            long long x = pq.pop();
            if (x >= k) break;
            long long y = pq.pop();
            pq.push(min(x, y)*2 + max(x, y));
            cnt++;
        }
        return cnt;
    }
};

Leetcode Problem:

• Divide Players Into Teams of Equal Skill

Summary

• Divide players into teams of equal skill and return the sum of chemistry of all teams.

Approach

• Use a hash map to store the frequency of each skill, sort the skills, and then iterate over the sorted skills to divide the players into teams.

Complexity

• O(n log n) due to sorting, where n is the number of players

Explain

• The solution first calculates the total skill and the target skill for each team
• It then iterates over the sorted skills, and for each skill, it checks if there is a corresponding team with the required skill
• If found, the players are divided into the team and the chemistry is calculated and added to the result
• If not found, the function returns -1.

Solution Code:

class Solution {
public:
    long long dividePlayers(vector& skill) {
        unordered_map m;
        sort(skill.begin(), skill.end());
        int total = 0;
        int N = skill.size();
        for(int i = 0 ; i < N; i++){
            m[skill[i]]++;
            total += skill[i];
        }
        int eachSum = total / (N / 2);
        long long res = 0;
        for(int i = 0 ; i < N/2; i++){
            int a = skill[i];
            int b = eachSum - a;
            if (m[a] == 0) return -1;
            m[a]--;
            if (m[b] == 0) return -1;
            m[b]--;
            res += a*b;
        }
        return res;

    }
};

Leetcode Problem:

• Make Sum Divisible by P

Summary

• Given an array of positive integers and a divisor, find the length of the smallest subarray that needs to be removed to make the sum of the remaining elements divisible by the divisor.

Approach

• The solution uses a sliding window approach and a hash map to keep track of the prefix sum modulo the divisor
• It iterates through the array, updating the prefix sum and the hash map, and at each step, it checks if there is a previous prefix sum that is congruent to the current prefix sum minus the needed prefix sum modulo the divisor
• If such a prefix sum exists, it updates the result with the minimum length of the subarray that needs to be removed.

Complexity

• O(n), where n is the length of the array, because each element in the array is processed once.

Explain

• The solution starts by initializing the result with the length of the array, the needed prefix sum, and the current prefix sum
• It then iterates through the array, updating the current prefix sum and the hash map
• At each step, it checks if there is a previous prefix sum that is congruent to the current prefix sum minus the needed prefix sum modulo the divisor
• If such a prefix sum exists, it updates the result with the minimum length of the subarray that needs to be removed
• Finally, it returns the result, which is either the minimum length of the subarray that needs to be removed or -1 if it is impossible to make the sum of the remaining elements divisible by the divisor.

Solution Code:

class Solution {
public:
    
      int minSubarray(vector& A, int p) {
        int n = A.size(), res = n, need = 0, cur = 0;
        for (auto a : A)
            need = (need + a) % p;
        unordered_map last = {{0, -1}};
        for (int i = 0; i < n; ++i) {
            cur = (cur + A[i]) % p;
            last[cur] = i;
            int want = (cur - need + p) % p;
            if (last.count(want))
                res = min(res, i - last[want]);
        }
        return res < n ? res : -1;
    }
};

Leetcode Problem:

• Rank Transform of an Array

Summary

• Given an array of integers, replace each element with its rank
• The rank represents how large the element is.

Approach

• The approach used is to first sort the array and then create a map to store the rank of each unique number
• Then, for each number in the original array, find its rank in the map and add it to the result vector.

Complexity

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

Solution Code:

class Solution {
public:
    vector arrayRankTransform(vector& arr) {
        vector arr2 = arr;
        sort(arr2.begin(), arr2.end());
        unordered_map m;
        
        int rank = 0;
        int curNum = -1;
        for(int num : arr2){
            if(curNum == num){
                continue;
            }
            curNum = num;
            rank++;
            m[num] = rank;
        }

        vector ans;
        for(int num: arr){
            ans.push_back(m[num]);
        }
        return ans;
    }
};

Leetcode Problem:

• Check If Array Pairs Are Divisible by k

Summary

• Given an array of integers and an integer k, determine if it is possible to divide the array into exactly n/2 pairs such that the sum of each pair is divisible by k.

Approach

• This problem can be solved using a hash map to count the remainders of the array elements when divided by k
• We first calculate the offset as k * k, then for each number in the array, we increment the count of the remainder
• If the count of 0 is odd, it means that we cannot divide the array into pairs with sum divisible by k
• Otherwise, we check if the counts of all remainders from 1 to k-1 are equal, and if the count of k/2 is odd when k is even
• If any of these conditions are not met, we return false
• Otherwise, we return true.

Complexity

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

Explain

• This solution works by first calculating the offset as k * k, then for each number in the array, we increment the count of the remainder
• If the count of 0 is odd, it means that we cannot divide the array into pairs with sum divisible by k
• Otherwise, we check if the counts of all remainders from 1 to k-1 are equal, and if the count of k/2 is odd when k is even
• If any of these conditions are not met, we return false
• Otherwise, we return true.

Solution Code:

class Solution {
public:
    unordered_map cnt;
    bool canArrange(vector& arr, int k) {
        if (k == 1) return true;
        long long offset = k;
        while(offset < 1e9){
            offset *= k;
        }
        for(long long num : arr){
            cnt[(num + offset) % k]++;
        }
        if(cnt[0] & 1) return false;
        for(int i = 1; i < ((k+1)>>1); i++){
            if(cnt[i] != cnt[k - i]) return false;
        }
        if((k %2) == 0 && ((cnt[k/2] %2) == 1)){
            return false;
        }
        return true;
    }
};

Leetcode Problem:

• Design a Stack With Increment Operation

Summary

• Design a stack that supports increment operations on its elements
• The CustomStack class is implemented with a maximum size and supports push, pop, and increment operations.

Approach

• The CustomStack class uses an array to store the stack elements and a separate array to store the lazy values
• The lazy array is used to store the increment values for each element in the stack
• The push operation adds an element to the top of the stack, the pop operation removes an element from the top of the stack and updates the lazy values, and the increment operation updates the lazy values for a range of elements in the stack.

Complexity

• O(1) for push, O(1) for pop, and O(min(k, top)) for increment operations

Explain

• The CustomStack class is implemented with two arrays, arr and lazy, to store the stack elements and lazy values respectively
• The top variable is used to keep track of the top element in the stack
• The push operation adds an element to the top of the stack and updates the lazy value for the top element
• The pop operation removes an element from the top of the stack and updates the lazy values for the elements below it
• The increment operation updates the lazy values for a range of elements in the stack
• The time complexity of the push and pop operations is O(1) because they only involve updating a single element in the stack
• The time complexity of the increment operation is O(min(k, top)) because it involves updating the lazy values for a range of elements in the stack.

Solution Code:

class CustomStack {
public:
    int stackSize;
    int arr[1001];
    int lazy[1001];
    int top;
    CustomStack(int maxSize) {
        stackSize = maxSize;
        top = 0;
        for(int i = 0 ; i < maxSize; i++){
            lazy[i] = 0;
        }
    }
    
    void push(int x) {
        if (top == stackSize) return;
        arr[top++] = x;
    }
    
    int pop() {
        if (top == 0) return -1;
        top--;
        if (top > 0) lazy[top-1] += lazy[top];
        arr[top] += lazy[top];
        lazy[top] = 0;
        return arr[top];
    }
    
    void increment(int k, int val) {
        if (top == 0) return;
        lazy[min(k-1, top-1)] += val;
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack* obj = new CustomStack(maxSize);
 * obj->push(x);
 * int param_2 = obj->pop();
 * obj->increment(k,val);
 */

Leetcode Problem:

• All O`one Data Structure

Summary

• Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Approach

• A Trie data structure is used to store the strings with their counts
• The Trie is divided into multiple levels based on the count of the strings
• The maxKey and minKey variables are used to keep track of the maximum and minimum counts respectively.

Complexity

• O(1) average time complexity

Explain

• The inc function increments the count of the string key by 1
• If the key does not exist, it is inserted with count 1
• The dec function decrements the count of the string key by 1
• If the count becomes 0, the key is removed from the data structure
• The getMaxKey and getMinKey functions return one of the keys with the maximum and minimum counts respectively.

Solution Code:

struct _node{
    int cnt;
    int idx;
};
template 
struct trie{
    T1 *nod;
    trie* next[26];
    trie(){
        nod = nullptr;
        for(int i = 0 ; i < 26; i++){
            next[i] = nullptr;
        }
    }
    ~trie(){
        if (nod != nullptr) delete nod;
        for(int i = 0 ; i < 26; i++){
            if(next[i] != nullptr) delete next[i];
            next[i] = nullptr;
        }
    }
};

trie<_node> *root;
_node* getNode(string &s){
    trie<_node>* ptr = root;
    for(char c : s){
        int idx = c - 'a';
        if(ptr->next[idx] == nullptr){
            ptr->next[idx] = new trie<_node>();
        }
        ptr = ptr->next[idx];
    }
    if(ptr->nod == nullptr){
        ptr->nod = new _node();
        ptr->nod->cnt = 0;
        ptr->nod->idx = -1;
    }
    return ptr->nod;
}

template 
struct _vector{
    T* arr;
    int size;
    int capacity;

    _vector(){
        size = 0;
        capacity = 1;
        arr = new T[capacity];
    }

    void push(T &a){
        if(size == capacity){
            capacity*=2;
            T* tmp = new T[capacity];
            for(int i = 0 ; i < size; i++){
                tmp[i] = arr[i];
            }
            delete[] arr;
            arr = tmp;
        }
        arr[size++] = a;
    }

    void del(int idx){
        arr[idx] = arr[--size];
        _node* nod = getNode(arr[idx]);
        nod->idx = idx;
    }
    T operator[](int idx){
        return arr[idx];
    }
};


class AllOne {
private:
    _vector v[50001];
public:
    int maxKey;
    int minKey;
    AllOne() {
        root = new trie<_node>();
        minKey = maxKey = 1;
    }
    ~AllOne() {
        delete root;
    }
    
    void inc(string key) {
        _node* nod = getNode(key);
        if(nod->cnt == minKey && v[nod->cnt].size == 1){
            minKey++;
        }
        if (nod->cnt == 0){
            minKey = 1;
        }
        if (nod->cnt == maxKey){
            maxKey++;
        }
        nod->cnt++;
        if(nod->cnt != 1){
            v[nod->cnt-1].del(nod->idx);
        }
        nod->idx = v[nod->cnt].size;
        v[nod->cnt].push(key);
        
    }
    
    void dec(string key) {
        _node* nod = getNode(key);
        if (nod->cnt == maxKey && v[nod->cnt].size == 1){
            maxKey--;
        }
        if (nod->cnt == minKey){
            minKey--;
        }
        
        v[nod->cnt].del(nod->idx);
        nod->cnt--;
        if(nod->cnt != 0){
            nod->idx = v[nod->cnt].size;
            v[nod->cnt].push(key);
        }
        if(minKey == 0){
            for(int i = minKey+1; i <= maxKey; i++){
                if(v[i].size > 0){
                    minKey = i;
                    break;
                }
            }
        }
    }
    
    string getMaxKey() {
        if (v[maxKey].size > 0) return v[maxKey][0];
        return "";
    }
    
    string getMinKey() {
        if (v[minKey].size > 0) return v[minKey][0];

        return "";
    }
};

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne* obj = new AllOne();
 * obj->inc(key);
 * obj->dec(key);
 * string param_3 = obj->getMaxKey();
 * string param_4 = obj->getMinKey();
 */

Leetcode Problem:

• Design Circular Deque

Summary

• Design a circular double-ended queue (deque) with methods to insert elements at the front and rear, delete elements from the front and rear, and check if the queue is empty or full.

Approach

• A circular deque is implemented using a fixed-size array
• The front and rear indices are used to track the current positions of the front and rear elements
• The insertFront, insertLast, deleteFront, and deleteLast methods update the front and rear indices accordingly
• The isEmpty and isFull methods check the front and rear indices to determine if the queue is empty or full.

Complexity

• O(1) for insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, and isFull operations
• O(n) for printing the queue, where n is the number of elements in the queue.

Explain

• The MyCircularDeque class is implemented using a fixed-size array of size k+2
• The front and rear indices are used to track the current positions of the front and rear elements
• The insertFront method adds an element at the front of the queue and updates the front index
• The insertLast method adds an element at the rear of the queue and updates the rear index
• The deleteFront method removes an element from the front of the queue and updates the front index
• The deleteLast method removes an element from the rear of the queue and updates the rear index
• The getFront and getRear methods return the front and rear elements respectively
• The isEmpty and isFull methods check if the queue is empty or full by comparing the front and rear indices.

Solution Code:

class MyCircularDeque {
public:
    int deque[1001];
    int size;
    int front;
    int rear;
    
    MyCircularDeque(int k) {
        size = k+2;
        front = rear = 0;
    }
    
    bool insertFront(int value) {
        if (isFull()) return false;
        if (isEmpty()){
            rear++;
            rear %= size;
        }
        deque[front--] = value;
        front = (front + size) % size;
        return true;
    }
    
    bool insertLast(int value) {
        if (isFull()) return false;
        if (isEmpty()){
            front = (front-1 + size) % size;
        }
        deque[rear++] = value;
        rear %= size;
        return true;
    }
    
    bool deleteFront() {
        if (isEmpty()) return false;
        front = (front + 1)%size;
        if ((front + 1)%size == rear){
            rear = front;
        }
        
        return true;
    }
    
    bool deleteLast() {
        if (isEmpty()) return false;
        rear = (rear - 1 + size) % size;
        if ((rear - 1 + size)%size == front){
            front = rear;
        }
        return true;
    }
    
    int getFront() {
        if (isEmpty()) return -1;
        int getIdx = (front + 1) % size;
        return deque[getIdx];
    }
    
    int getRear() {
        if (isEmpty()) return -1;
        int getIdx = (rear - 1 + size) % size;
        return deque[getIdx];
    }
    
    bool isEmpty() {
        return front == rear;
    }
    
    bool isFull() {
        return front == (rear + 1) % size;
    }
};

/**
 * Your MyCircularDeque object will be instantiated and called as such:
 * MyCircularDeque* obj = new MyCircularDeque(k);
 * bool param_1 = obj->insertFront(value);
 * bool param_2 = obj->insertLast(value);
 * bool param_3 = obj->deleteFront();
 * bool param_4 = obj->deleteLast();
 * int param_5 = obj->getFront();
 * int param_6 = obj->getRear();
 * bool param_7 = obj->isEmpty();
 * bool param_8 = obj->isFull();
 */

Leetcode Problem:

• My Calendar II

Summary

• Implementing a calendar system to avoid triple booking.

Approach

• This solution uses a data structure to store the events in the calendar
• It first checks for overlapping events with existing events in the calendar and returns false if a triple booking is found
• If no overlap is found, it adds the new event to the calendar.

Complexity

• O(n log n) due to sorting of events in the calendar

Explain

• The MyCalendarTwo class uses a vector to store the events in the calendar
• The book method first checks for overlapping events with existing events in the calendar
• It uses a nested loop to check for overlapping events and returns false if a triple booking is found
• If no overlap is found, it adds the new event to the calendar
• The time complexity of this solution is O(n log n) due to sorting of events in the calendar.

Solution Code:

struct _pair{
    int start;
    int end;
};
class MyCalendarTwo {
public:
    vector<_pair> bookList;
    MyCalendarTwo() {
        
    }
    
    bool book(int start, int end) {
        vector<_pair> doubleBookList;
        for(_pair book : bookList){
            if(book.start >= end || book.end <= start){
                continue;
            }
            int s = max(book.start, start);
            int e = min(book.end, end);
            for(_pair db: doubleBookList){
                if(db.start >= e || db.end <= s){
                    continue;
                }
                return false;
            }
            doubleBookList.push_back({s, e});
        }
        bookList.push_back({start, end});
        return true;
    }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

Leetcode Problem:

• My Calendar I

Summary

• Implementing a program to use as a calendar to avoid double booking.

Approach

• We use a vector of pairs to store the events in the calendar
• For each new event, we check if it intersects with any existing events
• If it does, we return false
• Otherwise, we add the new event to the calendar.

Complexity

• O(n) where n is the number of events in the calendar

Explain

• We define a struct _pair to store the start and end times of each event
• In the book function, we iterate over each event in the calendar
• If the end time of the new event is less than or equal to the start time of an existing event, or if the start time of the new event is greater than the end time of an existing event, we continue to the next event
• If we find an existing event that intersects with the new event, we return false
• Otherwise, we add the new event to the calendar by pushing it onto the vector of pairs and return true.

Solution Code:

struct _pair{
    int start;
    int end;
};
class MyCalendar {
public:
    vector<_pair> v;
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        for(_pair p : v){
            if (end <= p.start || p.end <= start){
                continue;
            }
            return false;
        }
        v.push_back({start, end});
        return true;
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */