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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap elements between two arrays.

DSA Go

if arr1[i] > arr2[[1]] {
    arr1[i], arr2[[1]] = arr2[[1]], arr1[i]
}

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

Aj

Bk

Cm

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using an undefined variable for the second array index.

We use 'j' as the index for the second array to swap elements correctly.

2fill in blank

medium

Complete the code to sort the first array after swapping.

DSA Go

for i := 0; i < len(arr1)-1; i++ {
    if arr1[i] > arr1[[1]] {
        arr1[i], arr1[i+1] = arr1[i+1], arr1[i]
    }
}

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

Ai-1

B0

Ci

Di+1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the same index for both elements, causing no swap.

We compare element at index i with the next element at i+1 to sort properly.

3fill in blank

hard

Fix the error in the loop condition to merge arrays correctly.

DSA Go

for i, j := 0, 0; i < len(arr1) && j < [1]; { 
    // merging logic
}

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

Alen(arr2)

Blen(arr1)

Clen(arr1) + len(arr2)

Dlen(arr2) - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the length of the first array for the second array index.

The second array length is len(arr2), so j should be less than that.

4fill in blank

hard

Fill both blanks to correctly swap and increment indices.

DSA Go

if arr1[[1]] > arr2[[2]] {
    arr1[i], arr2[j] = arr2[j], arr1[i]
    i++
    j++
}

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

Ai

Bj

Ck

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing up indices or using undefined variables.

We compare arr1[i] with arr2[j] to decide swapping and increment both indices.

5fill in blank

hard

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

DSA Go

for i, j := 0, 0; i < len(arr1) && j < len(arr2); {
    if arr1[[1]] <= arr2[[2]] {
        i++
    } else {
        arr1[[3]], arr2[j] = arr2[j], arr1[i]
        i++
        j++
    }
}

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

Ai

Bj

Dk

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices or mixing i and j.

We compare arr1[i] and arr2[j], increment i if smaller or equal, else swap arr1[i] and arr2[j] and increment both.

Practice

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

easy

A. Combine both arrays into one sorted sequence 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 should be created.

2. Step 2: Identify the correct approach

   Only Combine both arrays into one sorted sequence without using extra memory describes merging both arrays into one sorted sequence without extra memory, which matches the problem's goal.

3. Final Answer:

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

4. Quick Check:

   Merge without extra space = Combine sorted arrays in place [OK]

Hint: Remember: no extra space means no new arrays [OK]

Common Mistakes:

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

2. Which of the following Go code snippets correctly swaps two elements a[i] and b[j] without extra space?

easy

A. a[i] = a[i] + b[j]; b[j] = a[i] - b[j]; a[i] = a[i] - b[j]

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: Check Go syntax for swapping

   In Go, swapping two variables can be done directly using multiple assignment: a[i], b[j] = b[j], a[i].

2. Step 2: Analyze each option

   a[i], b[j] = b[j], a[i] uses correct Go syntax. temp := a[i]; a[i] = b[j]; b[j] = temp uses a temporary variable which is valid but uses extra space. a[i] = b[j]; b[j] = a[i] overwrites a[i] before assigning b[j]. a[i] = a[i] + b[j]; b[j] = a[i] - b[j]; a[i] = a[i] - b[j] uses arithmetic swap which is error-prone and not recommended.

3. Final Answer:

   a[i], b[j] = b[j], a[i] -> Option D

4. Quick Check:

   Go swap syntax = a[i], b[j] = b[j], a[i] [OK]

Hint: Use Go's multiple assignment for clean swaps [OK]

Common Mistakes:

• Overwriting values before swapping
• Using temp variables when avoiding extra space
• Using arithmetic swaps that can cause errors

3. What is the output of the following Go code after merging two sorted arrays without extra space?

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

for i := 0; i < len(arr1); i++ {
    if arr1[i] > arr2[0] {
        arr1[i], arr2[0] = arr2[0], arr1[i]
        // Re-sort arr2's first element
        first := arr2[0]
        k := 1
        for k < len(arr2) && arr2[k] < first {
            arr2[k-1] = arr2[k]
            k++
        }
        arr2[k-1] = first
    }
}

fmt.Println(arr1)
fmt.Println(arr2)

medium

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

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

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

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

Solution

1. Step 1: Understand the merging logic

   The code compares each element of arr1 with the first element of arr2. If arr1[i] is greater, it swaps and then re-sorts arr2's first element to maintain sorted order.

2. Step 2: Trace the arrays after merging

   After the loop, arr1 becomes [1 2 3 5 8 9] and arr2 becomes [10 13 15 20]. The code does not combine arrays but rearranges elements to keep both sorted without extra space.

3. Final Answer:

   [1 2 3 5 8 9] [10 13 15 20] -> Option A

4. Quick Check:

   In-place merge = arr1 and arr2 sorted separately [OK]

Hint: Swap and re-sort arr2's first element to keep order [OK]

Common Mistakes:

• Assuming arrays combine into one
• Not re-sorting arr2 after swap
• Confusing output format

4. Identify the bug in this Go code snippet that tries to merge two sorted arrays without extra space:

for i := 0; i < len(arr1); i++ {
    if arr1[i] > arr2[0] {
        arr1[i], arr2[0] = arr2[0], arr1[i]
        for j := 0; j < 2; j++ {
            if arr2[j] > arr2[j+1] {
                arr2[j], arr2[j+1] = arr2[j+1], arr2[j]
            }
        }
    }
}

medium

A. The outer loop should iterate over arr2 instead of arr1

B. Swapping arr1[i] and arr2[0] is incorrect

C. The inner loop does not fully sort arr2 after swapping

D. The code uses extra space for swapping

Solution

1. Step 1: Analyze the sorting of arr2 after swap

   The inner loop only runs once per swap and performs a single pass of adjacent swaps, which is not enough to fully sort arr2.

2. Step 2: Identify the bug

   Because arr2 is not fully sorted after swapping, the merge will fail to maintain sorted order. A full re-sort or a proper insertion step is needed.

3. Final Answer:

   The inner loop does not fully sort arr2 after swapping -> Option C

4. Quick Check:

   Partial sort after swap causes incorrect order [OK]

Hint: Ensure full re-sort or insertion after swapping [OK]

Common Mistakes:

• Assuming one pass sorts arr2
• Swapping incorrectly
• Looping over wrong array

5. Given two sorted arrays arr1 = [1, 4, 7, 8, 10] and 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 elements sorted? Choose the correct final state of arr1 and arr2.

hard

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

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

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

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

Solution

1. Step 1: Merge by comparing and swapping elements

   Compare elements from arr1 and arr2. Swap if arr1[i] > arr2[0], then re-sort arr2 to keep it sorted.

2. Step 2: Final arrays after merging

   After merging, arr1 holds the smallest 5 elements: [1, 2, 3, 4, 7], and arr2 holds the remaining sorted elements: [8, 9, 10].

3. Final Answer:

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

4. Quick Check:

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

Hint: Swap and re-sort arr2's first element after each swap [OK]

Common Mistakes:

• Not re-sorting arr2 after swaps
• Mixing order of elements in arr2
• Assuming arr1 grows beyond its size