Merge Two Sorted Arrays Without Extra Space in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap elements between two arrays.

DSA Python

if arr1[i] > arr2[[1]]:
    arr1[i], arr2[[1]] = arr2[[1]], arr1[i]

Drag options to blanks, or click blank then click option'

Ai

Bj

Ck

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index variable 'i' for both arrays.

Using an undefined variable as index.

We compare arr1[i] with arr2[j], so the index in arr2 should be 'j'.

2fill in blank

medium

Complete the code to move the pointer in the second array.

DSA Python

while i < n and j < m:
    if arr1[i] > arr2[j]:
        arr1[i], arr2[j] = arr2[j], arr1[i]
        j = [1]
    else:
        i += 1

Drag options to blanks, or click blank then click option'

Ai - 1

Bi + 1

Cj - 1

Dj + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Incrementing the wrong pointer.

Decrementing the pointer instead of incrementing.

After swapping, we move the pointer 'j' forward by 1 to check the next element in arr2.

3fill in blank

hard

Fix the error in the code to correctly sort the second array after swapping.

DSA Python

for k in range(m-1):
    if arr2[k] > arr2[[1]]:
        arr2[k], arr2[[1]] = arr2[[1]], arr2[k]

Drag options to blanks, or click blank then click option'

Ak + 1

Bk - 1

Ck

Dm - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index 'k' for both elements.

Using an index that goes out of range.

To compare adjacent elements, we check arr2[k] and arr2[k+1].

4fill in blank

hard

Fill both blanks to complete the inner loop that sorts arr2 after swapping.

DSA Python

for k in range(m-1):
    if arr2[[1]] > arr2[[2]]:
        arr2[[1]], arr2[[2]] = arr2[[2]], arr2[[1]]

Drag options to blanks, or click blank then click option'

Ak

Bk + 1

Cm - 1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index for both elements.

Using indices that cause out-of-range errors.

We compare arr2[k] with arr2[k+1] to swap if needed.

5fill in blank

hard

Fill all three blanks to complete the merge function without extra space.

DSA Python

def merge(arr1, arr2, n, m):
    i, j = 0, 0
    while i < n and j < m:
        if arr1[i] > arr2[j]:
            arr1[i], arr2[j] = arr2[j], arr1[i]
            j = [1]
        else:
            i += 1
    for k in range(m-1):
        for l in range(m-1-k):
            if arr2[[2]] > arr2[[3]]:
                arr2[[2]], arr2[[3]] = arr2[[3]], arr2[[2]]

Drag options to blanks, or click blank then click option'

Aj + 1

Bl

Cl + 1

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Not incrementing 'j' correctly.

Using wrong indices in the nested loop causing errors.

After swapping, increment 'j' by 1. In the nested loops, compare arr2[l] and arr2[l+1] to sort arr2.

Practice

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

easy

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

B. Sort each array separately using extra space

C. Copy elements from one array to another without sorting

D. Create a new array to hold merged elements

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 new arrays can be created.

2. Step 2: Identify the correct approach

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Merge by swapping elements in place without extra arrays [OK]

Common Mistakes:

• Trying to create a new array for merged result
• Sorting arrays separately without merging
• Ignoring the no extra space constraint

2. Which of the following Python code snippets correctly swaps elements between two arrays arr1 and arr2 without extra space?

easy

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

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

C. temp = arr1[i]; arr1[i] = arr2[j]; arr2[j] = temp

D. arr1[i], arr2[j] = arr2[j], arr1[i]

Solution

1. Step 1: Check swapping syntax in Python

   Python allows swapping two variables in one line using tuple unpacking: a, b = b, a.

2. Step 2: Identify correct swap without extra variable

   arr1[i], arr2[j] = arr2[j], arr1[i] uses this syntax correctly to swap arr1[i] and arr2[j] without extra space.

3. Final Answer:

   arr1[i], arr2[j] = arr2[j], arr1[i] -> Option D

4. Quick Check:

   Python swap syntax = arr1[i], arr2[j] = arr2[j], arr1[i] [OK]

Hint: Use Python tuple unpacking for swap: a, b = b, a [OK]

Common Mistakes:

• Assigning arr1[i] before arr2[j] loses original value
• Using temp variable unnecessarily
• Using arithmetic swap which can cause errors

3. What will be the content of arr1 and arr2 after running the following code?

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
i = 5
j = 0
while i >= 0 and j < len(arr2):
    if arr1[i] > arr2[j]:
        arr1[i], arr2[j] = arr2[j], arr1[i]
        i -= 1
        j += 1
    else:
        i -= 1
arr1.sort()
arr2.sort()
print(arr1)
print(arr2)

medium

A. [1, 5, 8, 10, 13, 15] and [2, 3, 9, 20]

B. [1, 2, 3, 5, 8, 9] and [10, 13, 15, 20]

C. [1, 5, 9, 8, 3, 2] and [20, 15, 10, 13]

D. [1, 3, 5, 8, 9, 10] and [2, 13, 15, 20]

Solution

1. Step 1: Trace the while loop swaps

   Start with i=5 (arr1[5]=20), j=0 (arr2[0]=2). Since 20 > 2, swap: arr1[5]=2, arr2[0]=20; i=4, j=1.
   Next i=4 (15), j=1 (3): 15 > 3, swap: arr1[4]=3, arr2[1]=15; i=3, j=2.
   i=3 (10), j=2 (8): 10 > 8, swap: arr1[3]=8, arr2[2]=10; i=2, j=3.
   i=2 (9), j=3 (13): 9 > 13? No, so i=1.
   i=1 (5), j=3 (13): 5 > 13? No, so i=0.
   i=0 (1), j=3 (13): 1 > 13? No, so i=-1 loop ends.
   After swaps: arr1 = [1, 5, 9, 8, 3, 2], arr2 = [20, 15, 10, 13].

2. Step 2: Sort both arrays after swapping

   The code sorts both arrays:
   arr1.sort() -> [1, 2, 3, 5, 8, 9]
   arr2.sort() -> [10, 13, 15, 20]

3. Final Answer:

   [1, 2, 3, 5, 8, 9] and [10, 13, 15, 20] -> Option B

4. Quick Check:

   Swapped and sorted arrays = [1,2,3,5,8,9], [10,13,15,20] [OK]

Hint: Swap bigger in arr1 with smaller in arr2, then sort both [OK]

Common Mistakes:

• Not decrementing i or incrementing j correctly
• Forgetting to sort arrays after swapping
• Confusing indices during swaps

4. Identify the error in the following code snippet intended to merge two sorted arrays arr1 and arr2 without extra space:

def merge(arr1, arr2):
    i = 0
    j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] > arr2[j]:
            arr1[i], arr2[j] = arr2[j], arr1[i]
        i += 1
        j += 1
    arr1.sort()
    arr2.sort()

medium

A. Sorting arrays after swapping is unnecessary

B. Swapping elements without checking if arr1[i] is smaller

C. Incrementing both i and j in every iteration causes skipping elements

D. Using while loop instead of for loop causes infinite loop

Solution

1. Step 1: Analyze loop increments

   Both i and j are incremented every iteration regardless of swap condition, which can skip elements that need comparison.

2. Step 2: Explain why skipping elements is wrong

   To merge correctly, we must compare all relevant pairs. Incrementing both pointers blindly misses some comparisons, causing incorrect merge.

3. Final Answer:

   Incrementing both i and j in every iteration causes skipping elements -> Option C

4. Quick Check:

   Increment both pointers blindly = skip elements [OK]

Hint: Increment pointers only when appropriate to avoid skipping [OK]

Common Mistakes:

• Incrementing both indices unconditionally
• Not sorting arrays after swaps
• Assuming while loop causes infinite loop here

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

hard

A. Use the gap method: compare elements at gap distance and swap if needed, reduce gap until 0

B. Concatenate both arrays and sort the combined array

C. Swap elements only if arr1[i] is greater than arr2[j], then sort both arrays

D. Copy arr2 elements into arr1 and sort arr1

Solution

1. Step 1: Understand the gap method

   The gap method starts with a gap equal to the sum of lengths divided by 2, compares elements at gap distance across both arrays, and swaps if out of order. The gap reduces each iteration until it becomes zero.

2. Step 2: Apply gap method to merge without extra space

   This method efficiently merges two sorted arrays in place without extra memory, ensuring both arrays are sorted and merged correctly.

3. Final Answer:

   Use the gap method: compare elements at gap distance and swap if needed, reduce gap until 0 -> Option A

4. Quick Check:

   Gap method merges in place without extra space [OK]

Hint: Use gap method to merge by reducing gap and swapping [OK]

Common Mistakes:

• Trying to concatenate arrays which uses extra space
• Sorting arrays separately without merging
• Swapping without systematic gap reduction