Day 9 (30 Days of Code)

8 July 2023

Today I solved 3 Leetcode problems.

1. Contains Duplicate II

   My approach:

   This question is very similar to one I did just yesterday and in this as well the best solution is achieved using Hashmap which gives us the time complexity of O(n).

   My solution:

    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int,int> map;
   
            for(int i=0;i<nums.size();i++){
                if(map.count(nums[i])>0){
                    if(abs(map[nums[i]]-i)<=k){
                        return true;
                    }
                }
                map[nums[i]] = i;
            }
            return false;
        }
    };
   

2. Implement Stack using Queues

   My approach:

   I was trying to figure out the solution in just O(1) which I realized is not possible so I simply used one queue and did the push function in O(n) time which made other operations in O(1) time.

   My solution:

    class MyStack {
    public:
   
        queue<int> output;
   
        MyStack() {
   
        }
   
        void push(int x) {
            int size = output.size();
            output.push(x);
            while(size>0){
                output.push(output.front());
                output.pop();
                size--;
            }
        }
   
        int pop() {
   
            int ans = output.front();
            output.pop();
            return ans;
   
        }
   
        int top() {
            return output.front();
        }
   
        bool empty() {
            return output.empty();
        }
    };
   

3. Invert Binary Tree

   My approach:

   This was an easy question as long as you understand that you just have to swap to a left and right child in each node. This can easily be done using recursion.

   My solution:

    class Solution {
    public:
        TreeNode* invertTree(TreeNode* root) {
            if(root==NULL){
                return root;
            }
            if(root->left==NULL && root->right==NULL){
                return root;
            }
   
            TreeNode* left = invertTree(root->left);
            TreeNode* right = invertTree(root->right);
   
            root->left = right;
            root->right = left;
            return root;
        }
    };