Find the Smallest Common Number
Short Summary
We are given three sorted arrays in ascending order. The task is to find the smallest common number among these arrays and return it, if not found return -1.
I/O Example
inputArr1 = [1, 4, 6, 7, 8, 10, 14];
inputArr2 = [1, 4, 5, 6, 7, 8, 50];
inputArr3 = [0, 6, 7, 8, 10, 25, 30, 40];
const output = myFunction(inputArr, windowSize);
// output -> 6Explanation and Walk-through
We want to detect the smallest common number in the given three arrays. We know that the arrays are sorted in ascending order.
Let's identify the important size factors:
inputArr1.length -> w1*N
inputArr2.length -> w2*N
inputArr3.length -> w3*N
w1 + w2+ w3 = 1
The total size of the input arrays (N) are important because the bigger the total size of arrays the longer the worst case search takes.
Try all possible candidates
If we start by thinking simple, a guaranteed solution would be picking an array starting from the smallest item in that array, checking if that item exists in other arrays. Once we find and item we can return it, if we run out of our picked array before finding an item that exists in all three arrays we can safely return not found. This is because at least 1 item should exist in all three arrays to be qualified as the smallest common item.
While executing this strategy, we will need to make (w1*N)*(w2+w3)*N comparisons. We won't need any additional proportional space for our operations, hence brute force approach will take:
Time complexity of O(N*N), Space complexity of O(1).
We can improve this brute force by utilizing the sorted property of our arrays and implementing binary search on second and third arrays. In that case we will need to make w1 times log(w2) and log(w3) comparisons. Which will effectively reduce our time complexity to O(N*log(N)).
Let's see how the brute force (without binary search) approach would look like in code.
const myFunction = function(inputArr1, inputArr2, inputArr3){
for(let i =0; i< inputArr1.length; i++){
let x = inputArr1[i];
if (inputArr2.indexOf(x) > -1 && inputArr3.indexOf(x) > -1){
return x;
}
};
return -1;
}Increasing efficiency
Let's see if we can improve over that solution. Since our arrays are sorted, we know for a fact that as the indexes increase the values won't be decreasing. We can use this property and make a walk-through in our arrays by keeping three indexes and comparing the values at hand. We can begin by index 0 on all arrays and compare the 3 values. If they are equal, we will have our result. If they are not, we can move our indexes of the smallest 2 values by one and repeat. At any point if we encounter a match, that's our result, if we run out of indexes on any array, we can return -1 safely because there won't be any match. Since in the worst case we will sweep through all the arrays, we will have to make w1+w2+w3 comparisons which is effectively N. We won't be using any additional memory for this operation so our auxillary space requirement is constant.
Time complexity: O(N) Space complexity: O(1)
Let's see how that looks like in code.
const myFunction = function(inputArr1, inputArr2, inputArr3){
let index1 = 0;
let index2 = 0;
let index3 = 0;
let currentMax = Number.MIN_VALUE;
// if we go overflow on any array we can stop the loop
while(index1 <inputArr1.length && index2 < inputArr2.length && index3<inputArr3.length){
if(inputArr1[index1] === inputArr2[index2] && inputArr2[index2] == inputArr3[index3]){
return inputArr1[index1];
}
currentMax = Math.max(inputArr1[index1],inputArr2[index2],inputArr3[index3]);
if(inputArr1[index1] < currentMax){
index1++;
}
if(inputArr2[index2] < currentMax){
index2++;
}
if(inputArr3[index3] < currentMax){
index3++;
}
}
// safely return -1 if we finish any of the arrays without a match.
return -1;
}We can still tweak our process for getting some quick wins.
We can detect the biggest element at index:0 of arrays and call that the main array.
Before starting to traverse, we can skip the elements that are smaller compared to out initial in the main array. We can achieve this by making a binary search on the other arrays for our current element and finding the index. If we can find our element in both of the arrays that's our result, if we can find it in only one of them, we can set that index as our start index for that array. This will allow us to avoid index traversing until that point.
These optimizations will have an upfront cost of binary searching, which will add log(N) to out complexity but since O(N) + O(log(N)) is effectively O(N) it might be worth it.
Doing that would look like this in code:
const binarySearch = function(arr, searchKey){
let start = 0;
let end = arr.length -1;
let mid = start + Math.floor((end-start)/2);
while(start <=end ){
if(searchKey > arr[mid]){
start = mid+1;
}else if (searchKey < arr[mid]){
end = mid-1;
}
else{
return mid;
}
mid = start + Math.floor((end-start)/2);
}
return -1;
}
const myFunction = function(inputArr1, inputArr2, inputArr3){
let index1 = 0;
let index2 = 0;
let index3 = 0;
let currentMax = Number.MIN_VALUE;
// Optimization tweak
currentMax = Math.max(currentMax, inputArr1[index1], inputArr2[index2], inputArr3[index3]);
if (inputArr1[index1] < currentMax){
// if found set it, if not found keep it at 0
index1 = Math.max(0, binarySearch(inputArr1, currentMax));
}
if (inputArr2[index2] < currentMax){
// if found set it, if not found keep it at 0
index2 = Math.max(0, binarySearch(inputArr2, currentMax));
}
if (inputArr3[index3] < currentMax){
// if found set it, if not found keep it at 0
index3 = Math.max(0, binarySearch(inputArr3, currentMax));
}
// if we go overflow on any array we can stop the loop
while(index1 <inputArr1.length && index2 < inputArr2.length && index3<inputArr3.length){
if(inputArr1[index1] === inputArr2[index2] && inputArr2[index2] == inputArr3[index3]){
return inputArr1[index1];
}
currentMax = Math.max(inputArr1[index1],inputArr2[index2],inputArr3[index3]);
if(inputArr1[index1] < currentMax){
index1++;
}
if(inputArr2[index2] < currentMax){
index2++;
}
if(inputArr3[index3] < currentMax){
index3++;
}
}
// safely return -1 if we finish any of the arrays without a match.
return -1;
}Although these are small optimizations they can come in handy when the datasets are large or datasets don't have many overlapping elements.
Feel free to checkout the complete code.
Please comment or dm me if you have other questions or remarks.
Until next time,
Stay all in!
Reha S.
Apr 28 2024