Skip to main content

LeetCode Problem #15. 3Sum


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.

Example :

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]
this problem is medium but I think it is much harder especially with the condition of non duplicate,  I'll write two solutions 
#First Solution
We want to find all triplets  (a,b,c)  such that  a+b+c=0 . In other words,  c=−(a+b) . The most straightforward  O(n^2)  solution is to enumerate all  (a,b)  pairs and check if the value  c  exists in the array, using a hash table. However, we can achieve a O(n^2) solution without extra data structures .

  1. Lets sort the given v array in ascending order. For all triplets  (i,j,k),i < j < k , we have  v[i] ≤ v[j] ≤ v[k] .

  2. If we enumerate all pairs  (i,j),i < j , the corresponding sum for a fixed i is non-decreasing:  v[i] + v[j] ≤ v[i] + v[j+1] ≤ v[i] + v[j+2] ≤ … ≤ v[i] + v[n] .
  3. Conversely,  −(v[i] + v[j]) ≥ −(v[i] + v[j+1]) ≥ −(v[i] + v[j+2])...≥ −(v[i] + v[n]) .
  4. This means that for a fixed i, if we check all values j, such that  i < j ≤ n , in increasing order, the index k corresponding to c, is decreasing. So, we can initialize an index k to the last position of the array and always decrease it when looking for a suitable value c.
  5. To ignore duplicates, note that we never want to consider consecutive indices i or j with the same value.
#Second Solution
the previous solution is good but its performance is not the best, we can optimize the performance by replacing for loops with while loop.
we know we need to find triplets (a,b,c) we already have a = nums[i] we can now slove 3Sums with 2Sums problem, we need to find b & c 
where b is greater than a, and c is greater than b.


  1. initialize low pointer low = i+1
  2. initialize high pointer high= n-1
  3. if sum (nums[i], nums[low], nums[high] == 0) this means we found a solution 
  4. if sum (nums[i], nums[low], nums[high] > 0) this means we need to decrease high--
  5. if sum (nums[i], nums[low], nums[high] < 0) this means we need to increase low++
check this version of code and check performance difference.
Thank you,
 Ahmed Ghazey

Comments

Post a Comment

Popular posts from this blog

DevExpress C# Chart Tutorial

Hello , this blog post about Charting in DevExpress , I faced many problems I visited hundreds of pages to solve this problems , actually it was the first time I use DevExpress Charts, Work is not like school or university , in school if you don't know thing you can learn it any time you want , in work you have to do today task yesterday, I like to share my knowledge and skills with you , I hope this Post help you . // clear series on chart  chart.Series.Clear(); // clear Titles of chart chart.Titles.Clear(); // legend alignment  chart.Legend.AlignmentHorizontal = LegendAlignmentHorizontal.Center; chart.Legend.AlignmentVertical = LegendAlignmentVertical.Bottom; chart.Legend.Direction = LegendDirection.LeftToRight; // creating series // series view Type example Line DevExpress.XtraCharts.Series series = new DevExpress.XtraCharts.Series("series name ", ViewType.Line); // add title  DevExpress.XtraCharts.ChartTitle chtTitle = new DevExpress.XtraCharts.Cha...
3 comments
Read more

Recursion

Recursion is a programming technique which function calls itself , this seems strange , however it is one of the most interested and effective technique in programming. it helps you write code in less statements and provides unique conceptual frame work to solve problems. lets discus some problems to know how it works : first example Triangular Numbers : it is series like : 1,3,6,10,15,21........ etc our program should get the nth term in the series, the numbers in this series called triangular numbers due to they can be visualized as a triangle. triangular numbers fig 1 finding the nth term using a loop see this figure : loop adding 1+2+3+4 and so on code is easy  , a loop will add numbers from n to 0 like this int triangle(int n) { int total = 0; while(n > 0) // until n is 1 { total = total + n; // add n (column height) to total --n; // decrement column height } return total; } it easy enough and for sure it is fast . before we start the recu...
2 comments
Read more

LeetCode Problem #19 Remove Nth Node From End of List

Solution for LeetCode Problem #19 Remove Nth Node From End of List it is linked list problem can be solved with multiple solutions, but I'm gonna solve it with fastest solution in java. Problem link we should assign dummy_head it is common while solving linked list problems  Assign 2 iterators slow and fast both equals to dummy_head we don't know the length of the list but we know it is always valid, so we will move with a window of size n+1 when we reach the end by the fast iterator the slow iterator will be in the node n+1 from the last , right? we will assign slow.next to be equal slow.next.next we are dropping the node n from last, got it? we will return dummy_head.next Thank you, AhmedG
Post a Comment
Read more