# Array II | Striver’s SDE Sheet

Posted on Dec 25, 2020

## Problem 1

### Brute

This question has been updated on leetcode with newer constraints : -2^31 <= matrix[i][j] <= 2^31 - 1. Hence, we will have to use some extra space.

``````class Solution {
public:

void nullify(vector<vector<int>>& matrix, int a, int b, int r, int c){

for (int i = 0; i < a; i++)
{
matrix[i][c] = 0;
}

for (int i = 0; i < b; i++)
{
matrix[r][i] = 0;
}
}

void setZeroes(vector<vector<int>>& matrix) {

int m = matrix.size();
int n = matrix[0].size();
vector<pair<int, int>> indexes;
pair<int, int> index;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == 0)
{
index.first = i;
index.second = j;
indexes.push_back(index);
}
}
}

for (auto e : indexes)
{
nullify(matrix, m, n, e.first, e.second);
}

}
};
``````

### Optimal

``````class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int rows = matrix.size();
int cols = matrix[0].size();
bool zeroth_col = false;
for (int j = 0; j < rows; ++j) {
if (matrix[j][0] == 0) zeroth_col = true;
for (int i = 1; i < cols; ++i) {
if (matrix[j][i] == 0) {
matrix[j][0] = matrix[0][i] = 0;
}
}
}
for (int j = rows - 1; j >= 0; --j) {
for (int i = cols - 1; i > 0; --i) {
if (matrix[j][0] == 0 || matrix[0][i] == 0) matrix[j][i] = 0;
}
if (zeroth_col) matrix[j][0] = 0;
}
}
};
``````

## Problem 5

### Brute

This question has been updated on leetcode with newer constraints : -2^31 <= matrix[i][j] <= 2^31 - 1. Hence, we will have to use some extra space.

### Optimal

• In this approach, we will iterate over the array and store the minimun value & the maximum profit in seperate variables.

Time Complexity: \$ O(n) \$

Auxiliary Space: \$ O(1) \$

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
int buy = INT_MAX, n =  prices.size(), profit = 0;
for (auto price : prices)
{