Merge Two Sorted Arrays Without Extra Space in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of merging two sorted arrays without extra space

What is the output of the following code that merges two sorted arrays without using extra space?

DSA Javascript

function merge(arr1, arr2) {
  let i = 0, j = 0, k = arr1.length - 1;
  while (i <= k && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      i++;
    } else {
      [arr2[j], arr1[k]] = [arr1[k], arr2[j]];
      j++;
      k--;
    }
  }
  arr1.sort((a,b) => a - b);
  arr2.sort((a,b) => a - b);
  return { arr1, arr2 };
}

const arr1 = [1, 5, 9, 10, 15, 20];
const arr2 = [2, 3, 8, 13];
console.log(merge(arr1, arr2));

A {"arr1":[1,2,3,5,8,9],"arr2":[10,13,15,20]}

B {"arr1":[1,3,5,8,9,10],"arr2":[2,13,15,20]}

C {"arr1":[1,2,3,5,8,9],"arr2":[10,13,20,15]}

D {"arr1":[1,2,3,5,8,9],"arr2":[10,15,13,20]}

💡 Hint

Focus on how elements are swapped and then both arrays are sorted separately.

The code swaps elements between arr1 and arr2 to ensure all smaller elements are in arr1. Then it sorts both arrays individually to maintain sorted order.

🧠 Conceptual

intermediate

Understanding the space complexity of merging two sorted arrays without extra space

What is the space complexity of merging two sorted arrays without using extra space?

A O(log n) - Logarithmic extra space

B O(n) - Linear extra space proportional to total elements

C O(1) - Constant extra space

D O(n^2) - Quadratic extra space

💡 Hint

No additional arrays or data structures are used in the merging process.

The merging is done by swapping elements within the existing arrays and sorting them in place, so no extra space beyond a few variables is used.

🔧 Debug

advanced

Identify the error in this merge function

What error will this code produce when merging two sorted arrays without extra space?

DSA Javascript

function merge(arr1, arr2) {
  let i = 0, j = 0, k = arr1.length - 1;
  while (i < k && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      i++;
    } else {
      [arr2[j], arr1[k]] = [arr1[k], arr2[j]];
      j++;
      k--;
    }
  }
  arr1.sort((a,b) => a - b);
  arr2.sort((a,b) => a - b);
  return { arr1, arr2 };
}

const arr1 = [1, 5, 9, 10, 15, 20];
const arr2 = [2, 3, 8, 13];
console.log(merge(arr1, arr2));

A SyntaxError due to incorrect destructuring assignment

B The loop condition causes missing comparison of the last element in arr1

C TypeError because arr2 is undefined

D No error, outputs correct merged arrays

💡 Hint

Check the loop condition carefully and think about the last element in arr1.

The loop uses 'i < k' which skips comparing when i equals k, so the last element in arr1 might not be checked properly, causing incorrect merging.

❓ Predict Output

advanced

Output after merging arrays with duplicates

What is the output of merging these two sorted arrays with duplicates without extra space?

DSA Javascript

function merge(arr1, arr2) {
  let i = 0, j = 0, k = arr1.length - 1;
  while (i <= k && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      i++;
    } else {
      [arr2[j], arr1[k]] = [arr1[k], arr2[j]];
      j++;
      k--;
    }
  }
  arr1.sort((a,b) => a - b);
  arr2.sort((a,b) => a - b);
  return { arr1, arr2 };
}

const arr1 = [1, 3, 5, 7, 9];
const arr2 = [3, 5, 7, 11];
console.log(merge(arr1, arr2));

A {"arr1":[1,3,3,5,5],"arr2":[7,7,9,11]}

B }]11,9,7,7[:"2rra",]5,5,3,3,1[:"1rra"{

C {"arr1":[1,3,5,7,9],"arr2":[3,5,7,11]}

D "arr1":[1,3,3,5,5],"arr2":[7,7,9,11]}

💡 Hint

Duplicates are swapped and sorted just like other elements.

The smaller duplicates move to arr1 and larger duplicates remain in arr2, both sorted after swapping.

🧠 Conceptual

expert

Why is sorting both arrays after swapping necessary?

Why do we sort both arrays after swapping elements during the merge process without extra space?

A Because the arrays are initially unsorted

B Because sorting is faster than swapping elements correctly

C Because sorting merges the arrays into one

D Because swapping can disrupt the sorted order within each array

💡 Hint

Think about what happens to the order inside each array after swapping.

Swapping elements between arrays can place larger elements in the first array and smaller in the second, disrupting their sorted order, so sorting restores order.

Practice

1. What is the main goal when merging two sorted arrays without extra space?

easy

A. Sort each array separately without merging

B. Create a new array to hold all elements from both arrays

C. Copy elements from one array to another without sorting

D. Combine both arrays into one sorted array without using extra memory

Solution

1. Step 1: Understand the problem requirement

   The problem asks to merge two sorted arrays into a single sorted sequence without using extra space, meaning no additional arrays or large memory allocations.

2. Step 2: Identify the approach

   We must rearrange elements within the given arrays themselves to maintain sorted order combined.

3. Final Answer:

   Combine both arrays into one sorted array without using extra memory -> Option D

4. Quick Check:

   Merge without extra space = Combine in-place [OK]

Hint: Think in-place rearrangement, not new arrays [OK]

Common Mistakes:

• Assuming extra arrays are allowed
• Sorting arrays separately without merging
• Copying elements without sorting

2. Which of the following JavaScript syntax snippets correctly swaps two elements a[i] and b[j] without using a temporary variable?

easy

A. [a[i], b[j]] = [b[j], a[i]];

B. temp = a[i]; a[i] = b[j]; b[j] = temp;

C. a[i] = b[j]; b[j] = a[i];

D. a[i], b[j] = b[j], a[i];

Solution

1. Step 1: Identify correct swap syntax in JavaScript

   Using destructuring assignment, [a[i], b[j]] = [b[j], a[i]]; swaps values without a temporary variable.

2. Step 2: Check other options

   temp = a[i]; a[i] = b[j]; b[j] = temp; uses a temporary variable, C incorrectly assigns twice, D is invalid syntax.

3. Final Answer:

   [a[i], b[j]] = [b[j], a[i]]; -> Option A

4. Quick Check:

   Destructuring swap = [a[i], b[j]] = [b[j], a[i]]; [OK]

Hint: Use destructuring assignment for swap without temp [OK]

Common Mistakes:

• Using invalid syntax like option D
• Forgetting to use a temporary variable if not destructuring
• Assigning values incorrectly causing data loss

3. What will be the content of arrays a and b after running this code?

let a = [1, 5, 9, 10];
let b = [2, 3, 8, 13];

for (let i = 0; i < a.length; i++) {
  if (a[i] > b[0]) {
    [a[i], b[0]] = [b[0], a[i]];
    b.sort((x, y) => x - y);
  }
}

medium

A. a = [1, 2, 3, 5], b = [8, 9, 10, 13]

B. a = [1, 3, 5, 8], b = [2, 9, 10, 13]

C. a = [1, 2, 5, 8], b = [3, 9, 10, 13]

D. a = [1, 2, 3, 8], b = [5, 9, 10, 13]

Solution

1. Step 1: Trace the loop and swaps

   i=0: a[0]=1 <= b[0]=2 no swap
   i=1: a[1]=5 > b[0]=2 swap -> a[1]=2, b[0]=5; b sorted: [3,5,8,13]
   i=2: a[2]=9 > b[0]=3 swap -> a[2]=3, b[0]=9; b sorted: [5,8,9,13]
   i=3: a[3]=10 > b[0]=5 swap -> a[3]=5, b[0]=10; b sorted: [8,9,10,13]

2. Step 2: Final arrays after loop

   a = [1, 2, 3, 5]
   b = [8, 9, 10, 13]

3. Final Answer:

   a = [1, 2, 3, 5], b = [8, 9, 10, 13] -> Option A

4. Quick Check:

   Swapped and sorted b each time = a = [1, 2, 3, 5], b = [8, 9, 10, 13] [OK]

Hint: Swap if a[i] > b[0], then sort b [OK]

Common Mistakes:

• Not sorting array b after swap
• Swapping incorrectly causing wrong order
• Assuming arrays merge into one

4. Identify the error in this code snippet intended to merge two sorted arrays without extra space:

let a = [1, 4, 7];
let b = [2, 5, 6];

for (let i = 0; i < a.length; i++) {
  if (a[i] > b[0]) {
    let temp = a[i];
    a[i] = b[0];
    b[0] = temp;
  }
  b.sort();
}

medium

A. The if condition should be a[i] < b[0] instead of a[i] > b[0]

B. The sort() method is called without a compare function, causing incorrect sorting

C. Loop should run over array b length instead of a length

D. Swapping elements uses a temporary variable incorrectly

Solution

1. Step 1: Check the sorting method used

   The code uses b.sort() without a compare function, which sorts elements as strings, not numbers, causing wrong order.

2. Step 2: Correct sorting approach

   Use b.sort((x, y) => x - y) to sort numbers correctly.

3. Final Answer:

   The sort() method is called without a compare function, causing incorrect sorting -> Option B

4. Quick Check:

   sort() without compare = wrong numeric order [OK]

Hint: Always provide compare function for numeric sort [OK]

Common Mistakes:

• Using default sort() for numbers
• Swapping incorrectly without temp variable
• Wrong loop range

5. Given two sorted arrays a = [1, 3, 5, 7] and b = [0, 2, 6, 8, 9], how can you merge them without extra space so that after merging, a contains the first 4 smallest elements and b contains the remaining elements sorted? Which approach is best?

hard

A. Swap elements only if a[i] > b[j] without sorting b after swaps

B. Concatenate arrays and sort the combined array

C. Use a gap method to compare and swap elements between arrays until fully sorted

D. Copy all elements to a new array and then split back

Solution

1. Step 1: Understand the gap method

   The gap method compares elements at a certain gap distance in both arrays and swaps if needed, reducing the gap until 1, ensuring sorted order without extra space.

2. Step 2: Why other options fail

   Concatenate arrays and sort the combined array and D use extra space, violating constraints. Swap elements only if a[i] > b[j] without sorting b after swaps misses sorting after swaps, causing incorrect order.

3. Final Answer:

   Use a gap method to compare and swap elements between arrays until fully sorted -> Option C

4. Quick Check:

   Gap method = in-place merge without extra space [OK]

Hint: Use gap method to merge in-place efficiently [OK]

Common Mistakes:

• Using extra arrays violating constraints
• Not sorting after swaps causing disorder
• Assuming simple swaps suffice without gap reduction