CODEWITHSUNDEEP
arraysalgorithmmatrixoptimization
Vivek Kumar
Vivek Kumar

Reputation: 71

Find the row with maximum number of 1s

Given a boolean 2D array of n x m dimensions where each row is sorted. Find the 0-based index of the first row that has the maximum number of 1's.

Below is the code I have written

int rowWithMax1s(int arr[][], int n, int m) {
        int ans = -1;
        int row = 0;
        int col = m-1;
        while(row<n && col>=0){
            if(arr[row][col] == 1){
                col--;
                ans = row;
            }
            else{
                row++;
            }
        }
        return ans;
    }

I believe time complexity for the above is O(M+N). yet its giving me time limit exceeded error.

This is the link for the question https://practice.geeksforgeeks.org/problems/row-with-max-1s0023/1#

Please help me what else I can do to optimize my code.

Upvotes: 2

Views: 758

Answers (1)

no comment
no comment

Reputation: 10153

I'm pretty sure it's not your fault but the driver code's.

If you submit it a few times, you can get lucky and get it accepted. I also tried this:

class Solution {
    static int total = 0;
    int rowWithMax1s(int arr[][], int n, int m) {
        if ((total += n + m) > 300000)
            throw new RuntimeException("darn");
        ...
        (your actual solution)
        ...

That got accepted after a few attempts. There's no way 300,000 relatively simple Java steps take more than 2 seconds.

But if you click on line 1 in their code editor, you see their driver code which reads the entire matrix (or rather all matrices, for all test cases). That's likely where all that time goes. And we're not even allowed to edit that part. You could try another language. I wrote a similar solution in Python and it got accepted all five times I submitted it.

Upvotes: 2

Related Questions