Commitea78926

authored

Merge pull requestneetcode-gh#1970 from Maunish-dave/main

Create 0054-brick-wall.cpp, 0122-best-time-to-buy-and-sell-stock-ii.cpp, Create 1963-minimum-number-of-swaps.cpp

2 parents78c6e36 +ad1d128 commitea78926Copy full SHA for ea78926

File tree

+110

-0

lines changed

+110

-0

lines changed

Lines changed: 42 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,42 @@`
	`1`	`+/*`
	`2`	`+ Approach:`
	`3`	`+ Store the count of the end of the brick for each row in a hash and keep the track`
	`4`	`+ of max number of brick that ends at same position, return rows - max.`
	`5`	`+`
	`6`	`+ Time complexity : O(n x m)`
	`7`	`+ Space complexity: O(n x m)`
	`8`	`+`
	`9`	`+ n is number of rows, m is max brick in a row.`
	`10`	`+*/`
	`11`	`+`
	`12`	`+classSolution {`
	`13`	`+public:`
	`14`	`+intleastBricks(vector<vector<int>>& wall) {`
	`15`	`+`
	`16`	`+ map<int,int> end_count;`
	`17`	`+int end_of_brick, max_end_count=0;`
	`18`	`+`
	`19`	`+int rows = wall.size(),cols;`
	`20`	`+`
	`21`	`+for(int i =0;i<rows;i++){`
	`22`	`+ end_of_brick =0;`
	`23`	`+`
	`24`	`+// '-1' because edge of the wall is not considered`
	`25`	`+ cols = wall[i].size() -1;`
	`26`	`+for(int j =0;j<cols;j++){`
	`27`	`+ end_of_brick += wall[i][j];`
	`28`	`+`
	`29`	`+if(end_count.find(end_of_brick)!=end_count.end())`
	`30`	`+ {`
	`31`	`+ end_count[end_of_brick]++;`
	`32`	`+ }`
	`33`	`+else{`
	`34`	`+ end_count[end_of_brick] =1;`
	`35`	`+ }`
	`36`	`+ max_end_count =max(max_end_count,end_count[end_of_brick]);`
	`37`	`+ }`
	`38`	`+ }`
	`39`	`+`
	`40`	`+return rows - max_end_count;`
	`41`	`+ }`
	`42`	`+};`

Lines changed: 22 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,22 @@`
	`1`	`+/*`
	`2`	`+ Approach:`
	`3`	`+ If stock price is going up tomorrow just buy it today and sell it tomorrow.`
	`4`	`+`
	`5`	`+ Time complexity : O(n)`
	`6`	`+ Space complexity: O(1)`
	`7`	`+`
	`8`	`+ n is number of days.`
	`9`	`+*/`
	`10`	`+`
	`11`	`+classSolution {`
	`12`	`+public:`
	`13`	`+intmaxProfit(vector<int>& prices) {`
	`14`	`+int ans =0;`
	`15`	`+`
	`16`	`+// look into the next day and if you are making profit just buy it today.`
	`17`	`+for(int i =1;i<prices.size();i++){`
	`18`	`+if(prices[i]>prices[i-1]) ans += (prices[i]-prices[i-1]);`
	`19`	`+ }`
	`20`	`+return ans;`
	`21`	`+ }`
	`22`	`+};`

Lines changed: 46 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,46 @@`
	`1`	`+/*`
	`2`	`+ Approach:`
	`3`	`+ Just check which '[' brackes are wrongly placed correct that bracket.`
	`4`	`+ use stack to keep track of bracket`
	`5`	`+`
	`6`	`+ Time complexity : O(n)`
	`7`	`+ Space complexity: O(n)`
	`8`	`+`
	`9`	`+ n is length of the string.`
	`10`	`+*/`
	`11`	`+`
	`12`	`+classSolution {`
	`13`	`+public:`
	`14`	`+intminSwaps(string s) {`
	`15`	`+`
	`16`	`+int answer=0;`
	`17`	`+`
	`18`	`+ stack<char> stc;`
	`19`	`+ stc.push(']');`
	`20`	`+`
	`21`	`+int n = s.size();`
	`22`	`+`
	`23`	`+for(int i=0;i<n;i++){`
	`24`	`+char top = stc.top();`
	`25`	`+`
	`26`	`+if(s[i]==']'){`
	`27`	`+`
	`28`	`+// is the '[' bracket correctly placed`
	`29`	`+// if yes then just pop`
	`30`	`+if (top=='[') {`
	`31`	`+ stc.pop();`
	`32`	`+ }`
	`33`	`+// if '[' is not correctly placed`
	`34`	`+// then correct it (push '[')`
	`35`	`+else{`
	`36`	`+ stc.push('[');`
	`37`	`+ answer++;`
	`38`	`+ }`
	`39`	`+ }`
	`40`	`+else{`
	`41`	`+ stc.push('[');`
	`42`	`+ }`
	`43`	`+ }`
	`44`	`+return answer;`
	`45`	`+ }`
	`46`	`+};`

Comments

(0)