Finding Combinations in Lists Using Go

Introduction

Hello! Prepare to explore an intriguing problem involving list manipulation and combinatorial logic using Go . We will tackle the challenge of identifying combinations in a given list that sum up to a specific target value. Ready for an exciting journey? Let's delve into the world of number theory and Go.

Task Statement

Here's your challenge: Write a Go function that accepts a slice of distinct integers and a target sum as inputs. The goal is to find exactly four numbers in the slice that, when added together, equal the target. If multiple sets satisfy this condition, your function should return any one of them. If no such combination exists, the function should return an empty slice. Take this slice as an example: [5, 15, 2, 7, 8, 4] . If your target sum is 24, a possible four-number set that adds up to this value could be [5, 7, 4, 8] . The input slice will contain at least 4 and at most 1,000 distinct integers. The input integers will be in the range of -1,000,000 to 1,000,000. The target sum will also be within the same range. The solution must run within a time limit of 3 seconds.

Estimating Program Evaluation Time

The simplest solution is the brute-force approach that iterates over every quadruple combination of numbers in the slice. The complexity of this approach is O(N^4) . Using a general assumption that each elementary operation takes a fixed small time, a brute-force O(N^4) operation with 1,000 integers would be impractical to run within 3 seconds. Therefore, it's essential to optimize the solution. A more efficient approach with an O(N^2) complexity is implemented in this lesson. By strategically managing the sums of pairs in a map for fast lookups, this solution significantly reduces the computation time, making it feasible for large datasets. These estimations underscore the importance of optimized solutions in achieving better time complexity. Our solution is fast and practical for the maximum input size requirement.

Solution Explanation

To solve this problem in Go, we utilize an optimized approach with O(N^2) time complexity, leveraging maps for efficient lookups. Conceptual Breakdown: Store Pair Sums : Use a Go map to manage all possible pairs of numbers and their corresponding sums, with sums as keys and pairs of indices as values. Finding Complement Pairs : For each pair of numbers in the slice, compute the needed complement sum from another pair and check for this in the map. Verify Distinct Indices : Ensure that none of these indices overlap with the initial pair. If valid pairs are found, return these four numbers as a result. Why This Works: Efficiency : Leveraging a map allows for rapid insertion and lookup operations, making this approach significantly faster than a brute-force solution. Scalability : This method delivers consistent performance even at its upper limit of input size, ensuring it runs within the given constraints.

Join the 1M+ learners on CodeSignal

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

Finding the Quad

Scan all pairs and, for each, compute the complement between the target sum and the pair's sum. Use the map for fast checks of this complement. Ensure that elements do not share indices across pairs, then return the four numbers if found, otherwise an empty slice.

package main

import "fmt"

func findQuadSum(targetSum int, numbers []int) []int {
    sumMap := make(map[int][][2]int)

    // Step 1: Populate map with the sums of all pairs.
    for i := 0; i < len(numbers)-1; i++ {
        for j := i + 1; j < len(numbers); j++ {
            pairwiseSum := numbers[i] + numbers[j]
            sumMap[pairwiseSum] = append(sumMap[pairwiseSum], [2]int{i, j})
        }
    }

    // Step 2: Search for complement pairs.
    for sum, pairs1 := range sumMap {
        complement := targetSum - sum
        if pairs2, found := sumMap[complement]; found {
            for _, pair1 := range pairs1 {
                for _, pair2 := range pairs2 {
                    a, b := pair1[0], pair1[1]
                    c, d := pair2[0], pair2[1]

                    // Ensure all indices are distinct.
                    if a != c && a != d && b != c && b != d {
                        return []int{numbers[a], numbers[b], numbers[c], numbers[d]}
                    }
                }
            }
        }
    }

    return []int{}
}

func main() {
    numbers := []int{5, 15, 2, 7, 8, 4}
    target := 24
    result := findQuadSum(target, numbers)
    fmt.Println(result) // Output: [5 7 8 4]
}

package main

import "fmt"

func findQuadSum(targetSum int, numbers []int) []int {
    sumMap := make(map[int][][2]int)

    // Step 1: Populate map with the sums of all pairs.
    for i := 0; i < len(numbers)-1; i++ {
        for j := i + 1; j < len(numbers); j++ {
            pairwiseSum := numbers[i] + numbers[j]
            sumMap[pairwiseSum] = append(sumMap[pairwiseSum], [2]int{i, j})
        }
    }

    // Step 2: Search for complement pairs.
    for sum, pairs1 := range sumMap {
        complement := targetSum - sum
        if pairs2, found := sumMap[complement]; found {
            for _, pair1 := range pairs1 {
                for _, pair2 := range pairs2 {
                    a, b := pair1[0], pair1[1]
                    c, d := pair2[0], pair2[1]

                    // Ensure all indices are distinct.
                    if a != c && a != d && b != c && b != d {
                        return []int{numbers[a], numbers[b], numbers[c], numbers[d]}
                    }
                }
            }
        }
    }

    return []int{}
}

func main() {
    numbers := []int{5, 15, 2, 7, 8, 4}
    target := 24
    result := findQuadSum(target, numbers)
    fmt.Println(result) // Output: [5 7 8 4]
}

Introduction

Task Statement

Estimating Program Evaluation Time

Solution Explanation

Join the 1M+ learners on CodeSignal

Initializing the Map

Populating the Map

Finding the Quad

Lesson Summary