Beyond Big O: A Comprehensive Performance Analysis of K-Sum Pair Solutions (Sorting vs. Hashmap)

As software developers, we often rely on the theoretical time complexity of an algorithm to gauge its efficiency. A lower asymptotic complexity is generally preferred, suggesting better performance as the input size grows. However, the real world often throws curveballs, and sometimes, an algorithm with a seemingly “worse” complexity can outperform its theoretically superior counterpart.

Recently, while exploring the classic LeetCode problem Max Number of K-Sum Pairs , this intriguing phenomenon came to the forefront. The problem asks us to find the maximum number of pairs in a given array of integers nums that sum up to a target value k.
Let’s analyze two common approaches to solve this problem using Kotlin.

Solution 1: The Hash Map Approach

class Solution {
    fun maxOperations(nums: IntArray, k: Int): Int {
        var freqMap = HashMap<Int, Int>()
        var maxOp = 0
        for(i in 0..nums.size - 1) {
            if(freqMap.containsKey(k-nums[i])) {
                maxOp++
                freqMap.put(k-nums[i], freqMap.getOrDefault(k-nums[i], 0) - 1)
                if(freqMap.get(k-nums[i]) == 0) {
                    freqMap.remove(k-nums[i])
                }
            } else {…