15. 3Sum

package main

import (
    "sort"
)

func threeSum(nums []int) [][]int {
    sort.Ints(nums) // Sort the slice in place
    var res [][]int

    for i := 0; i < len(nums)-2; i++ {
        // Skip duplicate values for i
        if i > 0 && nums[i] == nums[i-1] {
            continue
        }
        for j, k := i+1, len(nums)-1; j < k; {
            sum := nums[i] + nums[j] + nums[k]
            if sum > 0 {
                k--
            } else if sum < 0 {
                j++
            } else {
                // Append the triplet
                res = append(res, []int{nums[i], nums[j], nums[k]})
                // Skip duplicate values for j and k
                for j < k && nums[j] == nums[j+1] {
                    j++
                }
                for j < k && nums[k] == nums[k-1] {
                    k--
                }
                j++
                k--
            }
        }
    }

    return res
}
        

Time Complexity

1. Sorting: The initial sort operation has a time complexity of O(nlogn), where n is the number of elements in the input array.
2. Nested Loops for Triplet Search: After sorting, the function uses a nested loop where the outer loop runs through each element, and the inner loop uses the two-pointer technique to find pairs that sum up to the negative of the current element pointed by the outer loop. The outer loop runs in O(n) time, and for each iteration of the outer loop, the inner while loop can run up to O(n) times in the worst case (where the two pointers move towards each other from the ends of the array segment).Therefore, the nested loop part of the algorithm has a time complexity of approximately O(n2).

Combining both parts, the dominant term for the time complexity is O(n2), making the overall time complexity of the threeSum algorithm O(nlogn)+O(n2)=O(n2). The sorting term O(nlogn) is overshadowed by the O(n2) complexity of the nested loop search.

Space Complexity

1. Sorting: The space complexity of the sorting algorithm in Go's standard library (sort.Ints) is O(logn) due to the internal use of an algorithm similar to QuickSort or similar in-place sorting algorithms, which require log-linear extra space for their call stack.
2. Output List: The space needed for storing the output depends on the number of triplets found. In the worst case, if all elements of the array are part of a valid triplet, the space complexity would be O(n3) in terms of the number of triplets stored. However, this is a very loose upper bound, as it assumes each element can form a unique triplet with every other pair of elements, which is highly unlikely in practice. A more practical consideration for space complexity related to the output would be O(m), where m is the actual number of triplets found.
3. Auxiliary Space: Apart from the space for the output, the algorithm uses constant extra space.

Thus, the overall space complexity of the algorithm is O(m)+O(logn), where m is the space required for the output. Since m can vary independently of n, and the O(logn) term is related to the sorting algorithm's space requirement, it's more precise to note that the significant factor here is the space required to store the result, making the space complexity O(m) for the output list, with an additional O(logn) space for the sorting operation.