Applying the Two-Pointer Technique for Pair Sums in Go

Introduction

In this lesson, we're going to take a deep dive into an exciting technique — the two-pointer technique . This technique is a crucial skill for enhancing your algorithmic problem-solving abilities, especially when dealing with slices. In this unit, we'll apply this technique to a problem that involves a slice of integers and a target value. Let's get started!

Task Statement

Envision the problem at hand: we've been given a slice of distinct integers and a target value. The task is to find all pairs of integers from the given slice that sum up to the target value using the two-pointer technique . The function FindPairs should take this slice of integers and a target value as parameters. It should return a slice containing pairs of numbers, sorted in ascending order by the first element of each pair. If no pairs satisfy this requirement, the function should return an empty slice. Consider, for instance, an example in which you're given a slice, numbers := []int{1, 3, 5, 2, 8, -2} and target := 6 . In this case, the function should return [][]int{{-2, 8}, {1, 5}} because only these pairs from the input slice of integers add up to the target value.

The Naive Approach

The naive approach to solving this problem would be to use a pair of nested loops to check each pair of numbers. This approach would have a time complexity of O(n^2) and a space complexity of O(1) . The naive approach can be time-consuming and inefficient, particularly for large slices. Comparatively, the two-pointer technique makes the problem-solving process more efficient by eliminating unnecessary operations (repeatedly checking pairs that can't sum to the target), thus enhancing the overall performance and efficiency of the solution.

The Algorithm

We start by sorting the slice, preparing it for easier comparisons. We then apply the two-pointer technique : Two pointers, one at the start (left) and the other at the end (right), are initialized. In each iteration, we calculate the sum of the two numbers pointed to by the two respective pointers. If the sum is equal to the target value, the pair is added to the output slice, and both pointers are moved toward the center. This is because we know there are no other potential pairs with the current values of numbers[left] and numbers[right] (since the numbers are distinct). When the sum is less than the target, we move the left pointer to the right (increasing the value of numbers[left]), and when the sum is greater than the target, we move the right pointer to the left (decreasing the value of numbers[right]). This process continues until the left pointer crosses the right pointer. At this point, all potential pairs have already been identified and added to the return slice.

Join the 1M+ learners on CodeSignal

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

package main

import (
    "sort"
)

func FindPairs(numbers []int, target int) [][]int {
    // Sorting the slice
    sort.Ints(numbers)
    return [][]int{}
}

package main

import (
    "sort"
)

func FindPairs(numbers []int, target int) [][]int {
    // Sorting the slice
    sort.Ints(numbers)
    return [][]int{}
}

func FindPairs(numbers []int, target int) [][]int {
    sort.Ints(numbers)
    left := 0
    right := len(numbers) - 1
    pairs := [][]int{}
    return pairs
}

func FindPairs(numbers []int, target int) [][]int {
    sort.Ints(numbers)
    left := 0
    right := len(numbers) - 1
    pairs := [][]int{}
    return pairs
}

func FindPairs(numbers []int, target int) [][]int {
    sort.Ints(numbers)
    left := 0
    right := len(numbers) - 1
    pairs := [][]int{}

    // Using two-pointer technique to find pairs
    for left < right {
        total := numbers[left] + numbers[right]

        if total == target {
            // Add the pair to the result slice if the sum matches the target
            pairs = append(pairs, []int{numbers[left], numbers[right]})
            left++  // Move left pointer one step to the right
            right-- // Move right pointer one step to the left
        } else if total < target {
            left++  // Move left pointer one step to the right to increase the sum
        } else {
            right-- // Move right pointer one step to the left to decrease the sum
        }
    }
    return pairs // Return the slice of pairs that sum up to the target
}

// Example usage
func main() {
    numbers := []int{1, 3, 5, 2, 8, -2}
    result := FindPairs(numbers, 6)
    for _, pair := range result {
        fmt.Printf("[%d, %d]\n", pair[0], pair[1])
    }
    // Output: [-2, 8]
    //         [1, 5]
}

func FindPairs(numbers []int, target int) [][]int {
    sort.Ints(numbers)
    left := 0
    right := len(numbers) - 1
    pairs := [][]int{}

    // Using two-pointer technique to find pairs
    for left < right {
        total := numbers[left] + numbers[right]

        if total == target {
            // Add the pair to the result slice if the sum matches the target
            pairs = append(pairs, []int{numbers[left], numbers[right]})
            left++  // Move left pointer one step to the right
            right-- // Move right pointer one step to the left
        } else if total < target {
            left++  // Move left pointer one step to the right to increase the sum
        } else {
            right-- // Move right pointer one step to the left to decrease the sum
        }
    }
    return pairs // Return the slice of pairs that sum up to the target
}

// Example usage
func main() {
    numbers := []int{1, 3, 5, 2, 8, -2}
    result := FindPairs(numbers, 6)
    for _, pair := range result {
        fmt.Printf("[%d, %d]\n", pair[0], pair[1])
    }
    // Output: [-2, 8]
    //         [1, 5]
}

package main

import (
    "sort"
)

func FindPairs(numbers []int, target int) [][]int {
    // Sorting the slice
    sort.Ints(numbers)
    return [][]int{}
}

func FindPairs(numbers []int, target int) [][]int {
    sort.Ints(numbers)
    left := 0
    right := len(numbers) - 1
    pairs := [][]int{}
    return pairs
}

func FindPairs(numbers []int, target int) [][]int {
    sort.Ints(numbers)
    left := 0
    right := len(numbers) - 1
    pairs := [][]int{}

    // Using two-pointer technique to find pairs
    for left < right {
        total := numbers[left] + numbers[right]

        if total == target {
            // Add the pair to the result slice if the sum matches the target
            pairs = append(pairs, []int{numbers[left], numbers[right]})
            left++  // Move left pointer one step to the right
            right-- // Move right pointer one step to the left
        } else if total < target {
            left++  // Move left pointer one step to the right to increase the sum
        } else {
            right-- // Move right pointer one step to the left to decrease the sum
        }
    }
    return pairs // Return the slice of pairs that sum up to the target
}

// Example usage
func main() {
    numbers := []int{1, 3, 5, 2, 8, -2}
    result := FindPairs(numbers, 6)
    for _, pair := range result {
        fmt.Printf("[%d, %d]\n", pair[0], pair[1])
    }
    // Output: [-2, 8]
    //         [1, 5]
}