Merge Two Sorted Arrays Without Extra Space in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean to merge two sorted arrays without extra space?

It means combining two sorted arrays into one sorted sequence without using any additional array or storage space beyond the given arrays.

beginner

Why can't we simply concatenate and sort two arrays to merge without extra space?

Concatenating requires extra space to hold combined elements, and sorting after concatenation is inefficient. The goal is to merge while keeping space usage minimal and maintaining sorted order.

intermediate

What is the main idea behind the gap method for merging two sorted arrays without extra space?

The gap method compares elements at a certain gap distance and swaps them if out of order, gradually reducing the gap until it becomes 1, ensuring the arrays are merged and sorted in place.

intermediate

In the gap method, how is the gap value updated after each pass?

The gap is updated by dividing it by 2 and rounding up (gap = (gap + 1) / 2) until it becomes 1, which is the final pass to ensure complete sorting.

intermediate

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

The time complexity is approximately O((n + m) log(n + m)), where n and m are the sizes of the two arrays, due to repeated passes with decreasing gap sizes.

What is the main challenge when merging two sorted arrays without extra space?

A Keeping the arrays sorted without using extra storage

B Finding the maximum element

C Reversing the arrays

D Sorting each array separately

The main challenge is to merge while keeping the arrays sorted without using extra storage.

Which method is commonly used to merge two sorted arrays without extra space?

A Gap method

B Bubble sort

C Quick sort

D Insertion sort

The gap method is a popular approach to merge two sorted arrays in place without extra space.

How is the gap updated in the gap method?

A gap = gap * 2

B gap = (gap + 1) / 2

C gap = gap + 1

D gap = gap - 1

The gap is updated by dividing it by 2 and rounding up: gap = (gap + 1) / 2.

What happens when the gap becomes 1 in the gap method?

A The process restarts

B The arrays are reversed

C The arrays are split

D The arrays are fully merged and sorted

When gap is 1, the final pass ensures the arrays are fully merged and sorted.

What is the space complexity of merging two sorted arrays using the gap method?

A O(n + m)

B O(n)

C O(1)

D O(m)

The gap method merges arrays in place using constant extra space O(1).

Explain the gap method for merging two sorted arrays without extra space.

Think about how you compare and swap elements at a distance that shrinks each time.

Describe why merging two sorted arrays without extra space is useful and how it differs from normal merging.

Consider memory constraints and efficiency.

Practice

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

easy

A. Create a new array to hold merged elements

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

C. Copy elements from one array to another without sorting

D. Sort each array separately using extra space

Solution

1. Step 1: Understand the problem requirement

   The task is to merge two sorted arrays so that the combined elements remain sorted, but without using any extra space like a new array.

2. Step 2: Identify the correct approach

   We must rearrange elements within the given arrays themselves to maintain sorted order without additional memory.

3. Final Answer:

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

4. Quick Check:

   Merge without extra space = Combine in place [OK]

Hint: Merge by swapping elements between arrays without extra space [OK]

Common Mistakes:

• Assuming extra space is allowed
• Sorting arrays separately without merging
• Creating a new array for merged result

2. Which of the following C# code snippets correctly swaps elements between two arrays without extra space?

easy

A. arr1[i] = arr1[i] + arr2[j]; arr2[j] = arr1[i] - arr2[j]; arr1[i] = arr1[i] - arr2[j];

B. arr1[i] = arr2[j]; arr2[j] = arr1[i];

C. if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; }

D. int temp = arr2[j]; arr2[j] = arr1[i]; arr1[i] = temp + 1;

Solution

1. Step 1: Check swapping logic correctness

   if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; } uses a temporary variable to swap values correctly without losing data.

2. Step 2: Analyze other options for errors

   arr1[i] = arr2[j]; arr2[j] = arr1[i]; overwrites arr2[j] before saving arr1[i], losing original value. arr1[i] = arr1[i] + arr2[j]; arr2[j] = arr1[i] - arr2[j]; arr1[i] = arr1[i] - arr2[j]; uses arithmetic swap but can cause overflow and is less safe. int temp = arr2[j]; arr2[j] = arr1[i]; arr1[i] = temp + 1; incorrectly adds 1 during swap, changing values.

3. Final Answer:

   if (arr1[i] > arr2[j]) { int temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp; } -> Option C

4. Quick Check:

   Temporary variable swap = Correct swap [OK]

Hint: Use a temp variable to swap safely in C# [OK]

Common Mistakes:

• Overwriting values without temp variable
• Using unsafe arithmetic swaps
• Altering values unintentionally during swap

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

int[] arr1 = {1, 5, 9, 10, 15, 20};
int[] arr2 = {2, 3, 8, 13};
int n = arr1.Length, m = arr2.Length;
for (int i = 0; i < n; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    int first = arr2[0];
    int k;
    for (k = 1; k < m && arr2[k] < first; k++) {
      arr2[k - 1] = arr2[k];
    }
    arr2[k - 1] = first;
  }
}

medium

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

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

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

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

Solution

1. Step 1: Trace the swapping and insertion in arr2

   For each element in arr1, if it is greater than arr2[0], swap and then insert arr2[0] in sorted order in arr2. This pushes larger elements to arr2.

2. Step 2: Final arrays after all iterations

   After all swaps and insertions, arr1 becomes [1, 2, 3, 5, 8, 9] and arr2 becomes [10, 13, 15, 20].

3. Final Answer:

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

4. Quick Check:

   In-place merge with insertion sort = arr1 and arr2 sorted [OK]

Hint: Swap if arr1[i] > arr2[0], then insert arr2[0] sorted [OK]

Common Mistakes:

• Not inserting arr2[0] correctly after swap
• Overwriting arr2 elements incorrectly
• Confusing array indices during insertion

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

for (int i = 0; i < n; i++) {
  if (arr1[i] > arr2[0]) {
    int temp = arr1[i];
    arr1[i] = arr2[0];
    arr2[0] = temp;
    int first = arr2[0];
    int k = 1;
    while (k < m && arr2[k] < first) {
      arr2[k - 1] = arr2[k];
      k++;
    }
    arr2[k] = first;
  }
}

medium

A. The insertion index in arr2 is incorrect; should be arr2[k - 1] = first

B. The swap logic between arr1[i] and arr2[0] is wrong

C. The loop should run from i = 1 instead of 0

D. The condition arr2[k] < first should be arr2[k] > first

Solution

1. Step 1: Analyze insertion logic in arr2

   The code shifts elements left to make space for 'first'. The correct insertion index after shifting is k - 1, not k.

2. Step 2: Identify the error impact

   Assigning arr2[k] = first overwrites the next element incorrectly, causing wrong order.

3. Final Answer:

   The insertion index in arr2 is incorrect; should be arr2[k - 1] = first -> Option A

4. Quick Check:

   Correct insertion index = k - 1 [OK]

Hint: Insert shifted element at k-1 index after loop ends [OK]

Common Mistakes:

• Using wrong index for insertion after shifting
• Incorrect swap logic
• Wrong loop start index

5. Given two sorted arrays:
arr1 = [1, 4, 7, 8, 10]
arr2 = [2, 3, 9]
How would you merge them without extra space so that after merging, arr1 contains the first 5 smallest elements and arr2 contains the remaining sorted elements? Choose the correct final arrays.

hard

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, 4, 7, 8], arr2 = [3, 9, 10]

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

Solution

1. Step 1: Compare and swap elements between arr1 and arr2

   Start from beginning of arr1, if arr1[i] > arr2[0], swap and then insert arr2[0] in sorted order in arr2.

2. Step 2: After all swaps and insertions

   arr1 becomes [1, 2, 3, 4, 7] and arr2 becomes [8, 9, 10], maintaining sorted order without extra space.

3. Final Answer:

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

4. Quick Check:

   In-place merge keeps first array smallest elements [OK]

Hint: Swap if arr1[i] > arr2[0], then insert arr2[0] sorted [OK]

Common Mistakes:

• Not maintaining sorted order after swap
• Incorrect insertion in second array
• Assuming extra space is allowed