using System;

using System.Collections.Generic;

public class Program

{

    public static void Main()

    {

        // 2 Pointers 

        // https://leetcode.com/problems/container-with-most-water/description/

        int[] height = new int[]{1,8,6,2,5,4,8,3,7};

        int result = Pointers.ContainerMostWater(height);

        Console.WriteLine($"#container-with-most-water#\nMax area for the container with most water is {result}.\n");

        // 2 Pointers

        // https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

        int [] sortedNumbers = new int[]{2,7,11,15};

        int target = 9;

        int [] twoSumSortedResult = Pointers.TwoSumIISorted(sortedNumbers, target);

        Console.WriteLine($"#two-sum-ii-input-array-is-sorted#\nFor sorted input array, index {twoSumSortedResult[0]} and index {twoSumSortedResult[1]} sum up to {target}.\n");

        // 2 Pointers

        // https://leetcode.com/problems/3sum/description/

        int [] numbers3Sum = new int[]{-1,0,1,2,-1,-4};

        IList<IList<int>> result3Sum = Pointers.ThreeSum(numbers3Sum);

        Console.WriteLine("#3Sum#\nResult is: ");

        foreach(var n in result3Sum)

        {

            for(int i = 0; i < n.Count; i++)

            {

                Console.Write($"{n[i]} ");

            }

            Console.WriteLine();

        }

        Console.WriteLine();

        // Sliding window

        // https://leetcode.com/problems/longest-substring-without-repeating-characters/

        string s = "pwwkew";

        int lengthOfLongestSubstring = Pointers.LongestSubstringWithoutRepeatingCharacters(s);

        Console.WriteLine($"#LongestSubstringWithoutRepeatingCharacters#\nLongest substring without repeating characters in {s} is {lengthOfLongestSubstring}\n");

        // Sliding window

        // https://leetcode.com/problems/maximum-sum-of-distinct-subarrays-with-length-k/

        int[] nums = new int[]{1,5,4,2,9,9,9};

        int k = 3;

        long maxSumOfDistinctSubbarays = Pointers.MaxSumOfDistinctSubbarraysWithLengthK(nums,k);

        Console.WriteLine($"#MaxSumOfDistinctSubbarraysWithLengthK#\nMaximum sum of distinct subbarrays with length K = {maxSumOfDistinctSubbarays}");

    }

}

​

public static class Pointers

{

    public static long MaxSumOfDistinctSubbarraysWithLengthK(int[] nums, int k)

    {

        int left = 0;

        long currentSum = 0;

        long maxSum = 0;

        HashSet<int> window = new();

        for(int right = 0; right < nums.Length; right++)

        {

            while(window.Contains(nums[right]))

            {

                window.Remove(nums[left]);

                currentSum -= nums[left];

                left++;

            }

            window.Add(nums[right]);

            currentSum += nums[right];

            if(right - left + 1 == k)

            {

                maxSum = Math.Max(maxSum, currentSum);

                window.Remove(nums[left]);

                currentSum -= nums[left];

                left++;

            }

        }

        return maxSum;

    }

    public static int LongestSubstringWithoutRepeatingCharacters(string s)

    {

        if(s.Length <= 1) return s.Length;

        int longestSubstring = int.MinValue;

        HashSet<char> temp = new();

        int left = 0;

        for(int right = left; right < s.Length; right++)

        {

            while(temp.Contains(s[right]))

            {

                temp.Remove(s[left]);

                left++;

            }

            temp.Add(s[right]);

            longestSubstring = Math.Max(longestSubstring, right - left + 1);

        }

        return longestSubstring;

    }

    public static IList<IList<int>> ThreeSum(int[] nums)

    {

        IList<IList<int>> result = new List<IList<int>>();

        Array.Sort(nums);

        for(int i = 0; i < nums.Length; i++)

        {

            if(nums[i] > 0) break;

            if(i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i, right = nums.Length - 1;

            while(left < right)

            {

                int sum = nums[i] + nums[left] + nums[right];

                if(sum < 0) left++;

                else if(sum > 0) right--;

                else

                {

                    result.Add(new List<int>(){

                        nums[i], nums[left], nums[right]

                    });

                    left++;

                    right--;

                    while(left < right && nums[left] == nums[left - 1]) left++;

                }

            }

        }

        return result;

    }

    public static int[] TwoSumIISorted(int[] nums, int target)

    {

        int left = 0;

        int right = nums.Length - 1;

        while(left < right)

        {

            if(nums[left] + nums[right] < target) left++;

            if(nums[left] + nums[right] > target) right--;

            else

            {

                return new int[]{left + 1, right + 1};

            }

        }

        return new int[2];

    }

    public static int ContainerMostWater(int [] heights)

    {

        if(heights.Length == 1) return -1;

        int left = 0;

        int right = heights.Length - 1;

        int maxArea = int.MinValue;

        while(left < right)

        {

            int area = (right - left) * Math.Min(heights[left], heights[right]);

            maxArea = Math.Max(maxArea, area);

            if(heights[left] < heights[right])

            {

                left++;

            }

            else

            {

                right--;

            }

        }

        return maxArea;

    }

}