O(m + n) int rowWithMax1s(vector arr, int m, int n) { int i = 0, j = n - 1; int ans = -1; while(i < m && j >= 0) { if(arr[i][j] == 1) { ans = i; j--; } else i++; } return ans; }
One observation would be that since rows are sorted, so if we start from top-left and check column-wise, then the first 1 we encounter would mean that this row has all 1's ahead and below rows may have 1 or 0, but since we are required to give least row, so this would be the answer. That's it. Code: for(int j=0;j
What if all the elements in the matrix are zeroes??..then we will end up with travesing through all the elements..which makes the TC at worst case as O(N*M)
Yeah that is the O(N+M) solution, I remember solving a similar question like this. It is the best approach because even with binary search it is O(M * log(N)).
@@TechHeda7nah, if we see current element is 0 we move to next row, column will only move backward with current element is 1. Therefore if everything is 0, it would only take O(M) Also, I am not talking about the code above, I am talking about its real solution
But this also has the worst time complexity as O(N*M) If the matrix is :- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 then it traversed the whole array to find the answer, Yeah but it is more efficient than the brute force.
I think this can be solved in m+n by traversing from right most end of first row and moving left whenever it's a 1, whenever 0 comes, we go down and we maintain the min row index in a variable
class Solution { public int[] findMaxRow(int mat[][], int N) { // code here int row=0; int count=0; int j=N-1; for(int i=0;i-1&&mat[i][j]==1){ row=i; count++; j--;
} } int[]ans={row,count}; return ans; } }; Yeah ! Your are absolutely correct Time complexity - O(N+M)
better sol => int rowWithMax1s(vector &arr) { // code here int n = arr.size(), m = arr[0].size(); int row = 0, col = m-1; int index = -1; int count = -1, ans = -1; while(row=0){ if(arr[row][col] == 1){ count ++; col--; } else{ row ++ ; } if(count > ans){ ans = count; index = row; } } return index; }
hey striver this question could also be solved using a basic observation of sorted rows ,in tc -> O(max(n,m)) int rowWithMax1s(vector &matrix, int n, int m){ int i=0,row=0,j=m-1; while(j>=0 && i
@@bevanmehra1706 but he did the next question in the series with the same concept which i just told , so ig he is focusing on less time complexity , i think
Imagine matrix to be : [0 , 0 , 0 , 0 , 0] [0 , 0 , 0 , 0 , 0] [0 , 0 , 0 , 0 , 0] [0 , 0 , 0 , 0 , 1] In this case, your solution will check every element column wise and will stop at the last column at index [3][4] Since it is checking all elements one by one. I will say O(N x M)! But nice approach for checking 1s in rows👌
When I run this below java code in coding ninja ,always gives me run time error Can anyone help me resolve this? public static int lowerBound(ArrayList arr, int n, int x) { int low = 0; int high = n - 1; int ans = n; while (low = x) { ans = mid; // look for smaller index on the left high = mid - 1; } else { low = mid + 1; // look on the right } } return ans; } public static int rowMaxOnes(ArrayList matrix, int n, int m) { int cnt_max = 0; int index = 0; // traverse the rows: for (int i = 0; i < n; i++) { // get the number of 1's: int cnt=lowerBound(matrix.get(i), m, 1); int cnt_ones=m-cnt; if (cnt_ones > cnt_max) { cnt_max = cnt_ones; index = i; } } return index; }
leetcode soln: class Solution { public int lowerBound(int[] mat,int n,int x){ int low =0; int high = n-1; int ans =n; Arrays.sort(mat); while(low=x){ ans = mid; high =mid-1; } else{ low =mid+1; } } return ans; } public int[] rowAndMaximumOnes(int[][] mat) { int count_max = -1; int no_of_ones =0; int index = -1; int output[] = new int[2]; int n = mat.length; int m = mat[0].length; for(int i=0;icount_max){ count_max =no_of_ones; index =i; output[0] = index; output[1] = count_max; } } return output; } }
LeetCode Solution : class Solution { public: int lower(vector arr,int n,int x){ int low = 0; int high = n-1; int ans = n; while(low = x){ ans = mid; high = mid-1; } else{ low = mid+1; } } return ans; } vector rowAndMaximumOnes(vector& mat) { int n = mat.size(); int index = -1; int max_count = -1; int m = mat[0].size(); for(int i = 0;i max_count){ max_count = count_ones; index = i; } } return {index,max_count}; } };
int rowWithMax1s(int arr[][], int n, int m) { int ans = -1; int j = m - 1; for (int i = 0; i < n; i++) { while (j >= 0 && arr[i][j] == 1) { j--; ans = i; } } return ans; }
@take U forward // Is this solution any different... tried to optimize by row since elements are only 0 and 1 import java.util.ArrayList; public class Solution { private static int onePresent(ArrayList matrix, int n, int m, int col) {
for (int i = 0; i < n; ++i) { if (matrix.get(i).get(col) == 1) { return i; } } return -1; } public static int maximumOnesRow(ArrayList matrix, int n, int m) { // Write your code here. int low = 0, high = m - 1, ans = -1; while (low
int rowWithMax1s(vector &matrix, int n, int m) { if (n == 0 || m == 0) { return -1; // Matrix is empty } int i = 0; int j = m - 1; int ans = -1; while (i < n && j >= 0) { if (matrix[i][j] == 1) { ans = i; j--; } else { i++; } } return ans; } can we solve this questions using this approach it's time complexity is 0(m+n)
O(m + n)
int rowWithMax1s(vector arr, int m, int n) {
int i = 0, j = n - 1;
int ans = -1;
while(i < m && j >= 0)
{
if(arr[i][j] == 1)
{
ans = i;
j--;
}
else
i++;
}
return ans;
}
good solution
nice
I came to look for this in video, thanks man
good👍
@@urstrulyjatin Worst case of yours is still O(row * col) in case there are no 1's
Int row = -1;
Int j = m-1;
While(j>=0 and arr[0][j]==1){
J--;
Row=0;
}
For(int i =1;i=0 and arr[i][j]==1){
J--;
Row=i;
}
}
Return row;
i coded this by myself.........firstly the iterative approach n*m comp..... and then n*log(m) comp..........thanks bhai
Finished one more video with ease . Thank you very much for such amazing content.
Thank you striver. Eagerly waiting for String
day 124 of asking striver to post the series on strings!
Day 124 of wasting your precious time
@@trueemperor3647 Day 169 of wasting my time
You would have learnt it yourself than counting days, lol
tataa bye bye.., gud bye
Understood! Such a great explanation as always, thank you very much for your effort!!
This playlist is priceless. Trust me.
One observation would be that since rows are sorted, so if we start from top-left and check column-wise, then the first 1 we encounter would mean that this row has all 1's ahead and below rows may have 1 or 0, but since we are required to give least row, so this would be the answer. That's it.
Code:
for(int j=0;j
yeah same, i also thought of that after first looking at the problem
What if all the elements in the matrix are zeroes??..then we will end up with travesing through all the elements..which makes the TC at worst case as O(N*M)
Yeah that is the O(N+M) solution, I remember solving a similar question like this. It is the best approach because even with binary search it is O(M * log(N)).
@@TechHeda7nah, if we see current element is 0 we move to next row, column will only move backward with current element is 1. Therefore if everything is 0, it would only take O(M)
Also, I am not talking about the code above, I am talking about its real solution
But this also has the worst time complexity as O(N*M)
If the matrix is :-
0 0 0 0 0
0 0 0 0 0
0 0 0 0 1
then it traversed the whole array to find the answer, Yeah but it is more efficient than the brute force.
Once again a fabulous explanation ❤
Understood,thanks striver for this amazing video.
I think this can be solved in m+n by traversing from right most end of first row and moving left whenever it's a 1, whenever 0 comes, we go down and we maintain the min row index in a variable
class Solution {
public int[] findMaxRow(int mat[][], int N) {
// code here
int row=0;
int count=0;
int j=N-1;
for(int i=0;i-1&&mat[i][j]==1){
row=i;
count++;
j--;
}
}
int[]ans={row,count};
return ans;
}
};
Yeah ! Your are absolutely correct
Time complexity - O(N+M)
Thanks Striver!
Understood✅🔥🔥
Understood ❤
hi striver im big fan of you.
please explain O(n+m) sloution as well.
Int row = -1;
Int j = m-1;
While(j>=0 and arr[0][j]==1){
J--;
Row=0;
}
For(int i =1;i=0 and arr[i][j]==1){
J--;
Row=i;
}
}
Return row;
int rowWithMax1s(vector &matrix, int n, int m)
{
int i=0,j=m-1;
int ind=-1;
while(i=0){
if(matrix[i][j]==1){
j--;
ind=i;
}else{
i++;
}
}
return ind;
}
Can also pass whole matrix to lowerbound and do arr[rowindex][mid] but also need to pass rowindex to function .
UNDERSTOOD EVERYTHING
better sol =>
int rowWithMax1s(vector &arr) {
// code here
int n = arr.size(), m = arr[0].size();
int row = 0, col = m-1;
int index = -1;
int count = -1, ans = -1;
while(row=0){
if(arr[row][col] == 1){
count ++;
col--;
}
else{
row ++ ;
}
if(count > ans){
ans = count;
index = row;
}
}
return index;
}
hey striver this question could also be solved using a basic observation of sorted rows ,in tc -> O(max(n,m))
int rowWithMax1s(vector &matrix, int n, int m){
int i=0,row=0,j=m-1;
while(j>=0 && i
bro he is teaching BS not how to do question in less time complexity ,I think.
@@bevanmehra1706 but he did the next question in the series with the same concept which i just told , so ig he is focusing on less time complexity , i think
@@mriduljain1981Thank You🎉
Understood
This was asked in Amazon interview
Please upload more and more videos. I know you'll be busy but please upload as soon as you can . Thank you so this content ❤
understood 😀
Understood 10:01
Keep it up.
if you put inside the for loop then time complexity is just o(n)
count=sum(mat[i])
if count>f_count:
ans=i
f_count=count
Sir please upload strings question approach.❤
understood! Thanks bhaiya
Understood, thank you.
Opposite Polarity concept also works over here....
2:44 it works as long as any array is sorted
UNDERSTOOD;
The required TC should be O(N+M) as per the question..but we have achieved O(nlogm)
understood
There is some error in submission in coding ninja,
Awesome lecture..................
Understood
The Java code using BS is not working in code ninja. It throws NPE. Anyone facing this ?
yes i too facing the same problem
Understood!!!
Tc is given o(m+n)
Showing runtime error even after submitting the correct code
Simple O(n+m) solution :
int rowWithMax1s(vector &arr) {
int n= arr.size();
int m=arr[0].size();
int maxRow=-1;
int i=0,j=m-1;
while(i=0){
if(arr[i][j]==0)
i++;
else{
maxRow=i;
j--;
}
}
return maxRow;
}
understood bro🙇🏿♂🙇🏿♂
understood bhaiya
what about this one:
int a=arr.size();
int b=arr[0].size();
for(int i=0;i
understood!
understood
Done
class Solution {
public int rowWithMax1s(int arr[][]) {
int rows = arr.length;
int cols = arr[0].length;
int i =0;
int j =0;
while(i
One test case is failing in coding ninjas I have checked the code 5 times
🎉🎉❤❤
i got brute force by myself eventhough it is not acceptable but i thank striver to make me to do the brute method myself
tysm sir
I am getting nullPointerException in one ip where first row =[3,3] whereas other rows are having 3 values
"understood"
understood : )
int rowWithMax1s(vector &matrix, int n, int m) {
int ans=-1;
for(int i=0;i
Imagine matrix to be :
[0 , 0 , 0 , 0 , 0]
[0 , 0 , 0 , 0 , 0]
[0 , 0 , 0 , 0 , 0]
[0 , 0 , 0 , 0 , 1]
In this case, your solution will check every element column wise and will stop at the last column at index [3][4]
Since it is checking all elements one by one. I will say O(N x M)!
But nice approach for checking 1s in rows👌
When I run this below java code in coding ninja ,always gives me run time error
Can anyone help me resolve this?
public static int lowerBound(ArrayList arr, int n, int x) {
int low = 0;
int high = n - 1;
int ans = n;
while (low = x) {
ans = mid;
// look for smaller index on the left
high = mid - 1;
} else {
low = mid + 1; // look on the right
}
}
return ans;
}
public static int rowMaxOnes(ArrayList matrix, int n, int m) {
int cnt_max = 0;
int index = 0;
// traverse the rows:
for (int i = 0; i < n; i++) {
// get the number of 1's:
int cnt=lowerBound(matrix.get(i), m, 1);
int cnt_ones=m-cnt;
if (cnt_ones > cnt_max) {
cnt_max = cnt_ones;
index = i;
}
}
return index;
}
leetcode soln:
class Solution {
public int lowerBound(int[] mat,int n,int x){
int low =0;
int high = n-1;
int ans =n;
Arrays.sort(mat);
while(low=x){
ans = mid;
high =mid-1;
}
else{
low =mid+1;
}
}
return ans;
}
public int[] rowAndMaximumOnes(int[][] mat) {
int count_max = -1;
int no_of_ones =0;
int index = -1;
int output[] = new int[2];
int n = mat.length;
int m = mat[0].length;
for(int i=0;icount_max){
count_max =no_of_ones;
index =i;
output[0] = index;
output[1] = count_max;
}
}
return output;
}
}
LeetCode Solution :
class Solution {
public:
int lower(vector arr,int n,int x){
int low = 0;
int high = n-1;
int ans = n;
while(low = x){
ans = mid;
high = mid-1;
}
else{
low = mid+1;
}
}
return ans;
}
vector rowAndMaximumOnes(vector& mat) {
int n = mat.size();
int index = -1;
int max_count = -1;
int m = mat[0].size();
for(int i = 0;i max_count){
max_count = count_ones;
index = i;
}
}
return {index,max_count};
}
};
This is not the optimal approach the optimal approach is O(n+m)
that is not valid in all the cases in worst case that apporach also take O(n*m)
Nope bro try using the search in a sorted Matrix 2 it is always be valid
// This is also a good solution!
int rowWithMax1s(vector &matrix, int n, int m) {
for(int i = 0;i
int rowWithMax1s(int arr[][], int n, int m) {
int ans = -1;
int j = m - 1;
for (int i = 0; i < n; i++) {
while (j >= 0 && arr[i][j] == 1) {
j--;
ans = i;
}
}
return ans;
}
@take U forward
// Is this solution any different... tried to optimize by row since elements are only 0 and 1
import java.util.ArrayList;
public class Solution
{
private static int onePresent(ArrayList matrix, int n, int m, int col) {
for (int i = 0; i < n; ++i) {
if (matrix.get(i).get(col) == 1) {
return i;
}
}
return -1;
}
public static int maximumOnesRow(ArrayList matrix, int n, int m) {
// Write your code here.
int low = 0, high = m - 1, ans = -1;
while (low
😇
us
int rowWithMax1s(vector &matrix, int n, int m) {
if (n == 0 || m == 0) {
return -1; // Matrix is empty
}
int i = 0;
int j = m - 1;
int ans = -1;
while (i < n && j >= 0) {
if (matrix[i][j] == 1) {
ans = i;
j--;
} else {
i++;
}
}
return ans;
}
can we solve this questions using this approach it's time complexity is 0(m+n)
Understood
Understood
understood
understood!
understood!
Understood
understood
understood!
Understood
understood
Understood
understood
Understood
understood
Understood
understood
Understood
understood
understood