DSA sheet notes

Day 1 Array-

Q.Set Matrix Zeroes

intution->add two arrays having row,columns

when matrix[i][j]==0 =>add row[i]=0,col[j]=0

2nd loop->check r[i] or col[0] then matrix[i][j]=0;

Q.Pascal's Triangle

intution->,1.resize the arr[i] to i+1,then add [i][0].[i][i]=1,

check i==0 if yes then continue else ->loop

ans[i][j] = ans[i-1][j-1] + ans[i-1][j]

Q.Kadane's Algorithms

Forget things=>1.if less sum then sum=0,only two variable(sum,maxSum) used,intiate maxSum=nums[0]

Javascript

Dark

    int maxSubArray(vector<int>& nums) {
        int sum=0;
        int max=nums[0];
        for(int i=0;i<nums.size();i++){
            if(sum+nums[i]>0){
                sum+=nums[i];
            }else{
                sum=0;
            }
              if(max<sum && sum!=0){
               max=sum;
            }if(max<nums[i]){
                  max=nums[i];
              }}
        return max;
    }

Q.Dutch National flag algorithm

use three variable ,l,m,h->

while(m<=h) having three cases if nums[mid] ->

if 0->swap(l,m) & l++,m++

IF 1 -> l++

IF 2->swap(h,m)h--;

Q.Rotate matrix

(Nested LOOP 1. i<col, 2 j<i )->swap(ar[i][j],ar[j][i]);

Loop i<col ->reverse(arr[i])

Q.Merge Overlapping Subintervals

did by own-->tem<int>(2){initially tem[0]=arr[0][0],tem[1]...}

1 Loop with two IF condition,

1. (tem[1]>=arr[i][0])then tem[1]=max(tem,arr[i 0)

2 .else--> push tem to ans , tem[0] = ar[i 0].tem[1]=ar[i 1]

Q.Rotate Matrix in ClockWise(Spiral transversal of matrix )

you need for variable is=0,ie=n-1,js=0,je=m-1

one while having 4 For loop

1. i=je+1 to js ->print(arr[is][j]);

2. i=ie+1 to is ->print(arr[i][je]);

3. i= je-1 to js-->print(arr[ie][i]

4. i =ie-1 to is-->print(arr[i][js]

Q.Search a 2D Matrix(binary search in 2D arr)

two variable l=0,h=m*n-1

while(l<=h), cal mid=l+(h-l)/2

things forget IF arr[mid/n][mid%n] > < == further operations

Q.Majority element(n/2)

moore's algorithm-->two variable count=, element=0;

Loop-->having 3 conditional statement

IF count==0--> elemnt=arr[i]

IF element ==arr[i]-->count++

ELSE-->count--;

After loop you get max element having n/2, for checking

1LOOP==>IF a[i]==elemnt ,val++ , after loop check is val >n/2

Q.Majority element (n/3)

moore's algorithms

same as before but just taken 4 variable cnt1=0,ele1=0,cnt2=0,ele=2

LOOP-->having 5 condional statement

IF ele1==num-->cnt1++, IF ele2-->cnt2++

IF cnt1==0-->ele1=num,cnt1=1,, IF cnt2-->ele2=num,cnt2=1l

ELSE==>cnt1--,cnt2--;

Rest is same for checking

Q.2sum

using Hashing-> unordered_Map<int,int>

check IF map[num-target]>=1==>push num,and num-target

Else-->map[num]=1

EXTRA SOLUTION

Javascript

Dark

  int check = mp[s-num];
        if(check>=1){
             tem[0]=min(num,s-num);
             tem[1]=max(num,s-num);
        }
        while(check--){
            ans.push_back(tem);
        }
        mp[num]++;
    
    }

Q.4sum

Most difficult solution

2Nested LOOP to get fix ,i j value then another while loop(l<h) where l=j+1,h=n-1

In while Loop there is three condition to check the sum

IF sum>target-->h--

IF sum<target-->l++

esle you find the sum now do further excution

Q.Largets subarray having 0 sum

we can do this in N , using map<int,int>

1LOOP having nested conditional statement on sum{ sum+=arr[i]}

IF sum==0, mx=i+1

else-->need to check if the sum is already present in MAP or not

IF yes-->mx=max(mx,i-map[sum])

IF No-->map[sum]=i

Q.Longest unique string

can be sloved easily by a map(we use vector of 256 as a char of map)

three variable l,r,mx

1LOOP-->having 1 IF condition to check if str[r] is already exist then change l= str[r]

IF(mp[str[i]]!=-1)-->L=max(L,map[str[r]]+1) {Forget things}

mx= max(mx, r-l+1),

map[str[r]]=r;,r++;

we get max uinque str len in max;

LINKED LIST

Reverse Linked List

three pointer->prev,curr,next

while(head!=null)-->next=curr->next

curr->next=prev

prev=curr

curr=next

TO BE CONTINUE

GREEDY ALORITHM

Q.N meeting in a room

A-->in that question need to return max no. meetings pos. can we done if only one room available

Intutution-->as we need to return pos , we create struct having start, end and postion

add values in it and sort it i. A.end<B.end{Forget things}

for auto num LOOP in meeting, with one condition

IF num.start>limit-->push in ans, & limit = num.end

Finally we get answers

Q.Maximum number of platform in the railway station

1st approach is about creating struct load data, sort it all and use priority queue(min heap)

I.e IF curr.arrival>pq.top-->push, departure , pop

ELSE-->push depature

Then the size of the pq is ans

2nd approach is just not able to understand

Javascript

Dark

 sort(at, at + n);
    sort(dt, dt + n);
     int count = 0;
    int i = 0, j = 0;
     while(i < n && j < n){
        if(at[i] <= dt[j])count++;            
        else j++;
        i++;
    }
    return count;

Q.Job Sequencing Problem

more tougher then other

we sort in decending order, i.e having more money will come first

find out the max deadline by 1LOOP-->maxi= max(maxi, i.deadline);

create an array of maxiarr(deadline,-1)

iterate through the data(2 nested loop)

1LOOP-->i to end

2LOOP-->j=i.deadline to j>0==>we check if maxiarr[j]==-1,then add there j, and break

that sit, while looping add profit variable to track it all and return it as ans;

Q.Fractional Knapsack

most dimaag ka dahi karne walaa

as always we need to sort but there we sort in some manner like-->

double a=(double)A.second/A.first; {most imp and forget things}

double b=(double)B.second/B.first;

return a>b;

Javascript

Dark

sort(items.begin(),items.end(),[](pair<int,int>&A,pair<int,int>&B){
       double a=(double)A.second/A.first;
       double b=(double)B.second/B.first;
       return a>b;
   });
    int curr=0;
    double profit=0;
    for(auto i:items){
       if(curr+i.first<=w){
           profit+=i.second;
           curr+=i.first;
       }else{
           int rem=w-curr;
           double pro= ((double)i.second/i.first)*(double)rem;
           profit+=pro;
           break;
       }
        
    }
    return profit;

Recurrsion

subset sum(very easy)

recurion function->

base case i>=arr.size()==>push sum into arr

call with same s value,ans i+1

call with s+arr[i], i+!

subset II

sort the data, ans call recursive function similar to above

same base case but in recursive call first call push_back data

then iterate to duplicate then call blank data

Javascript

Light

 		sub.push_back(arr[i]);
        recur(arr,ans,sub,i+1);
        sub.pop_back();
        while(i+1<arr.size() && arr[i]==arr[i+1])i++;
        recur(arr,ans,sub,i+1);

Combination Sum

difficult lil bit, when we allow to use duplicates

we minus arr[i] from target to check whether it is zero( Base case) ans push it

ibase case IF i>=size--> has inside IF t==0==> push subarr

after base case again IF t==0 => push subarr (IMP Forget thing)

1LOOP idx=i to n

IFarr[idx]>t then

push arr[idx], and recursion with idx(not idx+1)

pop back

Last Updated:

Summarize & share videos seamlessly