Problem statement

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

Problem statement taken from: https://leetcode.com/problems/3sum/

Example 1:

Example 2:

Example 3:

Explanation

Brute force

A brute force solution is to use three nested loops.

A C++ code block will look as below:

The time complexity for the above code is O(N3) and, hence the solution is not efficient.

For large arrays, the above solution will give Timeout exceeded error.

Sorting

We can reduce the time complexity to O(N²) by sorting the array first. The algorithm is similar to what we have used in earlier blog post.

Algorithm

C++ solution

Golang solution

The algorithm involves two major parts for computing time complexity. Time complexity for sorting average is O(NlogN) and the time complexity for finding the triplets is O(N²).

Hence the total time complexity is O(NlogN) + O(N²)O(N²).

Originally published at https://alkeshghorpade.me.

Software Engineer. Working Saeloun. My portfolio https://alkeshghorpade.me