Find Maximum 1's Row | GFG Solution | Searching and Sorting
Vložit
- čas přidán 20. 06. 2021
- Please consume this content on nados.pepcoding.com for a richer experience. It is necessary to solve the questions while watching videos, nados.pepcoding.com enables that.
NADOS also enables doubt support, career opportunities and contests besides free of charge content for learning. For a better experience and more exercises, VISIT: www.pepcoding.com/resources/
Have a look at our result: www.pepcoding.com/placements
Follow us on our CZcams page: / pepcoding
Follow us on our FB page: / pepcoding
Follow us on Instagram: / pepcoding
Follow us on LinkedIn: / pepcoding-education
Follow us on Pinterest: / _created
Follow us on Twitter: home
.
.
.
Happy Programming !!! Pep it up 😍🤩
.
.
.
#pepcoding #code #coder #codinglife #programming #coding #java #freeresources #datastrucutres #pepcode #competitive #competitiveprogramming #softwareengineer #engineering #engineer
GFG wants an O(N+M) solution. This solution is O(N*log(M)).
The O(N*log(M)) implementation in C++ is giving AC but in Java; it's is giving TLE
public static int findRow(int[][] arr) {
int i = 0;
int j = arr[0].length - 1;
int ans = i;
while(i < arr.length && j >= 0){
if(arr[i][j] == 1){
ans = i;
j--;
}else{
i++;
}
}
return ans;
}
Thanks..but there is a much more optimized solution with O(m+n) time complexity.
this is O(n +m ) optimized approach tested of GFG > int rowWithMax1s(int matrix[][], int n, int m) {
int i = 0, j = m - 1, maxRow = - 1;
while(i < n && j >= 0)
{
if(matrix[i][j] == 1)
{
maxRow = i;
j--;
}
else
i++;
}
return maxRow;
}
@@IamLucky0007 ya
in our O(m+n) solution ,we will do something similar like count 1s question earlier in playlist ,if we get 1 then we can discard check on our column as max count wouln' be larger than our curr 1s count ,we move col-- ,if encounter a 0 then there's a possibility then row++ wali row mai 1 ho so we move down , although thisoltuion works in O(n+m) ,but when we have only 1 row in matrix and that too a large one with first one at very first ,we move O(n) but binarysearch sol finds it in O(logn)
public static int findRow(int[][]mat) {
int row = 0;
int col = mat[0].length-1;
int res = 0;
while(row=0){
if(mat[row][col]==1){
res = row;
col--;
}
else
row++;
}
return res;
}
You can consume the same content with doubt support on nados.pepcoding.com
TLE de raha h ye to n*logn me b pass nhi ho rha h esa kyu madam ? esa kyu ??
check my above comment
@@danishrockz1 Can't see your comment.
maam plzz discuss optimised approach O
check my above comment for optimized sol