Striver SDE Sheet Solutions | Day 1

In this post we will provide solutions of striver sde sheet day 1 in c++. Each code is successfully accepted at leetcode.

Striver SDE Sheet Solutions Day 1: Arrays

1. Set Matrix Zeroes

class Solution {
public:
    void setZeroes(vector<vector <int>>& matrix) {
        int r=matrix.size(),c=matrix[0].size();
        vector<int> rows(r,0),cols(c,0);
        
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(matrix[i][j]==0)
                {
                    rows[i]=1;
                    cols[j]=1;
                }
            }
        }
        
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                if(cols[j]==1||rows[i]==1)
                {
                    matrix[i][j]=0;
                }
            }
        }
        
    }
};

2. Pascal’s Triangle

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans(numRows);
        for(int i=0;i<numRows;i++)
        {
            ans[i].resize(i+1,1);
            for(int j=0;j<=i;j++)
            {
                if(j==0||j==i) continue;
                ans[i][j]=ans[i-1][j-1]+ans[i-1][j];
            }
        }
        return ans;
    }
};

3. Next Permutation in C++

 In this program, we are going to make a c++ program for next permutation.

Credits: Striver SDE Sheet

A man named Narayana Pandita presented the following algorithm to solve the next permutation problem in the 14th century.

1. Find the largest index “ind” such that nums[ind]<nums[ind+1]. If there is no such index exist just reverse the array and return.
2. Find the largest index j>ind such that nums[ind]<nums[j].
3. Swap (nums[ind],nums[j]);
4. Reverse the subarray on the right side of nums[ind]. {reverse(nums.begin()+ind+1,nums.end());}

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n=nums.size();
        int ind=-1;
        for(int i=n-2;i>=0;i--)
        {
            if(nums[i]<nums[i+1])
            {
                ind=i;
                break;
            }
        }
        
        if(ind==-1) {
            reverse(nums.begin(),nums.end());
            return;
        }
        
        for(int j=n-1;j>ind;j--)
        {
            if(nums[j]>nums[ind])
            {
                swap(nums[j],nums[ind]);
                break;
            }
        }
       reverse(nums.begin()+ind+1,nums.end());
    }
};

4. Maximum Subarray

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int curr=0,ans=INT_MIN;
        
        for(auto it:nums)
        {
            curr+=it;
            ans=max(ans,curr);
            
            if(curr<0)
                curr=0;
        }
        return ans;
        
    }
};

5. Sort 0,1 and 2

void sortColors(vector<int>& nums) {
        int i=0,j=0,k=nums.size()-1;
        
        while(j<=k)
        {
            if(nums[j]==1) j++;
            else
                if(nums[j]==0) swap(nums[i++],nums[j++]);
            else
                if(nums[j]==2) swap(nums[k--],nums[j]);
        }
        
    }

6. Best Time to Buy and Sell Stock

int maxProfit(vector<int>& prices) {
        int mn=prices[0],ans=0;
        
        for(auto it:prices)
        {
            ans=max(ans,it-mn);
            mn=min(it,mn);
        }
        return ans;
    }