Merge Two Sorted Arrays Without Extra Space in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output after merging two sorted arrays without extra space

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

DSA Go

package main
import "fmt"
func merge(arr1 []int, arr2 []int) {
    n, m := len(arr1), len(arr2)
    for i := 0; i < n; i++ {
        if arr1[i] > arr2[0] {
            arr1[i], arr2[0] = arr2[0], arr1[i]
            // Move the first element of arr2 to its correct position
            first := arr2[0]
            k := 1
            for k < m && arr2[k] < first {
                arr2[k-1] = arr2[k]
                k++
            }
            arr2[k-1] = first
        }
    }
}
func main() {
    arr1 := []int{1, 5, 9, 10, 15, 20}
    arr2 := []int{2, 3, 8, 13}
    merge(arr1, arr2)
    fmt.Println(arr1)
    fmt.Println(arr2)
}

A

]02 51 31 01[
]9 8 5 3 2 1[

B

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

C

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

D

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

💡 Hint

Focus on how the smallest element of the second array is swapped and repositioned.

The code swaps elements from arr1 with the smallest element of arr2 if arr1's element is bigger. Then it repositions the smallest element in arr2 to maintain sorted order. This results in both arrays sorted without extra space.

❓ Predict Output

intermediate

Resulting arrays after merging with different input

Given the following Go code merging two sorted arrays without extra space, what is the printed output?

DSA Go

package main
import "fmt"
func merge(arr1 []int, arr2 []int) {
    n, m := len(arr1), len(arr2)
    for i := 0; i < n; i++ {
        if arr1[i] > arr2[0] {
            arr1[i], arr2[0] = arr2[0], arr1[i]
            first := arr2[0]
            k := 1
            for k < m && arr2[k] < first {
                arr2[k-1] = arr2[k]
                k++
            }
            arr2[k-1] = first
        }
    }
}
func main() {
    arr1 := []int{10, 12}
    arr2 := []int{5, 18, 20}
    merge(arr1, arr2)
    fmt.Println(arr1)
    fmt.Println(arr2)
}

A

[5 12]
[10 18 20]

B

[5 18]
[10 12 20]

C

[10 12]
[5 18 20]

D

[5 10]
[12 18 20]

💡 Hint

Check how the smallest element from arr2 moves into arr1 and arr2 is reordered.

The smallest element 5 from arr2 swaps with 10 in arr1. Then arr2 is reordered to keep sorted order. Resulting arrays are [5 10] and [12 18 20].

❓ Predict Output

advanced

Output of merging arrays with duplicates

What will be the output of the following Go program that merges two sorted arrays containing duplicates without extra space?

DSA Go

package main
import "fmt"
func merge(arr1 []int, arr2 []int) {
    n, m := len(arr1), len(arr2)
    for i := 0; i < n; i++ {
        if arr1[i] > arr2[0] {
            arr1[i], arr2[0] = arr2[0], arr1[i]
            first := arr2[0]
            k := 1
            for k < m && arr2[k] < first {
                arr2[k-1] = arr2[k]
                k++
            }
            arr2[k-1] = first
        }
    }
}
func main() {
    arr1 := []int{1, 3, 5, 7}
    arr2 := []int{0, 3, 6, 8, 9}
    merge(arr1, arr2)
    fmt.Println(arr1)
    fmt.Println(arr2)
}

A

[0 1 3 3]
[5 6 7 8 9]

B

]9 8 7 6 3[
]5 3 1 0[

C

[0 1 3 5]
[3 6 7 8 9]

D

]9 8 7 6 5[
]3 3 1 0[

💡 Hint

Duplicates are handled by swapping and repositioning the smallest element in arr2.

The smallest element 0 swaps with 1 in arr1. Then 3 swaps with 3 but no change. The arrays after merging are [0 1 3 3] and [5 6 7 8 9].

🧠 Conceptual

advanced

Why does the merge algorithm reposition the first element of the second array?

In the in-place merge algorithm for two sorted arrays, why do we move the first element of the second array to its correct position after swapping?

A Because the first element of the second array is removed and must be replaced.

B Because the first element of the second array is always the largest and must be moved to the end.

C Because swapping may break the sorted order of the second array, so repositioning restores it.

D Because the first element of the second array is swapped with the last element of the first array.

💡 Hint

Think about what happens to the order of the second array after swapping.

Swapping the first element of the second array with a bigger element from the first array can break the sorted order of the second array. Moving it to the correct position restores sorting.

❓ Predict Output

expert

Output of merging arrays with negative and positive numbers

What is the output of this Go program merging two sorted arrays containing negative and positive numbers without extra space?

DSA Go

package main
import "fmt"
func merge(arr1 []int, arr2 []int) {
    n, m := len(arr1), len(arr2)
    for i := 0; i < n; i++ {
        if arr1[i] > arr2[0] {
            arr1[i], arr2[0] = arr2[0], arr1[i]
            first := arr2[0]
            k := 1
            for k < m && arr2[k] < first {
                arr2[k-1] = arr2[k]
                k++
            }
            arr2[k-1] = first
        }
    }
}
func main() {
    arr1 := []int{-10, -3, 0, 5}
    arr2 := []int{-5, 2, 4, 6}
    merge(arr1, arr2)
    fmt.Println(arr1)
    fmt.Println(arr2)
}

A

[-10 -5 -3 0]
[2 4 5 6]

B

[-10 -5 -3 2]
[0 4 5 6]

C

[-10 -3 -5 0]
[2 4 5 6]

D

[-10 -3 0 2]
[-5 4 5 6]

💡 Hint

Check how negative numbers are swapped and repositioned to maintain sorted order.

The smallest element -5 swaps with -3 in arr1, then repositioned in arr2. The arrays become [-10 -5 -3 0] and [2 4 5 6].

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