Data Structure & Algorithms
  • 🖌️Unlocking the Power of Algorithms with C#
  • Data Structure
    • Data Structure
    • Big O
    • Array
    • Linked Lists
    • Stacks
    • Queues
    • Hash Tables
    • Trees
    • Graphs
    • Heap Sort
    • ParkingLot Algorithm
    • LRU cache
    • Priority Queue
  • Algorithms
    • Algorithm
    • Recursion
    • Sorting
    • Searching
    • Dynamic Programming
  • Problems
    • Array
      • Two Sum
      • Two Sum II - Input Array Is Sorted
      • Contains Duplicate
      • Maximum Subarray
      • House Robber
      • Move Zeroes
      • Rotate Array
      • Plus One
      • Find number of subarrays with even length
      • Find number of subarrays with even sum
      • Find Missing Element
      • Reduce Array Size to The Half
      • Remove Duplicates
      • Merge Sorted Arrays
      • Arrays Intersection
      • 3Sum
      • Trapping Rain Water
      • Maximum sum of a subarray
      • Longest Subarray
      • Subarray Sum Equals K
      • Container With Most Water
      • Missing Number
      • Roman to Integer
      • First Missing Positive
      • Unique Integers That Sum Up To 0
      • Integer to Roman
      • Flatten
    • String
      • Check if two strings are permutation of each other
      • String Compression
      • Palindrome Permutation
      • Determine if a string has all Unique Characters
      • One Away
      • Longest Substring Without Repeating Characters
      • Valid Palindrome
      • Valid Palindrome II
      • Backspace String Compare
      • First Unique Character in a String
      • Is Subsequence
      • URLify a given string
      • String has same characters at same position
      • Number of Ways to Split a String
      • Check whether two Strings are anagram of each other
      • Print last `n` lines of a big file or big string.
      • Multiply Strings
    • Matrix
      • Search a 2D Matrix
      • Search a 2D Matrix II
      • Rotate Matrix
      • Spiral Matrix
      • Set Matrix Zeroes
    • Bit Manipulation
      • Sum of Two Integers
      • Reverse Number
      • Reverse Number II
      • Binary Bits Count
      • Binary Bits Count II
    • Stack
      • Valid Parentheses
      • Balance or not expression
      • Decode String
    • Tree
      • Binary Tree Inorder Traversal
      • Binary Tree Preorder Traversal
      • Binary Tree Postorder Traversal
      • Binary Tree Level Order Traversal
      • Binary Tree Return All Root-To-Leaf Paths
      • Binary Tree Height-Balanced
      • Valid Binary Search Tree
      • Binary Tree Sum of all left leaves.
    • Linked List
      • Linked List Delete Middle Node
      • Merge Sorted Linked List
      • Reverse Linked List
      • Remove Duplicates from Sorted List
      • Remove Duplicates from Unsorted List
      • Linked List Cycle
    • Graph
      • The Number Of Islands
      • Number of Closed Islands
      • Max Area of Island
      • Rotting Oranges
      • Number of Provinces
      • Course Schedule
      • Surrounded Regions
      • Snakes and Ladders
      • Widest Path Without Trees
      • Knight Probability in Chessboard
      • Possible moves of knight
      • Check Knight Tour Configuration
      • Steps by Knight
      • Network Delay Time
    • Greedy
      • Best Time to Buy and Sell Stock
      • Best Time to Buy and Sell Stock II
      • Smallest Subset Array
      • Jump Game
    • Backtracking
      • Towers of Hanoi
      • Subsets
      • Combination Sum
      • Sudoku Solver
      • Word Search
    • Heap
      • Kth Largest Element in an Array
      • Top K Frequent Elements
    • Sorting
      • Order Colors String
    • Recursion
      • Number To Text
      • Divide Number
Powered by GitBook
On this page
  1. Problems
  2. Array

3Sum

Array, Two Pointers

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: 
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0

Assumptions:

  • Each input have multiple solutions.

  • The same element cannot be used twice.

  • The answer can be returned in any order.

Questions to Clarify:

  • Negative Numbers: Can the input array contain negative numbers? Yes.

  • Duplicate Numbers: Can the input array contain duplicate numbers? Yes.

  • Unique Solution: Is it guaranteed that there will always be exactly one solution? No.

  • Multiple Solutions: Should we return all possible solutions, or just one? All possible unique solutions.

  • Indices Required: Do we need to return the actual indices of the solution numbers, or just the numbers themselves? Actual indices of the solution numbers.

Additional Considerations:

  • Array Size: What are the expected size limits for the input array?

  • Time and Space Complexity: Are there any specific time or space complexity requirements for the solution?

  • Algorithm Choice: Would a specific algorithm (e.g., hash table-based or sorting-based) be preferred?

Solutions

Check sum of three elements of an array.

Approach – Brute Force Technique

Run two nested loops to check sum of three elements is equal to 0. Also avoid duplicate solution.

Steps

  1. Sort the array: The algorithm starts by sorting the input array. This is done to allow us to skip over duplicate values in the array, which ensures that the solution set does not contain duplicate triplets.

  2. Iterate over the array: The algorithm then iterates over the sorted array with three nested loops, each starting from a different index. The outer loop (i) goes from 0 to nums.Length - 2, the middle loop (j) goes from i + 1 to nums.Length - 1, and the inner loop (k) goes from j + 1 to nums.Length.

  3. Skip duplicates: At the start of each loop, the algorithm checks if the current number is the same as the previous one. If it is, the algorithm skips to the next iteration. This is done to avoid adding duplicate triplets to the result.

  4. Check for zero sum: For each triplet (nums[i], nums[j], nums[k]), the algorithm checks if their sum is zero. If it is, the triplet is added to the result list.

  5. Return the result: After all triplets have been checked, the algorithm returns the list of triplets that sum to zero.

public class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        IList<IList<int>> result = new List<IList<int>>();
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 2; i++)
        {
            if (i == 0 || (i > 0 && nums[i] != nums[i - 1]))
            {
                for (int j = i + 1; j < nums.Length - 1; j++)
                {
                    if (j == i + 1 || nums[j] != nums[j - 1])
                    {
                        for (int k = j + 1; k < nums.Length; k++)
                        {
                            if (k == j + 1 || nums[k] != nums[k - 1])
                            {
                                if (nums[i] + nums[j] + nums[k] == 0)
                                {
                                    result.Add(new List<int> { nums[i], nums[j], nums[k] });
                                }
                            }
                        }
                    }
                }
            }
        }
        return result;
    }
}

Complexity

  • Time Complexity: O(n^3)

  • Auxiliary Space: O(1)

This algorithm works by checking every possible triplet in the array. Because of the sorting and the check for duplicates, each triplet in the result is unique. However, because it uses three nested loops, its time complexity is O(n^3), which means it can be slow for large inputs.

Approach – Two Poniters Technique

As we know that two-poiner approach is good if if array in sorted order. here's a step-by-step explanation of the optimized algorithm:

Steps

  1. Sort the array: The algorithm starts by sorting the input array. This is done to allow us to skip over duplicate values in the array, which ensures that the solution set does not contain duplicate triplets.

  2. Iterate over the array: The algorithm then iterates over the sorted array with a single loop (i), which goes from 0 to nums.Length - 2.

  3. Skip duplicates: At the start of the loop, the algorithm checks if the current number is the same as the previous one. If it is, the algorithm skips to the next iteration. This is done to avoid adding duplicate triplets to the result.

  4. Initialize two pointers: For each i, the algorithm initializes two pointers, low and high. low is initialized to i + 1 and high is initialized to nums.Length - 1. The variable sum is initialized to 0 - nums[i].

  5. Move the pointers: While low is less than high, the algorithm checks the sum of nums[low] and nums[high]. If their sum is equal to sum, it means we have found a triplet that sums to zero, so it adds the triplet to the result list, increments low, and decrements high. If their sum is less than sum, it increments low, and if their sum is greater than sum, it decrements high.

  6. Skip duplicates: After finding a triplet, the algorithm again checks for duplicates by comparing nums[low] and nums[high] with their adjacent elements. If nums[low] is the same as nums[low + 1], it increments low. If nums[high] is the same as nums[high - 1], it decrements high.

  7. Return the result: After all triplets have been checked, the algorithm returns the list of triplets that sum to zero.

public class Solution
{
   public IList<IList<int>> ThreeSum(int[] nums)
   {
       IList<IList<int>> result = new List<IList<int>>();
       Array.Sort(nums);
       for (int i = 0; i < nums.Length - 2; i++)
       {
           if (i == 0 || (i > 0 && nums[i] != nums[i - 1]))
           {
               int low = i + 1, high = nums.Length - 1, sum = 0 - nums[i];
               while (low < high)
               {
                   if (nums[low] + nums[high] == sum)
                   {
                       result.Add(new List<int> { nums[i], nums[low], nums[high] });
                       while (low < high && nums[low] == nums[low + 1]) low++;
                       while (low < high && nums[high] == nums[high - 1]) high--;
                       low++; high--;
                   }
                   else if (nums[low] + nums[high] < sum)
                   {
                       low++;
                   }
                   else
                   {
                       high--;
                   }
               }
           }
       }
       return result;
   }
}

Complexity

  • Time Complexity: O(n^2)

  • Auxiliary Space: O(1)

PreviousArrays IntersectionNextTrapping Rain Water

Last updated 1 year ago