3 ms·
In my experience, when interviewers do grade based on algorithmic performance, they want to see low time complexity, and care much less about space complexity.
by warent 9y ago
In my experience, when interviewers do grade based on algorithmic performance, they want to see low time complexity, and care much less about space complexity.
In this example, you could actually accomplish the solution in linear time using a hashmap and keeping track of the min/max vals; O(max-min)
Something like...
let map = {};
let minVal = null;
let maxVal = null;
for (let a of arrays) {
for (let v of a) {
if (minVal === null) minVal = v;
else minVal = Math.min(minVal, v);
if (maxVal === null) maxVal = v;
else maxVal = Math.max(maxVal, v);
if (!map[v]) map[v] = 0;
map[v]++;
}
}
let result = [];
for (let i = minVal; i <= maxVal; i++) {
for (let n = map[i] || 0; n > 0; n--) {
result.push(i);
}
}
return result;
Haven't ran the above, just an example
- Vendan 9y agoBut you have to quantify the max-min, cause it's quite easy for the data to make that way more expensive then "merge then sort". I.e., run your algo on [[0, 1000000000], [1, 2]]
- warent 9y agoGood point :) Perhaps add a check to see if min-max is greater than K*N, and if so then use alternative method (e.g. merge sort)
- myegorov 9y agoWhat about continuous data (real numbers, strings)? Your approach has rather limited application. On a different note, merge/sort approach (O(n log n)) is in general less efficient than the heap approach (O(n log a)), and may be impractical or wasteful of space (O(n) vs O(a)) if dealing with realtime data for example.