The actual problem is pretty simple, implement an algorithm that returns true if the target value is contained within the matrix. Here are the two solutions I came up with. I’m not sure which one would be preferable? I believe solution 1 is faster since we don’t need to build a new array, however would this be significantly faster?
Solution 1:
var searchMatrix = function(matrix, target) {
let cols = matrix[0].length;
let rows = matrix.length;
let left = 0;
let right = cols*rows - 1;
while(left <= right) {
let midIndex = left + Math.floor((right-left)/2);
let midValue = matrix[Math.floor(midIndex/cols)][Math.floor(midIndex%cols)];
console.log(midValue);
if(midValue === target) {
return true;
}
else if(midValue < target) {
left = midIndex + 1;
} else {
right = midIndex - 1;
}
}
return false;
};
Solution 2:
var searchMatrix = function(matrix, target) {
let arr = []
for(let row of matrix) {
arr = [...arr,...row];
}
let left = 0;
let right = arr.length - 1;
while(left <= right) {
let middle = left + Math.floor((right-left)/2);
if(arr[middle] === target) {
return true;
} else if(arr[middle] < target) {
left = middle + 1;
} else {
right = middle - 1;
}
}
return false;
};
Based on my understanding, the main step we’re adding is converting the matrix into a regular Array. Would this make the algorithm O(n) since we have to add every element into the new array?
For solution 1, we don’t have to create a new array so we’d have constant space correct?
I’m not particularly sure how to explain the first solution is preferable in terms of time/space.