3Sum (Sorted Output)
Medium About 25 min Free, no account needed
Find all distinct triplets that sum to zero, in sorted order.
The brief
Given an integer array nums, return all distinct triplets of values
[a, b, c] with a + b + c == 0.
- Each triplet must be sorted ascending (
a <= b <= c). - The list of triplets must be sorted lexicographically.
- No duplicate triplets.
The obvious approach tries every triplet, O(n^3), and deduplicates by scanning its own results. The hidden test has 2,000 elements: over a billion triplets, so it's too slow. You need O(n2) total, with duplicate triplets avoided as you go rather than filtered afterward.
Starter code
using System;
public class Solution
{
// TODO: return all distinct value triplets summing to zero, each sorted, list sorted lexicographically.
public int[][] ThreeSum(int[] nums)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Two pointers
- Walk a sorted or symmetric sequence from both ends, or fast and slow, instead of checking every pair.
Do these first
Related katas
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.
- Container With Most Water Medium Free Pick two lines that, with the x-axis, hold the most water.
- Find the Duplicate Number Medium Free Find the one repeated value in an array of n+1 numbers from 1..n, without allocating a set to do it.
- Longest Palindromic Substring (Length) Medium Free How long is the longest palindrome hiding in the string?