DSA_Questions_Solutions.

SOLTION 1:

FIND DUPLICATE NUMBER.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int n=nums.size();int ans=0;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            if(nums[i]==nums[i+1]){
                ans=nums[i];
            }
        }
        return ans;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOUTION 2:

SORT COLOR.

class Solution {
public:
    void sortColors(vector<int>& nums) {
        // sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n;i++){
            for(int j=0;j<n-i-1;j++){
                if(nums[j] > nums[j+1]){
                    swap(nums[j],nums[j+1]);
                }
            }
        }
    }
};

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 3: 

REMOVE DUPLICATES FROM SORTED ARRAY.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n=nums.size();
        int j=0;
        for(int i=0;i<n;i++){
            if(nums[i]!=nums[j]){
                j++;
                nums[j]=nums[i];
            }
        }
        return j+1;
    }
};

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 4:

SET MATRIX ZERO.

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
       int m=matrix.size();
       int n=matrix[0].size();
       int x=1;
       int y=1;
       for(int j=0;j<n;j++){
           if(matrix[0][j]==0)x=0;
       }
       for(int i=0;i<m;i++){
           if(matrix[i][0]==0)y=0;
       }
       for(int i=1;i<m;i++){
           for(int j=1;j<n;j++){
               if(matrix[i][j]==0){
                   matrix[0][j]=0;
                   matrix[i][0]=0;
               }
           }
       }
       for(int j=1;j<n;j++){
           if(matrix[0][j]==0){
               for(int i=1;i<m;i++){
                   matrix[i][j]=0;
               }
           }
       }
       for(int i=1;i<m;i++){
           if(matrix[i][0]==0){
               for(int j=1;j<n;j++){
                   matrix[i][j]=0;
               }
           }
       }
       if(y==0){
           for(int j=0;j<n;j++){
               matrix[0][j]=0;
           }
       }
       if(x==0){
           for(int i=0;i<m;i++){
               matrix[i][0]=0;
           }
       }
    }
};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 5:

MOVE ZEROES.

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int nonZero=0;
        for(int i=0;i<nums.size();i++){
            if(nums[i] != 0){
                swap(nums[i],nums[nonZero]);
                nonZero++;
            }
        }
    }
};

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 6:

BUY AND SELL (1) .

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int mini=INT_MAX;
        int max_profit=0;
        for(int i=0;i<prices.size();i++){
        if(prices[i] < mini){
            mini=prices[i];
        }
        else if(prices[i]-mini>max_profit){
            max_profit=prices[i]-mini;
        }
    }
     return max_profit;
    }
};

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 7:

CHOCOLATE DISTRIBUTION PROBLEM .

class Solution{
public:
long long findMinDiff(vector<long long> a, long long n, long long m){
        
        sort(a.begin(),a.end());
        int i=0;
        int j=i+m-1;
        long long int mini=INT_MAX;
        while(j < n){
            long long int diff = a[j] - a[i];
            mini=min(diff,mini);
            i++;j++;
        }
        return mini;
    } 
};

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 8:

TWO SUM .

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(nums[i]+nums[j]==target){
                    return {i,j};
                }
            }
        }
        return {};
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 9:

BUY AND SELL STOCK (II) .

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int total_profit=0;
        if(n<=1){
            return 0;
        }
        for(int i=1;i<n;i++){
            if(prices[i] > prices[i-1]){
                total_profit += prices[i] - prices[i-1];
            }
        }
        return total_profit;
    }
};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 10: 

FIND ALL DUPLICATES IN ARRAY .

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        int n=nums.size()-1;
        vector<int>ans;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            if(nums[i] == nums[i+1]){
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 11:

SUBARRAY SUMS DIVISIBLE BY K .

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int sum=0;
        int ans=0;
        unordered_map<int,int> mp;
        mp[0]++;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            int rem=sum%k;
            if(rem<0)
            {
                rem+=k;
            }
            ans+=mp[rem];
            mp[rem]++;
        }
        return ans;
    }
};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 12:

MERGE SORTED ARRAY .

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 

          // USING TWO POINTERS
   {
        int i=m-1;
        int j=n-1;
        int k=m+n-1;
        while( j >= 0 ){
            if( i >= 0 && nums1[i] > nums2[j]){
                nums1[k--]=nums1[i--];
            }
            else{
                nums1[k--]=nums2[j--];
            }
        }
    }

           // USING STL

    //    {
    //     int n=nums.size();
    //     for(int i=m,j=0;j<n;j++){
    //         nums1[i++]=nums2[j];
    //     }
    //     sort(nums1.begin(),nums1.end());
    // }

};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 13:

CONTAINER WITH MOST WATER .

class Solution {
public:
    int maxArea(vector<int>& height) {
        int area=0;
        int maxarea=0;
        int l=0;
        int r=height.size()-1;
        while(l < r){
            area=min(height[l],height[r])*(r-l);
            if(area > maxarea){
                maxarea=area;
            }
            if(height[l] < height[r]){
                l++;
            }
            else{
                r--;
            }
        }
        return maxarea;
    }  
};

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 14:

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n=cardPoints.size();
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=cardPoints[i];
        }
         int ans;
        int window=0;
        if(n==k){
            return sum;
        }
        for(int i=0;i<n-k-1;i++){
            window+=cardPoints[i];
        }
        for(int i=n-k-1;i<n;i++){
            window+=cardPoints[i];
            ans=max(ans,sum-window);
            window-=cardPoints[i-(n-k-1)];
        }
        return ans;
    }
};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 15: 

ALL UNIQUE PERMUTATION OF AN ARRAY.

class Solution {
public:
 set<vector<int>> St;
   vector<vector<int>> ans;
       void helper(int ind , int n, vector<int> arr){
            if(ind == n){
               St.insert(arr);
          }
          else{
          for(int i=ind; i<n; i++){
             swap(arr[ind], arr[i]);
             helper(ind+1, n, arr);
             swap(arr[ind], arr[i]);
          }
        }
      }
vector<vector<int>> uniquePerms(vector<int> &arr ,int n){
         helper(0,n,arr);
           for(auto x : St)
            ans.push_back(x);
         return ans;
    }
};

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 16:

MAXIMUM SUBARRAY SUM (KADANE'S ALGO).

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxsum=INT_MIN;
        int currentsum=0;
        for(int i=0;i<nums.size();i++){
            currentsum+=nums[i];
            if(currentsum > maxsum)
            {
                maxsum=max(currentsum,maxsum);
            }
            if(currentsum < 0){
                currentsum=0;
            }
        }
        return maxsum;   
    }
};

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 17:

ROTATE ARRAY . 

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 18:

REMOVE ELEMENT .

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int index = 0;
        for(int i = 0; i< nums.size(); i++){
            if(nums[i] != val){
                nums[index] = nums[i];
                index++;
            }
        }
        return index;
    }
};

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 20 : 

MERGE TWO SORTED LISTS . 

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL){
            return list2;
        }
        if(list2==NULL){
            return list1;
        }
        if(list1->val <= list2->val){
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 21 :

REVERSE A LINKED LIST . 

/**
 * 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* reverseList(ListNode* head) {
        ListNode* prev=NULL;
        ListNode* curr=head;
        ListNode* next_node;
        while(curr!=NULL)
        {
            next_node=curr->next;
            curr->next=prev;
            prev=curr;
            curr=next_node;
        }
        return prev;
    }
};

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 22 :

DETECT LOOP IN LINKED LIST . 

class Solution
{
    public:
    //Function to check if the linked list has a loop.
    bool detectLoop(Node* head)
    {
        // your code here
        Node* slow=head;
        Node *fast=head;
        while(fast!=NULL && fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast){
                return 1;
            }
        }
        return 0;
    }
};

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 23:

REMOVE LINKED LISTS ELEMENTS . 

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* temp=new ListNode(0);
        temp->next=head;
        ListNode* curr=temp;
        while(curr->next!=NULL){
            if(curr->next->val == val)curr->next=curr->next->next;
            else curr=curr->next;
        }
        return temp->next;
    }
};

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 24 : 

CONVERT BINARY NUMBER IN LINKED LIST ELEMENT TO INTEGER . 

class Solution {
public:
    ListNode *reverse(ListNode *head){
        ListNode *prev=NULL;
        ListNode *curr=head;
        ListNode *next_node;
        while(curr!=NULL){
            next_node=curr->next;
            curr->next=prev;
            prev=curr;
            curr=next_node;
        }
        head=prev;
        return head;
    }
    int getDecimalValue(ListNode* head) {
        ListNode *temp=reverse(head);
        int i=0,total=0;
        while(temp!=NULL){
            int x=temp->val;
            total=total+pow(2,i)*x;
            i++;
            temp=temp->next;
        }
        return total;
    }
};

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 25:

INTERSECTION OF TWO LIKED LISTS . 

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB){
            return NULL;
        }
        ListNode *temp1=headA;
        ListNode *temp2=headB;
        while(temp1!=temp2){
            if(temp1==NULL){
                temp1=headA;
            }
            else{
                temp1=temp1->next;
            }
            if(temp2==NULL){
                temp2=headB;
            }
            else{
                temp2=temp2->next;
            }
        }
        return temp1;
    }
};

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 26 : 

DELETE NODES HAVING GREATER VALUE ON RIGHT . 

class Solution
{
    public:
    
    Node *reverse(Node *head)
    {
        Node *prev=NULL;
        Node *curr=head;
        while(curr!=NULL)
        {
            Node *next_node=curr->next;
            curr->next=prev;
            prev=curr;
            curr=next_node;
        }
        return prev;
    }
    
    Node *compute(Node *head)
    {
        head=reverse(head);
        Node *curr=head;
        int ma=head->data;
        Node *prev=head;
        head=head->next;
        while(head)
        {
            if(head->data >= ma)
            {
                ma=head->data;
                prev=head;
                head=head->next;
            }
            else
            {
                prev->next=head->next;
                head=prev->next;
            }
        }
        head=reverse(curr);
        return head;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 27 : 

PALINDROME LINKED LIST . 

class Solution {
public:
    
    ListNode *middle(ListNode *head){      
        ListNode *slow=head;
        ListNode *fast=head->next;
        while(fast!=NULL && fast->next!=NULL){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }

    ListNode *reverse(ListNode *head){
        ListNode* curr=head;
        ListNode *prev=NULL;
        while(curr!=NULL){
            ListNode *next_node=curr->next;
            curr->next=prev;
            prev=curr;
            curr=next_node;
        }
        return prev;
    }

    bool isPalindrome(ListNode* head) {
        if(head==NULL)
            return true;
        ListNode *mid=middle(head);
        ListNode *last=reverse(mid->next);
        ListNode *curr=head;
        while(last!=NULL){
            if(last->val!=curr->val)
                return false;
            last=last->next;
            curr=curr->next;
            
        }
        return true;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 28 : 

ADD TWO NUMBERS . 

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int d1 = (l1 != nullptr) ? l1->val : 0;
            int d2 = (l2 != nullptr) ? l2->val : 0;
            int sum = d1 + d2 + carry;
            int digit = sum % 10;
            carry = sum / 10;
            ListNode* newnode = new ListNode(digit);
            tail->next = newnode;
            tail = tail->next;
            l1 = (l1 != NULL) ? l1->next : NULL;
            l2 = (l2 != NULL) ? l2->next : NULL;
        }
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
        
    }
};

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 29 : 

REMOVE Nth NODE FROM END OF LIST . 

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;
        for (int i = 0; i <= n; i++) {
            first = first->next;
        }
        while (first != NULL) {
            first = first->next;
            second = second->next;
        }
        ListNode* temp = second->next;
        second->next = second->next->next;
        delete temp;
        return dummy->next;
    }
};

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 30 : 

FLATTENING A LINKED LIST (using queue) .

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
// A Linked List Node
struct Node
{
    int data;
    Node *next, *child;
};
 
// Helper function to create a new node with the given data and
// pushes it onto the list's front
void push(Node* &headRef, int data)
{
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    newNode->child = nullptr;
    headRef = newNode;
}
 
// Helper function to create a linked list with elements of a given vector
Node* createHorizontalList(vector<int> const &input)
{
    Node* head = nullptr;
    for (int i = input.size() - 1; i >= 0; i--) {
        push(head, input[i]);
    }
 
    return head;
}
 
// Function to convert a multilevel linked list into a singly linked list
void convertList(Node* const head)
{
    Node* curr = head;
    queue<Node*> q;
 
    // process all nodes
    while (curr)
    {
        // last node is reached
        if (curr->next == nullptr)
        {
            // dequeue the front node and set it as the next node of the current node
            curr->next = q.front();
            q.pop();
        }
 
        // if the current node has a child
        if (curr->child) {
            q.push(curr->child);
        }
 
        // advance the current node
        curr = curr->next;
    }
}
 
// Helper function to print a given linked list
void printList(Node* const head)
{
    Node* ptr = head;
    while (ptr)
    {
        cout << ptr->data <<" -> ";
        ptr = ptr->next;
    }
 
    cout << "nullptr" << endl;
}
 
int main()
{
    // create a multilevel linked list
    Node* head = createHorizontalList({1, 2, 3, 4, 5});
    head->child = createHorizontalList({6, 7});
    head->next->next->child = createHorizontalList({8, 9});
    head->child->next->child = createHorizontalList({10, 11});
    head->child->next->child->child = createHorizontalList({12});
 
    convertList(head);
    printList(head);
 
    return 0;
}

-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 31 : 

VALID PARENTHESIS

class Solution {
public:
    bool isValid(string s) {
        int n = s.length();
        stack<int> st;
        for (int i = 0; i < n; i++) {
            if (s[i] == '[' || s[i] == '(' || s[i] == '{') {
                st.push(s[i]);
            } else {
                if (st.empty()) {
                    return false;
                } else {
                    char c = st.top();
                    st.pop();
                    if ((s[i] == ')' && c == '(') ||
                        (s[i] == ']' && c == '[') ||
                        (s[i] == '}' && c == '{')) {
                        continue;
                    } else {
                        return false;
                    }
                }
            }
        }
        if (st.empty()) {
            return true;
        }
        return false;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

SOLUTION 32 :

BINARY TREE INORDER TRAVERSAL .

class Solution {
private:
    void traversal(TreeNode *root,vector<int>&arr){
        if(root==NULL){
            return ;
        }
        traversal(root->left,arr);
        arr.push_back(root->val);
        traversal(root->right,arr);
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>arr;
        traversal(root,arr);
        return arr;
    }
};

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------