Finding Four Elements to Match a Target Sum in Kotlin Using HashMap Optimization

Finding Four Elements to Match a Target Sum in Kotlin Using HashMap Optimization | CodeSignal Learn

Introduction

Hello there! Get ready as we delve into an exciting challenge involving list manipulation, combinatorial logic, and programming expertise. This challenge is about finding combinations in a given list where the sum equals a specified target value . Are you prepared for this intriguing quest? Great! Let's embark on this journey into the realm of problem-solving and number theory.

-10^6

O(N^4)

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

The strategic initial move is to initialize an empty HashMap . We'll use this map to store sums of all pairs of numbers in the list as keys, with indices of the number pairs as corresponding values. This strategy will be beneficial when searching for pairs that meet our conditions later. Kotlin fun findQuadSum(targetSum: Int, numbers: List<Int>): List<Int> {val length = numbers.size val sumMap = mutableMapOf<Int, MutableList<Pair<Int, Int>>>()}

Now, let's populate the HashMap . For each pair of integers in the list, we'll calculate their sum and store it as a key in the HashMap, using the indices of the pair as the values. Kotlin fun findQuadSum(targetSum: Int, numbers: List<Int>): List<Int> {val sumMap = mutableMapOf<Int, MutableList<Pair<Int, Int>>>() for (i in 0 until numbers.size - 1) {for (j in i + 1 until numbers.size) {val pairwiseSum = numbers[i] + numbers[j] // Store pairwise sums in sumMap sumMap.computeIfAbsent(pairwiseSum) { mutableListOf() }.add(Pair(i, j))}}}

For the final step, we will now scan all pairs. For each, calculate the difference between the target sum and the pair sum, searching this difference value in the HashMap . For successful searches, ensure the elements belong to distinct pairs. If we find such combinations, we return these four numbers. If all pairs are traversed without finding a valid set, we return an empty list. Kotlin fun findQuadSum(targetSum: Int, numbers: List<Int>): List<Int> {val sumMap = mutableMapOf<Int, MutableList<Pair<Int, Int>>>() // Step 2: Populate the HashMap with the sums of all pairs for (i in 0 until numbers.size - 1) {for (j in i + 1 until numbers.size) {val pairwiseSum = numbers[i] + numbers[j] sumMap.computeIfAbsent(pairwiseSum) { mutableListOf() }.add(Pair(i, j))}} // Step 3: Iterate over the sums for ((sum, pairs1) in sumMap) {val complement = targetSum - sum val pairs2 = sumMap[complement] ?: continue for ((a, b) in pairs1) {for ((c, d) in pairs2) {// Ensure all indices are distinct if (a != c && a != d && b != c && b != d) {return listOf(numbers[a], numbers[b], numbers[c], numbers[d])}}}} return emptyList()} fun main() {val numbers = listOf(5, 15, 2, 7, 8, 4) val target = 24 println(findQuadSum(target, numbers)) // Expected output: [5, 7, 8, 4]} Note that since the integers in the list are distinct, the list pairs doesn't contain pairs that share the same number, so the loop remains efficient.