Skip to the solution
HardDSAAsked in 20248 min read

Efficiently Merge Two Sparse Arrays (With Holes) Without Iterating Every Index

3.1k views

The problem

Problem, as an interviewer would state it: "Merge two sparse arrays (arrays with holes) so that the cost depends on how many elements are actually present, not on the array length. Discuss edge cases, runtime, and alternatives."

Examples:

Code
a = [ , "a1", , , "a4", ]     // length 6, holes at 0, 2, 3, 5
b = [ , "b1", "b2" ]          // length 3
merge(a, b) -> [ , "b1", "b2", , "a4", ]   // length 6; b wins where it has a value

Clarifying questions expected:

  • When both arrays have a value at an index, which wins? (This solution: b overrides a.)
  • Should holes stay holes in the result, and how long should the result be?
  • Is an explicit undefined a real value or the same as a hole?

Code / implementation expected: Yes — real, direct proof against a dense reference, and a measurement of which traversals genuinely avoid walking every index.

  • js-coding
  • utility
  • algorithm

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

The solution is hidden so you can try first

8 min read · 9 sections

Run the code

Edit the code and run it here. Each console line with an expected value becomes a test.

JavaScriptReal, direct proof: a sparse merge driven by Object.keys matches a dense reference, keeps holes as holes, and handles lengths in the billions instantly
Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

Question 132 of 154 in JavaScript coding

Keep your momentum going.

Mark this question solved to track your progress, then take the next one while it is fresh.

All JavaScript coding questions
Up nextHard

Queue via two stacks

Continue