Merge Two Sorted Arrays Without Extra Space in DSA Typescript

Mental Model

We want to combine two sorted lists into one sorted order without using extra space by cleverly swapping and sorting in place.

Analogy: Imagine two sorted trays of cookies side by side. Instead of moving cookies to a new tray, you swap cookies between trays to keep both trays sorted.

Array1: [1, 4, 7, 8, 10]
Array2: [2, 3, 9]

Dry Run Walkthrough

Input: Array1: [1, 4, 7, 8, 10], Array2: [2, 3, 9]

Goal: Merge both arrays so that all elements are sorted across both arrays without using extra space

Step 1: Compare last element of Array1 (10) with first element of Array2 (2), swap because 10 > 2

Array1: [1, 4, 7, 8, 2]
Array2: [10, 3, 9]

Why: We want smaller elements in Array1 and larger in Array2 to maintain sorted order after sorting

Step 2: Sort Array1 and Array2 individually after swap

Array1: [1, 2, 4, 7, 8]
Array2: [3, 9, 10]

Why: Sorting each array keeps them individually sorted after swapping elements

Step 3: Compare last element of Array1 (8) with first element of Array2 (3), swap because 8 > 3

Array1: [1, 2, 4, 7, 3]
Array2: [8, 9, 10]

Why: Continue swapping to ensure smaller elements stay in Array1

Step 4: Sort Array1 and Array2 again after swap

Array1: [1, 2, 3, 4, 7]
Array2: [8, 9, 10]

Why: Sorting keeps arrays sorted after each swap

Step 5: Compare last element of Array1 (7) with first element of Array2 (8), no swap needed

Array1: [1, 2, 3, 4, 7]
Array2: [8, 9, 10]

Why: Arrays are now correctly merged without extra space

Result:

Array1: [1, 2, 3, 4, 7]
Array2: [8, 9, 10]

Annotated Code

DSA Typescript

class MergeSortedArrays {
  static merge(arr1: number[], arr2: number[]): void {
    let n = arr1.length;
    let m = arr2.length;
    for (let i = n - 1; i >= 0; i--) {
      if (arr1[i] > arr2[0]) {
        // Swap if element in arr1 is greater than first element in arr2
        let temp = arr1[i];
        arr1[i] = arr2[0];
        arr2[0] = temp;

        // After swap, sort arr2 to keep it sorted
        arr2.sort((a, b) => a - b);
      }
    }
    // After all swaps, arr1 is sorted because we only swapped larger elements out
    arr1.sort((a, b) => a - b);
  }
}

// Driver code
const arr1 = [1, 4, 7, 8, 10];
const arr2 = [2, 3, 9];
MergeSortedArrays.merge(arr1, arr2);
console.log('Array1:', arr1.join(', '));
console.log('Array2:', arr2.join(', '));

for (let i = n - 1; i >= 0; i--) {

iterate backward through arr1 to compare largest elements first

if (arr1[i] > arr2[0]) {

check if current arr1 element is bigger than smallest arr2 element

let temp = arr1[i]; arr1[i] = arr2[0]; arr2[0] = temp;

swap elements to move smaller element into arr1

arr2.sort((a, b) => a - b);

sort arr2 after swap to maintain order

arr1.sort((a, b) => a - b);

final sort of arr1 after all swaps

Output

Array1: 1, 2, 3, 4, 7

Array2: 8, 9, 10

Complexity Analysis

Time: O(n * m log m) because for each element in arr1 we may sort arr2 which takes O(m log m)

Space: O(1) because no extra arrays are used, sorting is done in place

vs Alternative: Naive approach uses extra space to merge both arrays into one and then sort, costing O(n + m) space; this approach saves space but may be slower due to repeated sorting

Edge Cases

One or both arrays empty

No swaps needed, arrays remain as is

DSA Typescript

for (let i = n - 1; i >= 0; i--) {

Arrays already fully merged (all elements in arr1 smaller than arr2)

No swaps occur, minimal sorting

DSA Typescript

if (arr1[i] > arr2[0]) {

Arrays with duplicate elements

Duplicates are handled normally by sorting after swaps

DSA Typescript

arr2.sort((a, b) => a - b);

When to Use This Pattern

When asked to merge two sorted arrays without extra space, reach for the swapping and in-place sorting pattern to maintain order without extra memory.

Common Mistakes

Mistake: Not sorting the second array after swapping, causing it to become unsorted
Fix: Always sort arr2 after swapping to keep it sorted

Mistake: Sorting arr1 inside the loop causing unnecessary repeated sorting
Fix: Sort arr1 only once after all swaps are done

Summary

Merges two sorted arrays into sorted order without extra space by swapping and sorting in place.

Use when you must merge sorted arrays but cannot use extra memory for a combined array.

The key insight is to swap larger elements from the first array with smaller elements from the second, then sort the second array repeatedly to maintain 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 sorted

C. Combine both arrays into one sorted sequence without using extra memory

D. Swap elements randomly between arrays

Solution

1. Step 1: Understand the problem requirement

   The problem asks to merge two sorted arrays without using extra space, meaning no new array should be created.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays to form a combined sorted sequence.

3. Final Answer:

   Combine both arrays into one sorted sequence without using extra memory -> Option C

4. Quick Check:

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

Hint: Remember: no new array means merge in-place [OK]

Common Mistakes:

• Thinking a new array is allowed
• Sorting arrays separately without merging
• Swapping elements without order

2. Which TypeScript syntax correctly declares two sorted arrays for merging without extra space?

easy

A. const arr1: number[] = [1, 3, 5]; const arr2: number[] = [2, 4, 6];

B. let arr1 = (1, 3, 5); let arr2 = (2, 4, 6);

C. var arr1 = {1, 3, 5}; var arr2 = {2, 4, 6};

D. const arr1 = '1,3,5'; const arr2 = '2,4,6';

Solution

1. Step 1: Check array declaration syntax in TypeScript

   Arrays are declared using square brackets [] with type annotation number[].

2. Step 2: Validate each option

   const arr1: number[] = [1, 3, 5]; const arr2: number[] = [2, 4, 6]; uses correct syntax with const and number[] type. Others use incorrect syntax or wrong types.

3. Final Answer:

   const arr1: number[] = [1, 3, 5]; const arr2: number[] = [2, 4, 6]; -> Option A

4. Quick Check:

   Correct array syntax = const arr1: number[] = [1, 3, 5]; const arr2: number[] = [2, 4, 6]; [OK]

Hint: Use square brackets [] and type annotation for arrays [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using curly braces for arrays
• Declaring arrays as strings

3. Given arr1 = [1, 4, 7, 8, 10] and arr2 = [2, 3, 9], what will be the state of arrays after merging without extra space?

medium

A. arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10]

B. arr1 = [1, 3, 4, 7, 8], arr2 = [2, 9, 10]

C. arr1 = [1, 2, 3, 4, 10], arr2 = [7, 8, 9]

D. arr1 = [1, 2, 4, 7, 8], arr2 = [3, 9, 10]

Solution

1. Step 1: Compare elements from end of arr1 and start of arr2

   Swap elements if arr1's largest is greater than arr2's smallest to maintain order.

2. Step 2: After swapping and sorting both arrays individually

   arr1 becomes [1, 2, 3, 4, 7] and arr2 becomes [8, 9, 10].

3. Final Answer:

   arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10] -> Option A

4. Quick Check:

   In-place merge results = arr1 = [1, 2, 3, 4, 7], arr2 = [8, 9, 10] [OK]

Hint: Swap and sort ends to merge without extra space [OK]

Common Mistakes:

• Not sorting arrays after swapping
• Swapping wrong elements
• Assuming arrays merge fully into one

4. Identify the error in this TypeScript code snippet for merging two sorted arrays without extra space:

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

medium

A. Loop should run until arr2.length instead of arr1.length

B. Using arr2.sort() without a compare function causes incorrect sorting

C. Swapping elements between arrays is not allowed

D. Using let instead of const for temp variable

Solution

1. Step 1: Understand JavaScript/TypeScript sort behavior

   Without a compare function, sort() converts elements to strings and sorts lexicographically.

2. Step 2: Identify impact on numeric arrays

   Sorting numbers as strings leads to wrong order, e.g., 10 before 2.

3. Final Answer:

   Using arr2.sort() without a compare function causes incorrect sorting -> Option B

4. Quick Check:

   sort() needs compare function for numbers [OK]

Hint: Always provide compare function to sort numbers [OK]

Common Mistakes:

• Ignoring sort() default string comparison
• Thinking swapping is disallowed
• Wrong loop range assumptions

5. You have arr1 = [1, 5, 9, 10, 15, 20] and arr2 = [2, 3, 8, 13]. Using the gap method to merge without extra space, what is the final state of the arrays?

hard

A. arr1 = [1, 2, 3, 5, 9, 10], arr2 = [8, 13, 15, 20]

B. arr1 = [1, 2, 3, 5, 8, 13], arr2 = [9, 10, 15, 20]

C. arr1 = [1, 2, 3, 5, 8, 10], arr2 = [9, 13, 15, 20]

D. arr1 = [1, 2, 3, 5, 8, 9], arr2 = [10, 13, 15, 20]

Solution

1. Step 1: Calculate initial gap

   Total length = 6 + 4 = 10, initial gap = ceil(10/2) = 5.

2. Step 2: Compare and swap elements with gap 5, then reduce gap

   After several passes reducing gap to 3, 2, 1, arrays become sorted combined without extra space.

3. Final Answer:

   arr1 = [1, 2, 3, 5, 8, 9], arr2 = [10, 13, 15, 20] -> Option D

4. Quick Check:

   Gap method merges arrays in-place correctly [OK]

Hint: Use gap method: reduce gap, swap if needed [OK]

Common Mistakes:

• Not reducing gap correctly
• Swapping elements incorrectly across arrays
• Stopping before gap reaches 1