Merge Two Sorted Arrays Without Extra Space in DSA Python - 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 after merging two sorted arrays without using extra space?

DSA Python

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

arr1 = [1, 5, 9, 10, 15, 20]
arr2 = [2, 3, 8, 13]
merge(arr1, arr2, len(arr1), len(arr2))
print(arr1)
print(arr2)

A

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

B

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

C

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

D

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

💡 Hint

Focus on swapping elements when the first array element is greater than the second array element, then sort both arrays.

The code swaps elements between arr1 and arr2 when arr1[i] is greater than arr2[j], then sorts both arrays. This results in the smallest elements in arr1 and the larger ones in arr2, maintaining sorted order without extra space.

🧠 Conceptual

intermediate

Understanding the in-place merge approach

Why does the approach of swapping elements between two sorted arrays and then sorting both arrays work for merging without extra space?

A Because swapping ensures smaller elements move to the first array and sorting finalizes the order in both arrays.

B Because sorting only the first array is enough to merge both arrays.

C Because swapping elements randomly mixes arrays and sorting is unnecessary.

D Because the arrays are merged by concatenation without sorting.

💡 Hint

Think about how swapping affects the distribution of smaller and larger elements.

Swapping moves smaller elements to the first array and larger ones to the second. Sorting both arrays afterward ensures each array is sorted individually, achieving a merged state without extra space.

🔧 Debug

advanced

Identify the bug in the merge function

What is the bug in this merge function that merges two sorted arrays without extra space?

DSA Python

def merge(arr1, arr2, n, m):
    i = 0
    j = 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
    arr1.sort()
    arr2.sort()

A The index j is incremented incorrectly causing index out of range error.

B The arrays are not sorted after swapping elements.

C The index i is not incremented after swapping, causing an infinite loop.

D The function uses extra space which is not allowed.

💡 Hint

Check the loop variables and how they change inside the loop.

After swapping, only j is incremented but i remains the same, so if arr1[i] is still greater than arr2[j], the loop never progresses i, causing an infinite loop.

❓ Predict Output

advanced

Output of optimized gap method for merging arrays

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

DSA Python

def next_gap(gap):
    if gap <= 1:
        return 0
    return (gap // 2) + (gap % 2)

def merge(arr1, arr2, n, m):
    gap = n + m
    gap = next_gap(gap)
    while gap > 0:
        i = 0
        while i + gap < n:
            if arr1[i] > arr1[i + gap]:
                arr1[i], arr1[i + gap] = arr1[i + gap], arr1[i]
            i += 1
        j = gap - n if gap > n else 0
        while i < n and j < m:
            if arr1[i] > arr2[j]:
                arr1[i], arr2[j] = arr2[j], arr1[i]
            i += 1
            j += 1
        if j < m:
            j = 0
            while j + gap < m:
                if arr2[j] > arr2[j + gap]:
                    arr2[j], arr2[j + gap] = arr2[j + gap], arr2[j]
                j += 1
        gap = next_gap(gap)

arr1 = [10, 27, 38, 43]
arr2 = [3, 9, 82]
merge(arr1, arr2, len(arr1), len(arr2))
print(arr1)
print(arr2)

A

[3, 9, 10, 27]
[38, 43, 82, 100]

B

[10, 27, 38, 43]
[3, 9, 82]

C

[3, 9, 27, 38]
[10, 43, 82]

D

[3, 9, 10, 27]
[38, 43, 82]

💡 Hint

The gap method compares elements at a distance and reduces the gap gradually.

The gap method compares and swaps elements at a certain gap distance in both arrays, reducing the gap until zero. This results in fully merged sorted arrays without extra space.

🧠 Conceptual

expert

Why is the gap method efficient for merging without extra space?

Why does the gap method provide an efficient way to merge two sorted arrays without extra space compared to the naive swapping and sorting approach?

A Because it reduces the number of comparisons and swaps by comparing elements at a gap and gradually reducing it, avoiding full sorts.

B Because it uses extra memory to store intermediate results, speeding up the process.

C Because it sorts each array separately before merging, which is faster.

D Because it merges arrays by concatenation and then sorts the combined array.

💡 Hint

Think about how reducing the gap affects the sorting process.

The gap method reduces the gap between compared elements gradually, which reduces the total number of swaps and comparisons compared to sorting the arrays fully after swapping. It efficiently merges without extra space.