CODEWITHSUNDEEP
pythoncarraysalgorithmperformance
kleinbottle4
kleinbottle4

Reputation: 151

Efficiency comparison of two algorithms: Find the number of negative integers in a row-wise / column-wise sorted matrix

Here is the link to the full question: https://youtu.be/5dJSZLmDsxk Question: Make a function that returns the number of negative integers in a two dimensional array, such that the integers of each row in this array increase in size from index 0 to n, while the integers of each column do the same from top to bottom. E.g.

{{-5, -4, -3, -2},
 {-4, -3, -2, -1},
 {-3, -2, -1,  0},
 {-2, -1,  0,  1}}

In the video, CS Dojo presents the following solution:

def func(M, n, m):
    count = 0
    i = 0
    j = m - 1
    while j >= 0 and i < n:
        if M[i][j] < 0:
            count += j + 1
            i += 1
        else:
            j -= 1
    return count

My questions is: Why/Is the following code not as efficient? (The only difference is that the latter starts from the left, and that it increments count multiple times <-- But will these two things make any difference?

int rows = 3;
int cols = 4;

int count_neg(const int arrays[rows][cols]) {
    int count = 0;
    int pos = cols;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j <= pos; j++) {
            if (arrays[i][j] < 0)
                count++;
            else {
                pos = j;
                break;
            }
        }
        if (pos == 0)
            break; /*offers miniscule efficiency improvement?*/
    }
    return count;
}

Please assume that these were both written in the same language.

Upvotes: 1

Views: 60

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59204

The difference is that the second version scans all the negative numbers matrix, and takes O(n*m) time (the whole matrix might be negative), while the first one traces the boundary between the negative and non-negative elements, and takes O(n+m) time.

To see how the first one works, consider: Every iteration will either increment i or decrement j. i can only be incremented n-1 times, and j can only be decremented m-1 times.

Upvotes: 2

Related Questions