Day 2 Array | Striver 180 | takeUforward
Post
Cancel

# Day 2 Array | Striver 180 | takeUforward

## 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 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)$

1 2 3 4 5 6 7 8 9 10 11 12 class Solution { public: int maxProfit(vector<int>& prices) { int buy = INT_MAX, n = prices.size(), profit = 0; for (auto price : prices) { if (price < buy) buy = price; if (price - buy > profit) profit = price - buy; } return profit; } };