1
\$\begingroup\$

Question: Merge k sorted Arrays

My main concerns about my code are:

  1. Performance: is it optimized and is my description of the time and complexity correct. How should I annotate the space and time complexity at every step of the code?

  2. What effect do generators have on the time and space complexity?

  3. Is my code self-documenting, modular, and readable and how can it be written better?

Solution:

  1. convert the sorted arrays into a Set data structures O(N)

  2. create a generator function which takes in the iterative values, converts them into the values type, while removing the first value as an argument to be passed to the resulting iterations.

  3. I iterate over the remaining sets O(N)

  4. I Use another generator function to merge the values O(N*N)-> O(N^2)

  5. In the merge generator, I set three-pointers and iterate them over the combined lengths of the two target arrays, the accumulated array setA with the next sequential array setB. I then iterate the ri pointer over the space of both arrays

  6. In the merge generator, I check if setA pointer is > than the length of all possible setA, this leaves setB at its current pointer as the only viable solution set. I yeld its value inside the generator space. I also default to the pointer at SetB if the value at SetA is larger than that at SetB. Otherwise, the value at SetA is at a higher priority and I yield setA's value to the solution space of the generator at ri.

  7. in the merge generator space setA is the accumulation placeholder

  8. as I yield the pass in the mergeSortedSets generator I have to lazy load the yielded values

because of that, I think the run-time complexity is at worst O(N^3) (I think this might be wrong)

function* mergeSortedSets(iterative, sets = iterative.values(), pass = sets.next().value) {
  for (let set of sets) {
    yield pass = [...merge(pass, set)]
  }
}

function* merge(setA, setB) {
  for (let ri = 0, ai = 0, bi = 0; ri < setA.length + setB.length; ri++) {
    if (ai >= setA.length || setA[ai] > setB[bi]) yield setB[bi++];
    else yield setA[ai++];
  }
}


let reduce = mergeSortedSets(new Set([
  [1, 4, 5],
  [1, 3, 4],
  [2, 6],
  [2, 3, 4]
].map(iterative => iterative)))


for (let result of reduce) {
  console.log(result)
}

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.