C++ Day 1: Leetcode Blind 75

Alright, now this is going to be a fun journey. I am learning C++ right now. I have previously worked professionally using Java, and Golang. I am learning C++ this time as most popular databases and systems are written in C++. So hold on tight, and embark on this journey with me!

Two Sum — UNORDERED_MAP

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        unordered_map<int, int> map;

        for (int i=0; i<nums.size(); i++){
            if map.find(target - nums[i]) != map.end()){
                result.push_back(i);
                result.push_back(map[target-nums[i]]);
                return result;
            }
            map[nums[i]] = i;
        }

        return result;
    }
};

1. vector<int> This is like ArrayList
2. In C++ we have ordered_map and unordered_map

map is usually implemented as a binary search tree, therefore iterators would give you sorted keys already.

If you don’t care about the order you may use unordered_map (from c++11 or boost) which would give you some speed in trade of the order.

3. map.find() != map.end() : We use iterators as output of find(), search() etc.

4. result.push_back(i) : Note the function name. We are now using _ as separators.

Best Time to Buy and Sell Stock — INT_MAX

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxVal = 0;
        int minVal = INT_MAX;

        for (int i = 0; i< prices.size(); i++){
            minVal = min(minVal, prices[i]);
            maxVal = max(maxVal, prices[i] - minVal);
        }

        return maxVal;
    }

};

1. INT_MAX: previously we used to have math.MaxInt etc. In C++, we don’t call with the prefix math.
2. min(): We don’t have math. for min and max as well.

Contains Duplicate — Set

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return nums.size() > set<int>(nums.begin(), nums.end()).size() ;
    }
};

1. set<int>(nums.begin(), nums.end()): This is a hack to init set with the nums vector.
2. size(): every data structure will have .size() instead of .length()
3. vector<int>& nums: We are passing the argument as a reference.

Const Reference: If you don’t want the function to modify the vector but still want to avoid copying, you can use a const reference: const vector<int>& nums. This allows the function to read the vector without copying it, while preventing modifications.

Product of array except for self — Vector

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        
        vector<int> fromBegin(n);
        fromBegin[0] = 1;
        
        vector<int> fromLast(n);
        fromLast[n - 1] = 1;

        for (int i = 1; i < n; i++) {
            fromBegin[i] = fromBegin[i - 1] * nums[i - 1];
        }
        
        for (int i = n - 2; i >= 0; i--) {
            fromLast[i] = fromLast[i + 1] * nums[i + 1];
        }

        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            result[i] = fromBegin[i] * fromLast[i];
        }

        return result;
    }
};

1. vector<int> arr(n): Init vector with a fixed size.

Linked List Cycle — Class

struct ListNode{
    int val;
    ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

bool hasCycle(ListNode *head) {
    ListNode *slow_pointer = head, *fast_pointer = head;
    while (fast_pointer != nullptr && fast_pointer->next != nullptr) {
        slow_pointer = slow_pointer->next;
        fast_pointer = fast_pointer->next->next;
        if (slow_pointer == fast_pointer) {
            return true;
        }
    }
    return false;
}

1. ListNode(int x): val(x), next(NULL) {}: Initialize variable before constructor call

val(x): This is an initializer list, which is a feature of C++ that allows you to initialize member variables before the constructor body executes. Here, it sets the val member of the ListNode to the value of x.

next(NULL): This initializes the next pointer to NULL, meaning that by default, a new node does not point to any other node.

2. What is the difference between fn(vector<int>& a) and fn(ListNode *node)

When comparing fn(ListNode *node) and fn(ListNode& node), both functions allow modification of a linked list node, but they handle parameters differently: one uses pointers and the other uses references. Here are the key differences:

Word Break — Map

bool wordBreak(string s, unordered_set<string> &dict) {
        if(dict.size()==0) return false;
        
        vector<bool> dp(s.size()+1,false);
        dp[0]=true;
        
        for(int i=1;i<=s.size();i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                if(dp[j])
                {
                    string word = s.substr(j,i-j);
                    if(dict.find(word)!= dict.end())
                    {
                        dp[i]=true;
                        break; //next i
                    }
                }
            }
        }
        
        return dp[s.size()];
 }

1. Both the syntax is correct: Fn(unordered_set<string> &dict) vs Fn(unordered_set<string>& dict)
2. Both this syntax is correct: Fn(unordered_set<string>* dict) vs Fn(unordered_set<string> *dict)

3. vector<bool> dp(s.size()+1,false); initialize with all the elements as false.

4. Always remember to add ; at the end.

5. s.substr(j,i-j); we call substring from the original string directly. It is a function of the string object.

Clone Graph — DFS

class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node== nullptr) return node;

        unordered_map<Node*, Node*> mp;
        dfs(node, mp);

        return mp[node];
    }
private:
    void dfs(Node *node, unordered_map<Node*, Node*> &mp) {
        auto copy = new Node(node -> val);
        mp[node] = copy;
        for (auto &neighbor: node -> neighbors) {
            if (!mp.count(neighbor)) {
                dfs(neighbor, mp);
            }
            copy->neighbors.push_back(mp[neighbor]);
        }
    }
};

1. vector<Node*> neighbors; we see that * is put at the end of type. In Golang, it was in the beginning Neighbors []*Node
2. unordered_map<Node*, Node*> mp; This is used instead of the Golang code mp:= make(map[*Node]*Node)
3. if (!mp.count(neighbor)): This is hack instead of mp.find() != mp.end()

Maximum Depth of Binary Tree — Tree

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (root == nullptr)
            return 0;
        int lh = maxDepth(root->left);
        int rh = maxDepth(root->right);
        return max(lh, rh) + 1;
    }
};

1. If (root==NULL) vs if (root == nullptr)

Top K Frequent Elements — Heap

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> map;
        for(int num : nums){
            map[num]++;
        }
        
        vector<int> res;
        // pair<first, second>: first is frequency,  second is number
        priority_queue<pair<int,int>> pq; 
        for(auto it = map.begin(); it != map.end(); it++){
            pq.push(make_pair(it->second, it->first));
            if(pq.size() > (int)map.size() - k){
                res.push_back(pq.top().second);
                pq.pop();
            }
        }
        return res;
    }
};

1. pair<int, int>: Oh, I missed this class.
2. priority_queue<pair<int,int>> pq: This is quite straightforward.
3. pq.push(), pq.pop(): API for queue

Merge Intervals — Sort

class Solution {
public:
     vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size()<=1) return intervals;

        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> output;
        output.push_back(intervals[0]);
        for(int i=1; i<intervals.size(); i++) {
            if(output.back()[1] >= intervals[i][0]) 
                output.back()[1] = max(output.back()[1] , intervals[i][1]);
            else 
                output.push_back(intervals[i]); 
        }
        return output;
    }
};

1. sort(intervals.begin(), intervals.end()): Sorts a vector

Conclusion

I hope this is of some use to someone. Subscribe to us for more related content.