3 SUM

Problem Statement

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

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Source: https://leetcode.com/problems/3sum/
Programming Language: C#
Run Time Complexity: O(n^2)

After sorting the input array, 3 three pointers are initialized.
The first pointer goes from index 0 to index end-2.
The 2nd pointers goes from the current element(1st pointer) index + 1
The 3rd pointers goes from the last element in a reverse order.

Two iterations:
1. 1st pointer from 0 to index end-2
2. while (2nd<3rd)

Conditions:
1. if (array[1st]+array[2nd]+array[3rd]==0), get one result
2. if (array[1st]+array[2nd]+array[3rd]>0), 3rd -1
3. if (array[1st]+array[2nd]+array[3rd]<0), 2nd +1

Solution

public IList<IList<int>> ThreeSum(int[] num)
{
    IList<IList<int>> Resultset3Sum = new List<IList<int>>();

    if ((num == null) || (num.Length < 3))
        return Resultset3Sum;

    // sort array
    List<int> numList = num.ToList();
    numList.Sort();

    for (int i = 0; i < numList.Count - 2; i++)
    {
        // //avoid duplicate solutions
        if (i == 0 || numList[i] > numList[i - 1])
        {

            int start = i + 1;
            int end = numList.Count - 1;

            while (start < end)
            {
                //case 1
                if (numList[i] + numList[start] + numList[end] == 0)
                {
                    List<int> temp = new List<int>();
                    temp.Add(numList[i]);
                    temp.Add(numList[start]);
                    temp.Add(numList[end]);

                    Resultset3Sum.Add(temp);
                    start++;
                    end--;
                    
                    //avoid duplicate solutions
                    while (start < end && numList[end] == numList[end + 1])
                        end--;

                    while (start < end && numList[start] == numList[start - 1])
                        start++;                    
                }
                //case 2
                else if (numList[i] + numList[start] + numList[end] < 0)
                {
                    start++;                    
                }
                //case 3
                else
                {
                    end--;
                }
            }
        }
    }
    return Resultset3Sum;
}

Container With Most Water

Problem Statement

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

Source: https://leetcode.com/problems/container-with-most-water/
Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: Constant space

Analysis:
In order to maximize the area we need to find out the farthest points with maximum possible.

Solution

public int MaxArea(IList<int> height)
{
    // Input validation
    if ((height == null) || (height.Count <= 1))
        return 0;

    // Track maxArea found so far
    int maxArea = Int32.MinValue;
    // Start index 
    int low = 0;
    // End Index
    int high = height.Count - 1;

    // While low is less than high
    while (low < high)
    {
        // Area equal to difference of high and low and min of heigh at that index
        int area = (high - low) * Math.Min(height[low], height[high]);

        // If area is greater than maxArea update
        maxArea = Math.Max(area, maxArea);

        // in an attemt to maximize the area 
        // increment the low if height at low is less than height at high
        if (height[low] < height[high])
            low = low + 1;
        // else decrement high
        else
            high = high - 1;
    }
    return maxArea;
}

Two Sum

Problem Statement

 

Given an array of integers, find two numbers such that they add up to a specific target number.

 

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

 

Please note that your returned answers (both index1 and index2) are not zero-based.

 

You may assume that each input would have exactly one solution. Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

 

Source: https://leetcode.com/problems/two-sum/
Programming Language: C#
Run Time Complexity: O(N)
Space Complexity: O(N)

Solution 
 

public Tuple<int, int> TwoSum(int[] numbers, int target)
{
    // Maintain map for the integers to have O(1) lookup
    Dictionary<int, int> dictionary = new Dictionary<int, int>();
            
    for (int index = 0; index < numbers.Length; index++)
    {
        // If exists in the map
        if (dictionary.ContainsKey(target - numbers[index]))
        {
            // Output is expected ordered by index
            if (index < dictionary[target - numbers[index]])
                return new Tuple<int, int>(index + 1, dictionary[target - numbers[index]] + 1);
            else
                return new Tuple<int, int>(dictionary[target - numbers[index]] + 1, index + 1);
        }
        else
        {
            if (!dictionary.ContainsKey(numbers[index]))
                dictionary.Add(numbers[index], index);
        }
    }

    // Return null if solution not found
    return null;
}