Rotating the Box | Brute Force | Optimal | Leetcode 1861 | codestorywithMIK

First 🎉❤

Was waiting 😊. Thank you for the consistency

finally solved the problem alone after 1hr, then saw video came

MIK sir, I feel so good I was able to solve this on my own. My problem solving is improving day by day. Thank you so much

Amazing ❤

sir,my solution

vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int m=box.size();
int n=box[0].size();
vector<vector<char>> rotated(n, vector<char>(m));

for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
if(box[i][j]=='#'){
int x=j+1;
while(x<n && box[i][x]=='.'){
x++;
}
if(x<=n && x>0)swap(box[i][j],box[i][x-1]);
}
}
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
rotated[i][j]=box[j][i];
}
}
for(auto &i:rotated){
reverse(i.begin(),i.end());
}
return rotated;
}

};

Bhaiya I solved it by myself it similar to the question rotate image towards right first I rotate the image towards right by transpose and then reverse all the rows and then just add the effect of gravity❤

I never expected to solve it by my own. Bt I did alhamdulillah. Thank you

public char[][]rotateTheBox(char[][]box){
int m=box.length,n=box[0].lenght;
char[][]ans=new char[n][m];
for(int i=0;i<m;++i)
for(int j=n-1,k=n-1;j>=0;--j){
ans[j][m-i-1]='.';
if(box[i][j]!='.'){
k=box[i][j]=='*'?j:k;
ans[k--][m-i-1]=box[i][j];
}
}
return ans;
}
🎉❤

can someone please tell the error in my code !!
Logic - Shifting stones to the right and then rotating the box


class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int m = box.size();
int n = box[0].size();

for(int i =0;i<m;i++){
vector<int>stones,empty;
stones.clear();
empty.clear();
for(int j =0;j<n;j++){
if(box[i][j]=='*'){
if(!empty.empty()&&!stones.empty()){
int x=empty.size()-1,y=0;
while(x>=0&&y<stones.size()){
swap(box[i][empty[x]],box[i][stones[y]]);
x--;
y++;
}
}
stones.clear();
empty.clear();
}else if( box[i][j]=='#'){
stones.push_back(j);
}else{
empty.push_back(j);
}
}
if(!empty.empty()&&!stones.empty()){
int x=empty.size()-1,y=0;
while(x>=0&&y<stones.size()){
swap(box[i][empty[x]],box[i][stones[y]]);
x--;
y++;
}
}
}
vector<vector<char>>ans(n,vector<char>(m));
for(int i =0;i<m;i++){
for(int j =0;j<n;j++){
ans[j][m-i-1]=box[i][j];
}
}
return ans;
}
};

I exracted each row and did Insertion sort with slight modification and then copied to the resultant matrix.
Time Complexity (m * n)
public void sort(char[]arr){
for(int i=1;i<arr.length;i++){
if(arr[i]=='*')continue;
for(int j=i-1;j>=0;j--){
if(arr[j]=='*')break;
if(arr[j]=='#' && arr[j+1]=='.'){
arr[j+1]='#';
arr[j]='.';
}
} }

Did it on my own 😢 But it seems easy problem

Jab se aapke videos dekhne lag gaya hu
Consistent rahne lag gaya hu
Coding me rum gaya hu
Logics sab samajh gaya hu
❤❤🎉🎉

You are my real hero , bhaiya 🙌🙌

class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int m = box.size(); // rows
int n = box[0].size(); // cols
vector<vector<char>> ans(n, vector<char>(m));
int j = m-1; // start from end column of ans matrix

for (auto& row : box) {
int r = n - 1;
int l = n - 1;

//Arrage the stones in each row of the given box
for (l; l >= 0; l--) {
if (row[l] == '*' || row[l] == '.' && row[r] != '.') r = l;
if (row[l] == '#' && row[r] == '.') {
swap(row[l], row[r]);
r--;
}
}

//First arranged row goes to last ans column
int i = 0;
for(char &c: row) {
ans[i++][j]= c;
}
j--;
}
return ans;
}
};
TC : O(2(m x n)) SC: O(1) excluding output array

No need to do transpose and reverse for the rotation just use res[j][m-i-1] = input [i][j], m = no of col

My Approach 👇
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int m=box.size();
int n=box[0].size();

for(auto &row:box){
int cntEmpty=0;
for(int j=n-1;j>=0;j--){
if(row[j]=='.')cntEmpty++;
else if(row[j]=='*')cntEmpty=0;
else{
if(cntEmpty==0)continue;
row[j+cntEmpty]='#';
row[j]='.';
}
}
}

vector<vector<char>>res;

for(int col=0;col<n;col++){
vector<char>temp;
for(int row=m-1;row>=0;row--){
temp.push_back(box[row][col]);
}
res.push_back(temp);
}

return res;
}
};

Plz upload binary tree concept video bro

Instead of doing transpose and then reversing it , we can play around the index and it will do the job :

int row = box.size();
int col = box[0].size();
vector<vector<char>> rotated(col , vector<char> (row));
//for copying elements
for(int i = 0 ; i < row ; i++) {
for(int j = 0 ; j < col ; j++) {
rotated[j][row - i - 1] = box[i][j];
}
}

I solved. Observed that transpose and reversing the array on my own. Then while simulating gravity I took a bit help of chatgpt. not completely. I was doing wrong updations on empty cell (`.`).

But later I also got to know that simulating gravity would not really require to do rotation first, I could simply move the # to right. So it's new thing to learn.

I really want to start the jan 1 with good news, but I was thinking how. I am simultaneously developing projects and solving problems. I alotted times. If you have some suggestions, can you reccommend ?

//In this I am shifting the stones first then rotating


//this is very similar to move zeros to end
void moveStones(vector<char>& row) {
int n = row.size();
int empty = n - 1;

for (int i = n - 1; i >= 0; --i) {
if (row[i] == '*') {
// move the empty pointer if u get a wall
empty = i - 1;
} else if (row[i] == '#') {
// move stone to the nearest empty spot
swap(row[i], row[empty]);
empty--;
}
// do nothing if it's empty space
}
}
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int m = box.size(),n=box[0].size();

for(auto &row : box){
moveStones(row);
}
vector<vector<char>>ans(n,vector<char>(m));

for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ans[i][j] = box[m-j-1][i];
}
}
return ans;
}

Thank God I got to know about your channel. I learn everyday from you ❤

Done with only single iteration
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
vector<vector<char>> ans(box[0].size(), vector<char>(box.size(), '.'));
for(int i=box.size()-1; i>=0; --i){
for(int j=box[0].size()-1, count=j; j>=0; --j){
if(box[i][j] == '#') ans[count--][box.size()-i-1] = '#';
else if(box[i][j] == '*') count = j, ans[count--][box.size()-i-1] = '*';
}
}
return ans;
}
};

Thanks a lot for details

I also thought of same optimized approach and then I thought reversing row does not make any sense and it is just increasing the time expense of solution. So I use the gravity simulation logic first and then apply the transpose logic directly without reversing rows.
Code (if someone wants to see the code) :

class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int n = box.size();
int m = box[0].size();

for (int i = 0; i < n; i++) {
int end = m - 1;
for (int start = m - 1; start >= 0; start--) {
if (box[i][start] == '*') {
end = start - 1;
}
else if (box[i][start] == '#') {
box[i][start] = '.';
box[i][end] = '#';
end--;
}
}
}

vector<vector<char>> ans(m, vector<char>(n, '.'));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
ans[j][n - i - 1] = box[i][j];
}
}

return ans;
}
};

sir plz make a video what to do as a fresher from 3rd tier cllg . how to make our cv shine within months plz . i get a lot of rejections because my cv nevr gets selected and i think most of us is facing the same issue i trust that u can help us u r genuine thank u for the videos and everything in advance

Mene to stack ka use karke isko solve kiya
I don't know mene itna kyu socha.

I was able to solve this using stack.

class Solution:
def rotateTheBox(self, box: List[List[str]]) -> List[List[str]]:

for i in range(len(box)):
stack = []
for j in range(len(box[i])-1, -1, -1):
if not stack and box[i][j] == ".":
stack.append((i,j))

if stack and box[i][j] == "*":
stack.pop()

if stack and box[i][j] == "#":
pos_i, pos_j = stack.pop()
box[pos_i][pos_j] = "#"
box[i][j] = "."
stack.append((pos_i,pos_j-1))


res = []

for col in range(len(box[0])):
new_col = []
for row in range(len(box)-1, -1, -1):
new_col.append(box[row][col])
res.append(new_col)

return res

Mik bhai does it in your way cook a story and turn it into code.Thank You Mzza Aagya❤
//Stone Count Method
class Solution {
public:
vector<vector<char>> rotateTheBox(vector<vector<char>>& box) {
int n = box.size();
int m = box[0].size();

vector<vector<char>>rotatedBox(m,vector<char>(n,'.'));

for(int i=0;i<n;i++){ //O(n)
int stoneCnt = 0; //for maintaining a stone count
for(int j=0;j<m;j++){ //O(m)
//If it is stone
if(box[i][j] == '#'){
//later we subtract it from current row number
//to reach at the position of top stone
stoneCnt++;
//push stone in rotated box
rotatedBox[j][n-1-i] = '#';
}
//if it is empty
else if(box[i][j] == '.'){
//check if we encounter any stone then remove top stone and place at
//current empty position
if(stoneCnt > 0){
rotatedBox[j][n-1-i] = '#';
rotatedBox[j-stoneCnt][(n-1-i)] = '.';
}
//otherwise keep it empty
else{
rotatedBox[j][n-1-i] = '.';
}
}
//if it is an obstacle push obstacle and make stoneCnt 0
else{
rotatedBox[j][n-1-i] = '*';
stoneCnt = 0;
}
}
}
return rotatedBox;
}
};
//TC - O(N*M)
//SC - O(N*M)