Question

C programming problem < purpose: need to find time and space complexities in this problem and which function(algorithm) will be used in this problem>

I have to design an efficient algorithm which solves this problem. Also, it needs to include time and space complexities of this algorithm.
There is a matrix (N times N) of integers which rows and columns are sorted in non-decreasing order.
A sorted matrix and integer M will be given and we need to find the position(row,column) of M in this matrix. it's okay to report only one position if there are more than one answers.

when it is 4 times 4 matrix, and integer M is 19

2	29	37	60
9	11	33	87
19	35	17	5
22	15	91	7

the answer will be (3,1)

I need to find an efficient way to find this position

Answer 1

Time Complexity = O(N)
Space Complexity = O(1)


Algorithm

1. Start from topmost right element
2) Compare the given key with the element in matrix if the value match the key then print and just return
3) If the element in matrix is greater than the key then move left i.e by decrementing index j
4) If the element in matrix is smaller than the key then move down i.e by incrementing index i
5) If we end up reaching a stage where the element in matrix is not found then just print not found

We do not iterate the complete matrix, At max we will be visiting N element based on element is greater than or less than the key


Hence Time Complexity = O(N) and since we dont use any extra space Space Complexity = O(1)

Working Code in C

#include <stdio.h>

#define ROW 4

#define COL 4

void FindInSortedMatrix(int arr[ROW][COL], int key) {

int i = 0, j = ROW - 1;

while (i < ROW && j >= 0) {

if (arr[i][j] == key) {

printf("(%d, %d)\n", i+1, j+1);

return;

}

if (arr[i][j] > key)

j--;

else

i++;

}

printf("Not found\n");

}

int main()

{

int input[ROW][COL] = {

{ 2,29,37,  60 },

{ 9,  11, 33, 87 },

{ 19, 35, 17, 5 },

{ 22, 15, 91, 7 },

};

FindInSortedMatrix(input, 19);

return 0;

}

SEE OUTPUT



Thanks, PLEASE COMMENT if there is any concern.