Skip to main content

Another solution for 3SUM problem

The 3SUM problem asks if a given set of n real numbers contains three elements that sum to zero.

It is a bit different solution comparing to known ones, time complexity is O(k2 + m2) where k + m <= n; what actually is the same as O(n2) but the solution is rather fast (beats 92.97% C# and 97.98% Python solutions on LeetCode).

The solution is based on the idea that in order to get zero sum we need at least one positive and one negative number. We can split the input into 2 sets, for positive and negative numbers. Zeros affect the output in the following way: 1 zero gives ability to combine triplets of positive number + negative number + zero; 3 and more zeros gives one additional result: a triplet consisting of zeros only. 

C# solution:

using System;
using System.Collections.Generic;

class Solution
{
    public IList<IList<int>> ThreeSum(int[] nums)
    {
        var result = new List<IList<int>>();

        int negativeEnd = -1;
        int positiveStart = -1;

        Array.Sort(nums);

        //hash containing negative numbers
        var negativeHash = new HashSet<int>();
        //hash containing positive numbers
        var positiveHash = new HashSet<int>();

        for (int i = 0; i < nums.Length; i++)
        {
            var item = nums[i];
            if (item > 0)
            {
                if (positiveStart == -1)
                {
                    positiveStart = i;

                    for (; i < nums.Length; i++)
                        positiveHash.Add(nums[i]);
                }
            }
            else if (item < 0)
            {
                negativeEnd = i;
                negativeHash.Add(item);
            }
        }

        var zerosCount = (positiveStart != -1 ? positiveStart : nums.Length) - negativeEnd - 1;
        //check if the result completed from zeros only is possible 
        if (zerosCount > 2)
            result.Add(new[] { 0, 0, 0 });

        //if either negative or positive numbers are absent is it not possible to create any combinations
        if (negativeEnd == -1 || positiveStart == -1)
            return result;

        //check if sum of 2 negative numbers has complementary positive number  
        CheckThree(ref nums, 0, negativeEnd, ref positiveHash, ref result);

        //check if sum of 2 positive numbers has complementary negative number
        CheckThree(ref nums, positiveStart, nums.Length - 1, ref negativeHash, ref result);

        //check if there are pairs of complementary negative and positive numbers 
        if (zerosCount > 0)
            CheckTwo(ref positiveHash, ref negativeHash, ref result);

        return result;
    }

    private void CheckTwo(ref HashSet<int> positiveHash, ref HashSet<int> negativeHash, ref List<IList<int>> result)
    {
        foreach (var item in positiveHash)
        {
            var checkedItem = -item;
            if (negativeHash.Contains(checkedItem))
                result.Add(new[] { item, 0, checkedItem });
        }
    }

    private void CheckThree(ref int[] nums, int start, int end, ref HashSet<int> opposite, ref List<IList<int>> result)
    {
        for (var i = start; i < end; i++)
        {
            var a = nums[i];
            if (i == start || a != nums[i - 1])
            {
                var jStart = i + 1;
                for (var j = jStart; j <= end; j++)
                {
                    var b = nums[j];
                    if (j == jStart || b != nums[j - 1])
                    {
                        var c = -a - b;

                        if (opposite.Contains(c))
                        {
                            result.Add(new[] { a, b, c });
                        }
                    }
                }
            }
        }
    }

}

Python solution

 class Solution(object):
 
     def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            nums.sort()
            
            self._result = list()
            self._nums = nums
            
            
            negativeEnd = -1
            positiveStart = -1
            length = len(nums)
            negativeHash = set()
            positiveHash = set()
            
            for i,item in enumerate(nums):
                if item > 0:
                    if positiveStart == -1:
                        positiveStart = i
                        positiveHash = set(nums[i:length])
                elif item < 0:
                    negativeEnd = i
                    negativeHash.add(item)
                    
            zeroCount = (positiveStart if positiveStart != -1 else length) -  negativeEnd - 1
            #check if the result completed from zeros only is possible 
            if zeroCount > 2:
                self._result.append([0, 0, 0])
                
            #if either negative or positive numbers are absent is it not possible to create any combinations
            if negativeEnd == -1 or positiveStart == -1:
                return self._result
                
            #check if sum of 2 negative numbers has complementary positive number 
            self._check3(0, negativeEnd, positiveHash)
            
            #check if sum of 2 positive numbers has complementary negative number
            self._check3(positiveStart, length-1, negativeHash)
            
            #check if there are pairs of complementary negative and positive numbers
            if zeroCount > 0:
                self._check2(positiveHash, negativeHash)
            
            return self._result
        
        def _check2(self, positiveHash, negativeHash):
            for item in positiveHash:
                checked = -item
                if checked in negativeHash:
                    self._result.append([item, 0, checked])
                    
        def _check3(self, start, end, opposite):
            slice1 = self._nums[start:end+1]
            for i, a in enumerate(slice1):
                if i == 0 or a != slice1[i-1]:
                    slice2 = slice1[i + 1:]
                    for j, b in enumerate(slice2):
                        if j == 0 or b != slice2[j - 1]:
                            c = -a -b
                            if c in opposite:
                                self._result.append([a, b, c])

Comments

Popular posts from this blog

How to merge cells with equal values in the GridView

My solution is not the first; however, I think, it is rather universal and very short - less than 20 lines of the code.

The algorithm is simple: to bypass all the rows, starting from the second at the bottom, to the top. If a cell value is the same as a value in the previous (lower) row, then increase RowSpan and make the lower cell invisible, and so forth.

The code that merges the cells is very short:
public class GridDecorator { public static void MergeRows(GridView gridView) { for (int rowIndex = gridView.Rows.Count - 2; rowIndex >= 0; rowIndex--) { GridViewRow row = gridView.Rows[rowIndex]; GridViewRow previousRow = gridView.Rows[rowIndex + 1]; for (int i = 0; i < row.Cells.Count; i++) { if (row.Cells[i].Text == previousRow.Cells[i].Text) { row.Cells[i].RowSpan = previousRow.Cells[i].RowSpan < 2 ? 2 : prev…

Merging columns in GridView/DataGrid header

As necessity to show header columns in a few rows occurs fairly often it would be good to have such functionality in the GridView/DataGrid control as an in-built feature. But meanwhile everyone solves this problem in his own way.

The described below variant of the merging implementation is based on irwansyah's idea to use the SetRenderMethodDelegate method for custom rendering of grid columns header. I guess this approach can be simplified in order to get more compact and handy code for reuse.
The code overview
As it may be required to merge a few groups of columns - for example, 1,2 and 4,5,6 - we need a class to store common information about all united columns.
[Serializable]
private class MergedColumnsInfo
{
// indexes of merged columns
public List<int> MergedColumns = new List<int>();
// key-value pairs: key = the first column index, value = number of the merged columns
public Hashtable StartColumns = new Hashtable();
// key-value pairs: key = the first column in…

JIRA REST API: Cookie-based Authentication

Three authentication methods are proposed by the JIRA REST API documentation: Basic Authentication is a simple but not very safe approach. Credentials are sent in the header on every request and encoding to Base64 is not a proper protection in this case; HTTPS connection is required. OAuth authentication - looks a bit complex and requires additional configuration at the JIRA server that is not always possible. Cookie-based Authentication - this approach seems to be the most convinient one: credentials are checked once, then the authentication cookie only is sent on subsequent requests. However, trying to use the cookie-based authentication I encountered an issue. The approach described in the documentation worked partially: I was able to create a new session and get the response containing the session cookie but all subsequent requests using this session cookie were rejected as unauthorized. Spending some time investigating this I found the cause of the issue: JSESSIONID is not th…