Efficient Pair Replacement Using Slices and Two-Pointer Technique in Go

Introduction

Hello there! Are you ready to solve another engaging problem today? We have a practical task that will enhance your problem-solving skills. It involves critical aspects of programming — dealing with slices and using techniques such as sorting and the two-pointer method . So, let's jump in!

Task Statement

Our task is as follows. Suppose you have two equally long slices, A and B, with lengths varying from 1 to 1000, with each element being a unique positive integer ranging from 1 up to 1,000,000. Your challenge is to create a Go function that performs the following steps: For each element B[i] in slice B, double its value to get 2 * B[i] . Find the closest number to 2 * B[i] in slice B . Let's call this closest number B[j] . For each index i in slice B, get the value at index j in slice A, i.e., A[j] . Create a new slice where each element is A[j] corresponding to the closest number found in B . To illustrate this, let's consider an example. We have: Go A := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110} B := []int{4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100} After running your function, the resulting slice should look like this: Go result := []int{80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110} Let's walk through the first few steps: The first item in B is 4 at index=0 . Doubling this number gives us 8 . The closest number to 8 in slice B is 8, which is at index=7 . The number at the same index in slice A is 80, so we add 80 to our new slice. The second item in B is 12 at index=1 . Doubling this number gives us 24 . The closest number to 24 in B is 25, which is at index=9 . The corresponding index in A has the number 100 . So, we add 100 to our new slice. The third item in B is 3 at index=2 . Doubling this number gives us 6 . The closest number to 6 in B is 6, which is at index=4 . The corresponding index in A has the number 50 . So, we add 50 to our new slice. We continue this process for the rest of the elements in B .

Create and Sort Array

Let's embark on our solution-building journey by constructing a sorted list for slice B. This list will include pairs of values (val) and their corresponding indices (idx) from slice B. Here, val represents the element in B, while idx denotes the index at which val is found in slice B. This sorted list will mimic an associative array, storing 'value-index' pairs. It not only organizes the data for efficient retrieval but also makes it easier for us to traverse the list. Here's the introductory part of our Go function, including the creation of the sorted list: Gopackage main import ( "fmt" "sort" ) type Pair struct { value int index int } func FindAndReplace(A, B []int) []int { var B_sorted []Pair for i, v := range B { B_sorted = append(B_sorted, Pair{value: v, index: i}) } sort.Slice(B_sorted, func(i, j int) bool { return B_sorted[i].value < B_sorted[j].value }) In the above code, we generate a slice of Pair structures, comprising the values from B and their respective indices using a simple loop. Then, the sort.Slice function arranges these pairs in ascending order of their values.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Now that our sorted list is ready, we initiate the right pointer, j, and the result slice, res. The former assists in ensuring our search remains within the boundaries of B_sorted, while the latter will be our final output containing the replaced elements from slice A. We'll update res as we progress through the solution.

    j := 0 // Initialize right pointer
    res := make([]int, len(A)) // Initialize the result slice

    j := 0 // Initialize right pointer
    res := make([]int, len(A)) // Initialize the result slice

The primary logic of the problem lies in this step. We iterate over each item in B_sorted using its index i. For every item, we calculate the target, which is double the value of the element at the current index in B_sorted. We adjust the position of the right pointer, j, until it points to the closest number that is less than the target (2 * B_sorted[i].value). The operation continues as long as j is within the bound for B_sorted and the next number in the array is smaller than the target.

Once we've identified a number greater than or equal to the target, we compare it with the previous number to see which one is closer to the target. If the next number is closer, we advance j by one step.

    for i := 0; i < len(B); i++ {
        target := 2 * B_sorted[i].value // The target is twice the current number in the sorted B
        for j < len(B)-1 && B_sorted[j+1].value < target {
            j++ // Move the right pointer to find a number smaller than or equal to the target
        }
        if j < len(B)-1 && abs(B_sorted[j+1].value-target) < abs(target-B_sorted[j].value) {
            j++ // Move the right pointer one more step if the next number is closer to the target
        }
    }

    for i := 0; i < len(B); i++ {
        target := 2 * B_sorted[i].value // The target is twice the current number in the sorted B
        for j < len(B)-1 && B_sorted[j+1].value < target {
            j++ // Move the right pointer to find a number smaller than or equal to the target
        }
        if j < len(B)-1 && abs(B_sorted[j+1].value-target) < abs(target-B_sorted[j].value) {
            j++ // Move the right pointer one more step if the next number is closer to the target
        }
    }

Note that we use a helper function abs that we'll define next for calculating absolute values, as Go's standard library math.Abs only works with floats.

In this final step, we employ the indices from B_sorted to alter the appropriate elements in slice A. Based on the position of the right pointer j, we replace the corresponding element in res with the element in A located at the same index.

        res[B_sorted[i].index] = A[B_sorted[j].index]
    }

    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

        res[B_sorted[i].index] = A[B_sorted[j].index]
    }

    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Full Code

The fully combined code for this solution is found below. It effectively finds and replaces elements in the slice A based on the closest doubled values in the slice B:

package main

import (
    "fmt"
    "sort"
)

type Pair struct {
    value int
    index int
}

func FindAndReplace(A, B []int) []int {
    var B_sorted []Pair
    for i, v := range B {
        B_sorted = append(B_sorted, Pair{value: v, index: i})
    }
    sort.Slice(B_sorted, func(i, j int) bool {
        return B_sorted[i].value < B_sorted[j].value
    })

    j := 0 // Initialize right pointer
    res := make([]int, len(A)) // Initialize the result slice

    for i := 0; i < len(B); i++ {
        target := 2 * B_sorted[i].value // The target is twice the current number in the sorted B
        for j < len(B)-1 && B_sorted[j+1].value < target {
            j++ // Move the right pointer to find a number smaller than or equal to the target
        }
        if j < len(B)-1 && abs(B_sorted[j+1].value-target) < abs(target-B_sorted[j].value) {
            j++ // Move the right pointer one more step if the next number is closer to the target
        }
        res[B_sorted[i].index] = A[B_sorted[j].index]
    }

    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    A := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110}
    B := []int{4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100}
    result := FindAndReplace(A, B)
    fmt.Println(result) // 80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110
}

package main

import (
    "fmt"
    "sort"
)

type Pair struct {
    value int
    index int
}

func FindAndReplace(A, B []int) []int {
    var B_sorted []Pair
    for i, v := range B {
        B_sorted = append(B_sorted, Pair{value: v, index: i})
    }
    sort.Slice(B_sorted, func(i, j int) bool {
        return B_sorted[i].value < B_sorted[j].value
    })

    j := 0 // Initialize right pointer
    res := make([]int, len(A)) // Initialize the result slice

    for i := 0; i < len(B); i++ {
        target := 2 * B_sorted[i].value // The target is twice the current number in the sorted B
        for j < len(B)-1 && B_sorted[j+1].value < target {
            j++ // Move the right pointer to find a number smaller than or equal to the target
        }
        if j < len(B)-1 && abs(B_sorted[j+1].value-target) < abs(target-B_sorted[j].value) {
            j++ // Move the right pointer one more step if the next number is closer to the target
        }
        res[B_sorted[i].index] = A[B_sorted[j].index]
    }

    return res
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func main() {
    A := []int{10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110}
    B := []int{4, 12, 3, 9, 6, 1, 5, 8, 37, 25, 100}
    result := FindAndReplace(A, B)
    fmt.Println(result) // 80, 100, 50, 20, 20, 60, 40, 20, 110, 90, 110
}

It's vital to have an understanding of the computational complexity of our Two-Pointer approach and why it's effective for this problem.

Time Complexity: The main steps of our solution involve sorting the slice B and traversing it with two pointers. Sorting a slice of n elements has a time complexity of O(n log n). The two-pointer traversal of the sorted array adds an O(n) time complexity. Thus, the overall time complexity of our solution is O(n log n) for the sorting operation, which dominates the linear time traversal.
Space Complexity: Apart from the input data, our solution needs space for B_sorted and res, both of which are slices having the same length as the input. Therefore, our solution has a linear space complexity of O(n), where n is the length of the input slices.

Great job! You've successfully tackled a high-level task that involved manipulating slices and implementing advanced techniques such as sorting and the two-pointer method. Through this exercise, you've honed your Go coding skills further and demonstrated your ability to solve a complex, real-world challenge.

Now it's your turn to master these techniques. We encourage you to practice solving similar challenges using the skills you've learned from this lesson. The more you practice, the better your problem-solving skills will become. So, get started and enjoy your journey in coding!

Introduction

Task Statement

Create and Sort Array

Join the 1M+ learners on CodeSignal

Initialize Pointers and the Result Array

Traverse the Array and Compare

Assemble the Result Array

Full Code

Complexity Analysis

Lesson Summary