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;
}

Longest Substring Without Repeating Characters

Problem Statement
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Source: https://leetcode.com/problems/longest-substring-without-repeating-characters/
Programming Language: C#
Run Time Complexity: O(n)
Space Complexity: O(n)

Solution

public int LengthOfLongestSubstring(string s)
{
    if ((s == null) || (s.Length <= 0))
        return 0;    
    else if (s.Length == 1)
        return 1;

    // Dictionary to keep track of character and index position
    Dictionary<char, int> dictionary = new Dictionary<char, int>();
    int count = 0;
    int max_count = Int32.MinValue;
    int start_marker = 0;
    int end_marker = 0;
    

    while ((start_marker < s.Length) && (end_marker < s.Length))
    {
        if (!dictionary.ContainsKey(s[end_marker]))
        {
            dictionary.Add(s[end_marker], end_marker);
        }
        else if (dictionary.ContainsKey(s[end_marker]))
        {
            // Check if the index is in between start and end marker
            if ((dictionary[s[end_marker]] >= start_marker) && (dictionary[s[end_marker]] <= end_marker))
            {
                //update the count
                count = end_marker - start_marker;

                // update the max count
                max_count = Math.Max(count, max_count);

                // set the position of start marker
                start_marker = dictionary[s[end_marker]] + 1;
            }
            // Update with the current index
            dictionary[s[end_marker]] = end_marker;
        }
        end_marker++;
    }

    // for the end condition
    max_count = Math.Max(end_marker - start_marker, max_count);

    return max_count;
}