# Striver SDE Sheet Solutions [Day 1]

Striver SDE Sheet Solutions [Day 1]: In this post, we will provide solutions for Day 1 striver sde sheet.

In this post, we will provide solutions for Day 1 striver sde sheet.

## 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());
}
};

```
In this program, we just coded the algorithm for next permutation given by Narayana Pandita.

### 4. Maximum Subarray

In this question, we have to return the maximum subarray sum.
```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;
}
```
I want to update you about the Sale. If you purchase a coding ninjas course today, you shall get a flat 40% discount (30% Early Bird + 10% from my side) on the course. [course]