어쩌다보니 Logging System 을 만들고, 기록은 해놓아야 할 것 같아서, Singleton 패턴에 대해서 c++ 로 정리 하려고 한다. Singleton 이라는건 Class 를 딱 하나만 생성한다 라고 정의한다라는게 정의된다. static 으로 정의를 내릴수 있다. 그리고 객체가 복사가 이루어지면 안된다. 일단 싱글톤을 만든다고 하면, 하나의 설계 패턴이므로 나머지에 영향이 안가게끔 코드를 짜야된다. 일단 Meyer’s implementation 을 한번 봐보자.

class Singleton
{
public:
    static Singleton& getInstance();
    {
        static Singleton instance;
        return instance;
    }

private:
    Singleton(){}       // no one else can create one
    ~Singleton(){}      // prevent accidental deletion

    // disable copy / move 
    Singleton(Singleton const&) = delete;
    Signleton(Singleton&&) = delete;
    Singleton& operator=(Singleton const&) = delete;
    Singleton& operator=(Singleton&&) = delete
};

그렇다면 더확실하게 생성과 파괴의 주기를 확실하게 보기위해서는 아래와 같이 사용할수 있다.

class Singleton
{
public:
    static std::shared_ptr<Singleton> getInstance();
    {
        static std::shared_ptr<Signleton> s{ new Singleton };
        return s;
    }
private:
    Singleton(){}       // no one else can create one
    ~Singleton(){}      // prevent accidental deletion

    // disable copy / move 
    Singleton(Singleton const&) = delete;
    Signleton(Singleton&&) = delete;
    Singleton& operator=(Singleton const&) = delete;
    Singleton& operator=(Singleton&&) = delete
};

예제를 들어보자, 뭔가 기능상으로는 Random Number Generator 라고 하자. 아래와 같이 구현을 하면 좋을 같다.

class Random
{
public:
    static Random& Get()
    {
        static Random instance;
        return instance;
    }

    static float Float() { return Get().IFloat(); }
private:
    Random(){}
    ~Random();
    Random(const Random&) = delete;
    void operator=(Random const&) = delete;
    Random& operator=()
    float IFloat() { return m_RandomGenerator; } // internal
    float m_RandomGenerator = 0.5f;
};

int main()
{
    // auto& instance = Singleton::Get();   // this is good practice
    // Single instance = Singleton::Get();  // Copy this into new instance; Just want a single instance.

    float number = Random::Get().Float();
    return 0;
}

Resource

• Singleton Design Pattern
• Meyer’s Discussion
• Lecture Note
• The Cherno - Youtube

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.1

Implementation

• This is typical greey probelm, you select one, and compare it to get the maximum or the best output for goal once. This case, you want to maximize the profit, which in this case, you select one prices, and loop through to get the meximum prices.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;
        int buy = prices[0];
        for (int i = 1; i < prices.size(); i++) {
            int sell = prices[i];
            if (buy < sell) {
                profit = max(profit, sell - buy);
            } else {
                buy = sell;
            }
        }

        return profit;
    }
};

Resource

Best Time to Sell Stocks

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Approach

This is typically done in recursive fashion. But think of this. if i have steps 1, 2, 3, … i - 2, i - 1, i. Then, we need to use a step for i - 1 or i - 2 to get to i. This means I have several different steps to get to i. (this satisfies the optimal substructure). we can make a simple S(1) = 1, S(2) = 2, S(n) = S(n - 1) + S(n - 2).

First Implementation:

When I tested this on recursive way and submit, it exceed Time Limit!… Oh no…

class Solution {
public:
    int climbStairs(int n) {
        if (n < 1 || n > 46) return 0;
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

Second Implementation:

Now, I need to use dynamic programming, for top-down approach, it exceed Memory Limit, which possibly because of recursive way of saving into cache won’t work very well.

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 2;
        vector<int> dp(n+1, 0);
        
        if (dp[n]) return dp[n];
        int result = climbStairs(n - 1) + climbStairs(n - 2);
        return dp[n] = result;
    }
};

Third Attempts:

Now I choose the bottom up approach, and it worked very well!

class Solution {
public:
    int climbStairs(int n) {
        if (n <= 0) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 2;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i -1] + dp[i -2];
        }
        return dp[n];
    }
};

Resource

Climbing Stairs

Given an integer array arr and a 2D integer array queries, where each element of queries represents a query in the form of [s, e, k], perform the following operation for each query: For each query, find the smallest element in arr[i] that is greater than k for all i such that s ≤ i ≤ e. Return an array containing the answers for each query in the order they were processed. If no such element exists for a query, store -1 for that query.

Constraints:

The length of arr is between 1 and 1,000 (inclusive). Each element of arr is between 0 and 1,000,000 (inclusive). The length of queries is between 1 and 1,000 (inclusive). For each query [s, e, k], s and e are between 0 and the length of arr minus 1 (inclusive).

Implementation

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    int INF = std::numeric_limits<int>::max();
    vector<int> answer(queries.size(), INF);
    for(int i = 0; i < queries.size(); i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        int compare = queries[i][2];
        
        for (int j = start; j <= end; j++) {
            if (arr[j] > compare) {
                answer[i] = min(answer[i], arr[j]);
            }
        }
        
        if (answer[i] == INF) answer[i] = -1;
    }
    return answer;
}

Since, we’re looping through the queries n, which is O(n), but there is inner loop which is start time to end time. In the worst case, it can be O(n^2).

Given an integer array arr and a 2D integer array queries, where each element of queries represents a query in the form of [s, e], perform the following operation for each query: For each query, increment arr[i] by 1 for all i such that s ≤ i ≤ e. Return the array arr after processing all queries according to the above rule.

Constraints:

The length of arr is between 1 and 1,000 (inclusive). Each element of arr is between 0 and 1,000,000 (inclusive). The length of queries is between 1 and 1,000 (inclusive). For each query [s, e], s and e are between 0 and the length of arr minus 1 (inclusive).

Implementation

vector<int> solution(vector<int> arr, vector<vector<int>> queries) {
    for (int i = 0; i < queries.size(); i++) {
        int start = queries[i][0];
        int end = queries[i][1];
        for (int j = start; j <= end; j++) {
            arr[j]++;
        }
    }
    return arr;
}

instead of creating the output answer, we can just reduce the space, by writing into arr directly.

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

The major constraint is to calculate the product of array except itself. If you implement in brute force way, you will get O(n^2). However, this is the constraints! We need to solve this problem for O(n) time complexity with no extra space complexity.

Approach

This 2D structure represents the products of all numbers except the one at each index. The second and third lines show how we can calculate the left and right parts separately.

24, 2, 3, 4
1, 12, 3, 4
1,  2, 8, 4
1,  2, 3, 6

For the input array , the output array represents the prefix products, which are the products of all numbers to the left of each index. This prefix product is calculated by accumulating the numbers to the left at each iteration.

For instance, in the first iteration, there are no numbers to the left, so it’s just 1. In the second iteration, you have 1 to the left, so the output is 1 * 1 = 1. In the third iteration, you have 1 and 2 to the left, so the output becomes 1 * 2 = 2`, and so on.

This process continues until you have the prefix products for all indices. After calculating the prefix products, you can calculate the suffix products and multiply them with the prefix products to get the final result.

Then you do the right, which are going to be the product of suffix. You can do the same thing from right to left.

Implementation

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();

        std::vector<int> output(n, 1);

        // left
        for(int i = 1; i < n; i++) {
            output[i] = output[i - 1] * nums[i - 1];
        }
        
        // right
        int right = 1;
        for (int i = n - 1; i >= 0; i--){
            output[i] *= right;
            right *= nums[i];
        }
        
        return output;
    }
};

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Approach

• the fact that we’re looking for the sum, we just need to subtract the value in the nums, from the summation untill N.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int N = nums.size();
        int sum = 0;
        int compareSum = 0;
        for (int i = 0; i < N; i++){
            sum += nums[i];
        }
        
        for (int i = 0; i <= N; i++){
            compareSum += i;
        }

        return compareSum - sum;
    }
};

But this is O(N).

Can we make it better ?

Let’s think about this way, we are going to all the power to the sort(), which means the time complexity depends on sort algorithm. Then we can divide three cases:

1. If the first digit is missing, which is mostly likely 0 if the vector is sorted
2. If the last digit is missing, which is mostly likely the max Value of the vector.
3. If the any middle index are missing, starting from 0 to N-1, find the missing number and return the index.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        if (nums[0] != 0) return 0; // 0 is missing

        if (nums[n-1] != n) return n; // if the last character is missing

        for(int i = 1; i < nums.size(); i++){
            if (nums[i] != i) {
                return i;
            }
        }
        return 0;
    }
};

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Implementation

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* curr = dummyHead;
        int carry = 0;

        while(l1 != nullptr || l2 != nullptr || carry != 0) {
            int x = l1 ? l1->val : 0;
            int y = l2 ? l2->val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            l1 = l1 ? l1->next : nullptr;
            l2 = l2 ? l2->next : nullptr;
        }
ㅇㅇ
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }
};

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Approach

I thought if you put all the numbers in Set, then it will make my life easier, so I created set, then if loop counter is not in, then append to outputs like below

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> output;
        set<int> mySet(nums.begin(), nums.end());
        cout << nums.size() << endl;
        for (int i = 1; i <= nums.size(); i++)
        {
            if (!mySet.contains(i))
                output.push_back(i);
        }
        return output;
    }
};

Then I checked, and the time complexity was indeed O(n), but it took about 83 ms, which wasn’t what I wanted. One thing I was missing was considering the space complexity by switching to a set. However, as I looked at the hint, I realized that using the index itself was the key to improving performance.

One interesting aspect of the implementation below is that the elements at the corresponding index are marked as -1, indicating that the number exists somewhere, but the indices with positive values are the ones where the numbers do not correspond to their indices.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        int n = nums.size();
        vector<int> output;
        for(int i = 0; i < n; i++){
            int index = abs(nums[i]) - 1;
            if (nums[index] > 0){
                nums[index] = -nums[index];
            }
        }

        vector<int> result;
        for(int i = 0; i < n; i++) {
            if (nums[i] > 0)
                result.push_back(i + 1);
        }
        return result;
    }
};

Of course, unordered_map can be also good and fast, but space complexity can be O(n) in that case.

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        unordered_set<int> arr(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> ans;
        for(int i = 1; i <= n; i++) {
            if(arr.find(i) == arr.end()) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

• Reviewing what I studied, how this work will be explained as well.

Union-Find (Disjoint-Set) Concept

The Union-Find algorithm is used to manage disjoint-sets, which are collections of sets that are mutually exclusive, meaning they have no elements in common. This algorithm supports two primary operations: Find: This operation finds the representative element (root) of the set to which a given element belongs. Union: This operation merges two disjoint sets into one.

Disjoint-Set Tree

Disjoint-sets can be represented as a tree structure. Each node represents an element of a set, and child nodes point to their parents. The root node points to itself.

The Union-Find algorithm involves the following key operations:

• Make-Set: Initializes all elements to point to themselves.
• Find: Finds the root (representative element) of the set containing a given element.
• Union: Merges two disjoint sets into one.

int root[max_size];

// Similar to Make-Set function
for (int i = 0; i < max_size; i++) {
    parent[i] = i;
}

int find(int x) { // O(1)
    if (root[x] == x) {
        return x;
    }
    else {
        return find(root[x]);
    }
}

void union(int x, int y) { // O(N)
    x = find(x);
    y = find(y);

    root[y] = x; // set y's root to x's root
}

Optimization on Find / Union.

But there are two issues in the code above. If the depth of tree is 6, and to find that root node, we have to recursively go through 6 steps. Simply, why do we have to take 6 steps to find the root node? can we just make depth 1, but connected to all node! Yes! we can certainly! this method is called path compression.

Another issue would be union. Let’s assume I have trees A and B. A has depth (3), and B has depth (6), Then would it better to merge B into A or A into B? It’s better to merge tree that have lower depth to greater depth. For example, if we put A into B, then the depth of union tree doesn’t change, but if we union B to A, you will get +1 depth in resulting tree. So this can be managed by the concept of rank, which is similar to depth.

The below algorithm has path compression and union by rank applied.

struct UnionFind {
    vector<int> parent; // parent link
    vector<int> rank;   // depth information

    UnionFind(int n): parent(n), rank(n, 0) {
        // set all element pointing to itself.
        for(int i = 0; i < n; i++)
            parent[i] = i; // make-set
    }

    int find(int x) {
        if (parent[x] == x)
        return x;
    }

    int merge(int x, int y) {
        int x_set = find(x);
        int y_set = find(y);

        if (x_set == y_set)
            return x_set

        if (rank[x_set] < rank[y_set]){
            return parent[xset] = yset;
        } else {
            if (rank[x_set] == rank[y_set])
                rank[x_set]++
            return parent[y_set] = x_set;
        }
    }
}

Time Complexity

Let’s look at the time complexity by the operation. makeSet is O(N) when n element is given. Find Operation is similar, but the worst case scenario it’s O(N). Since Union uses Find operation, it takes about O(N). Overall, it becomes O(N) times, but constant time O(a(n)) if path compression & union by rank. (a=> ackerman function).

Resource

• Union-Find