# 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)
{
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://ahampriyanshu.com/posts/experimenting-with-cp/striver/180/2022-08-01-strivers-sde-sheet-top-coding-interview-problems-day-2-array-ii/", "fetch_time": 1674938369000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2023-06/segments/1674764499654.54/warc/CC-MAIN-20230128184907-20230128214907-00496.warc.gz", "warc_record_offset": 108087069, "warc_record_length": 3394, "token_count": 641, "char_count": 1871, "score": 3.609375, "int_score": 4, "crawl": "CC-MAIN-2023-06", "snapshot_type": "latest", "language": "en", "language_score": 0.39351925253868103, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00052-of-00064.parquet"}