leetcode day 30 – definitely struggling

3 sum: given a list of numbers, find all distinct triples that sum to 0. The hint was to transform this to a 2 sum problem, and look for the 2 sum that solves the problem for the current index.

My initial try spent a lot of effort trying to track the used values in maps, and I did not learn my lesson: when the solution feels too hard, you’re probably doing it wrong.

After I ran out of time, I started looking at solutions; I had started trying to sort the answers and see if there were duplicates, and it sort of worked, but failed some test cases in a non-obvious way.

The real attack for this kind of problem starts out by sorting the numbers first. You can then start depending on math identities to help winnow the solutions, eliminate duplicates, and shrink the search space all at once.

Here’s the solution that was clearest, with my comments and variable name adjustments to make the code clearer yet.

func threeSum(nums []int) [][]int {
    // Output slice.
    out := [][]int{}
    // Sort the numbers ascending first.
    sort.Ints(nums)

    var left, right, sum int

    // We're going to search for three terms. We're going to just move
    // left to right for the first one.
    for first, target := range nums {
        // Skip duplicate terms at the start. We always look at nums[0]
        // and start deduping after that.
        if i > 0 && a == nums[i-1] {
            // Same as previous so any solutions using this would be dups.
            // Skip to the next item.
            continue
        }
        // Start with second item just after the first and third at the end.
        second, third = first + 1, len(nums) - 1
        // As long as the second pointer hasn't hit the third, keep looking.
        for second < third {
            // calculate the sum
            sum = target + nums[second] + nums[third]
            if sum == 0 {
                // This is a solution, save it.
                out = append(out, []int{target, nums[second], nums[third]})
                // Skip duplicates of the second term. We increment once to
                // move to the item after the one we're dedeuping.
                second++
                for second < third && nums[second] == nums[second-1] {
                    second++
                }
            } else if sum < 0 {
                // second number is too small to work; third is the largest
                // as-yet-unused value, so the second has to be larger to
                // move the sum closer to zero.
                second++
            } else { // sum is > 0
                // third number is too large to work. The second number is
                // already the smallest possible for the next solution, so
                // we have to reduce the third to move closer to zero.
                third--
            }
        }
    }
    return out
}

This is good clever as opposed to bad clever, as it’s clear how this actually works. Notice how we keep shrinking the search space as we move the first pointer upward, and how the duplicate elimination at the first and second pointers speeds this up even further. We’re still O(N^2), but we’re discarding as much possible duplicate work as we can.

This is the kind of problem that I find quite difficult; I am not very friendly with numbers, despite a lot of programming over the years. I have spent more time chasing control block chains and securing inputs than I have shuffling numbers, and it shows: I have a lot less trouble with linked lists than these numerical problems.

Not feeling great about my chances to pass one of these live at the moment. Maybe it’s just “more practice needed”. I hope it is, anyway.