Leetcode 231, 232, 234, 242

9 July 2023

Today was only focussed on DSA. I solved 4 Leetcode questions and I have started learning Dynamic Programming.

My approach:

At first, I did this question using a general while loop which was easy and had a linear time complexity. However, there exists a function named log2() which made the question too easy and time complexity became O(logn).

My solution:

Using loop

  class Solution {
  public:
      bool isPowerOfTwo(int n) {
          if(n<=0){
              return false;
          }

          while(n%2==0){
              n = n/2;
          }

          if(n==1){
              return true;
          }
          return false;
      }
  };

Using log2() from STL

  class Solution {
  public:
      bool isPowerOfTwo(int n) {
          if(n<=0){
              return false;
          }
          if(n!=1 && n%2==1 ){
              return false;
          }
          int x = log2(n);

          if(pow(2,x)==n){
              return true;
          }
          return false;    
      }
  };

Implement Queue using Stacks

My approach:

This question was easy as we are allowed to use 2 stacks. The push function takes O(n) time but other functions takes O(1) time to implement.

My solution:

 class MyQueue {
 public:
     stack<int> s1;
     stack<int> s2;
     MyQueue() {

     }

     void push(int x) {
         if(s1.size()==0){
             s1.push(x);
         }else{
             int sz = s1.size();
             while(sz--){
                 s2.push(s1.top());
                 s1.pop();
             }
             s1.push(x);
             sz = s2.size();
             while(sz--){
                 s1.push(s2.top());
                 s2.pop();
             }
         }
     }

     int pop() {
         int ans = s1.top();
         s1.pop();
         return ans;
     }

     int peek() {
         return s1.top();
     }

     bool empty() {
         return !s1.size();
     }
 };

Palindrome Linked List

My approach:

My very first approach was to reverse the whole list and then compare it to the existing list which was correct but then I realised we don't have to reverse the whole list. What we can do is we can just simply reverse the end half of the list and compare it to the first half of the list.

My solution:

```cpp class Solution { public: int length(ListNode* head){ if(head==NULL){ return 0; } return 1+length(head->next); }

ListNode reverse(ListNode head){ if(head==NULL || head->next==NULL){ return head; }

ListNode reverseHead = reverse(head->next); head->next->next = head; head->next = NULL; return reverseHead; } bool isPalindrome(ListNode head) { int l = length(head);

int mid = (l-1)/2;

ListNode temp = head; for(int i=0;inext; } ListNode newHead = temp->next; temp->next = NULL;

newHead = reverse(newHead);

while(newHead!=NULL){ if(head->val!=newHead->val){ return false; } head = head->next; newHead = newHead->next; }

return true; } };



.

* [Valid Anagram](https://leetcode.com/problems/valid-anagram/)

    My approach:


My very approach was to use sorting and then compare them. This solution gave me a time complexity of O(nlogn) but I also knew we could do this using a Hashmap but I wasn't sure how so I looked at the hint and then came up with the O(n) time solution.

My solution:

* Using sort() method \[O(nlogn)\]


```cpp
class Solution {
public:
    bool isAnagram(string s, string t) {

        if(s.length()!=t.length()){
            return false;
        }

        sort(s.begin(),s.end());
        sort(t.begin(), t.end());

        return s==t;

};

Using Hashmap [O(n)]

class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<int,int> ourmap;
        vector<char> keyChar;
        for(int i=0 ; s[i]!='\0' ; i++){
            if(ourmap.count(s[i])>0){
                ourmap[s[i]]++;
                continue;
            }
            ourmap[s[i]] = 1;
            keyChar.push_back(s[i]);
        }

        for(int i=0 ; t[i]!='\0' ; i++){
            if(ourmap.count(t[i])>0){
                ourmap[t[i]]--;
            }
        }

        for(int i=0;i<keyChar.size();i++){
            if(ourmap[keyChar[i]]!=0){
                return false;
            }
        }

        return true;
    }
};

Day 10 (30 Days of Code)

9 July 2023