[LeetCode] Longest Substring Without Repeating Characters

Problem: Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Approach: Clearly it's a sliding window problem. Like in any other sliding window problem we will maintain start and end indices of current window. We can have a hash map but we can use hash set here as the occurrence of  every character in substring can't be more than one. We will keep incrementing end by 1 and for each index 'end', there could be 2 cases:

1. s[end] is not in current window means it won't be in our hash set too. We can simply add s[end] to hash set i.e. add s[end] to current window. We will also see if the current window length is more than max length then we can assign current length to max length.
2. s[end] is already in current window means it is already in our hash set. In this case we need to slide our window from the left. Means we will keep increasing start index of window and keep removing s[start] from hash set until s[end] character is removed from the hash set / current window.

In the end we will just return the max length. That's all!

Implementation in C#:

    public int LengthOfLongestSubstring(string s)

    {

        int length = s?.Length ?? 0;

        if (length <= 1)

        {

            return length;

        }

        HashSet<char> charSet = new HashSet<char>();

        int start = 0;

        int end = 0;

        int maxLen = 0;

        for ( ; end < length; ++end)

        {

            if (charSet.Contains(s[end]))

            {

                maxLen = Math.Max(maxLen, end - start);

                while (charSet.Contains(s[end]))

                {

                    charSet.Remove(s[start++]);

                }

            }

            charSet.Add(s[end]);

        }

        return Math.Max(maxLen, end - start);

    }

Complexity: O(n)

Median of 2 sorted arrays

Example: Input : ar1[] = {-5, 3, 6, 12, 15}

        ar2[] = {-12, -10, -6, -3, 4, 10}

        The merged array is :

        ar3[] = {-12, -10, -6, -5 , -3,

                 3, 4, 6, 10, 12, 15}

Output : The median is 3.

Solution: Start partitioning the two arrays into two groups of halves. The first half contains some first elements from the first and the second arrays, and the second half contains the rest elements form both arrays. Reach a condition such that, every element in the first half is less than or equal to every element in the second half.

    public double FindMedianSortedArrays(int[] nums1, int[] nums2)

    {

            if (nums1 == null && nums2 == null)

            {

                return -1;

            }

            if (nums1.Length == 0 && nums2.Length == 0)

            {

                return -1;

            }

            if (nums1.Length <= nums2.Length)

            {

                return this.FindMedianSortedArraysInternal(nums1, nums2);

            }

            else

            {

                return this.FindMedianSortedArraysInternal(nums2, nums1);

            }

        }

        private double FindMedianSortedArraysInternal(int[] nums1, int[] nums2)

        {

            int minIndex = 0, maxIndex = nums1.Length, nums1Index = 0, nums2Index = 0;

            double median = 0;

            while (minIndex <= maxIndex)

            {

                nums1Index = (minIndex + maxIndex) / 2;

                nums2Index = ((nums1.Length + nums2.Length + 1) / 2) - nums1Index;

                if (nums2Index < 0)

                {

                    maxIndex = nums1Index - 1;

                    continue;

                }

                // if num1Index = num1.Length, it means that elements from num1 in the second half is an  

                // empty set. and if num2Index = 0, it means that elements from num2 in the first half is an

                // empty set. so it is necessary to check that, because we compare elements from these two

               // groups. Searching on right  

                if (nums1Index < nums1.Length && nums2Index > 0 && nums2[nums2Index - 1] > nums1[nums1Index])

                {

                    minIndex = nums1Index + 1;

                }

                // if num1Index = 0, it means that Elements from num1 in the first half is an empty set and if 

                // num2Index = num2.Length, it means that Elements from num2 in the second half is an 

                // empty set. so it is necessary to check that, because we compare elements from these two

                // groups. searching on left

                else if (nums1Index > 0 && nums2Index < nums2.Length && nums2[nums2Index] < nums1[nums1Index - 1])

                {

                    maxIndex = nums1Index - 1; 

                }

                // Found the desired halves

                else

                {

                    // this condition happens when we don't have any elements in the first half from num1 so

                    // we returning the last element in num2 from the first half.

                    if (nums1Index == 0)

                    {

                        median = nums2[nums2Index - 1];

                    }

                    // this condition happens when we don't have any elements in the first half from num2 so

                    // we returning the last element in num1 from the first half.

                    else if (nums2Index == 0)

                    {

                        median = nums1[nums1Index - 1];

                    }

                    else

                    {

                        median = Math.Max(nums1[nums1Index - 1], nums2[nums2Index - 1]);

                    }

                    break;

                }

            }

            // If number of elements is odd there is one middle element. 

            if ((nums1.Length + nums2.Length) % 2 == 1)

            {

                return median;

            }

            // Elements from nums1 in the second half is an empty set.

            if (nums1Index == nums1.Length)

            {

                return (median + nums2[nums2Index]) / 2;

            }

            // Elements from nums2 in the second half is an empty set.

            if (nums2Index == nums2.Length)

            {

                return (median + nums1[nums1Index]) / 2;

            }

            return (median + Math.Min(nums1[nums1Index], nums2[nums2Index])) / 2;      

        }

Next Greater Element

Problem Statement:-

Given an array, print the Next Greater Element (NGE) for every element. The Next greater Element for an element x is the first greater element on the right side of x in array. Elements for which no greater element exist, consider next greater element as -1.

For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows.

Element       NGE

   4      -->   5

   5      -->   25

   2      -->   25

   25     -->   -1

Solution in JAVA int time complexity O(n) 

import java.io.*;

import java.util.*;

class nextGreater

{

    public static void nextGreat( int a[], int len)

    {

        int element, next;

        Stack mystack = new Stack();

        for(int i=0; i<len; i++)

        {   

            next = a[i];

            while(!mystack.empty())

            {

                element=(int)mystack.pop();

                if(element > next)

                {

                    //push back the element 

                    mystack.push(element);

                    break;

                }

                else

                {

                    System.out.println( element +"-------->"+next);

                }

            }

            mystack.push(a[i]);

        }

        while(!mystack.empty())

        {

            element = (int)mystack.pop();

            System.out.println( element +"-------->"+"-1");

        }

        return;

    }

    public static void main(String []args)

    {

        int a[] = {1,2,23,3,4,205,25,1,2,100,2,3,4,200,105};

        nextGreat(a,a.length);

     }

}

Minimum Initial Points to Reach Destination

Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0).

Constraints :

• From a cell (i, j) we can move to (i+1, j) or (i, j+1).
• We cannot move from (i, j) if your overall points at (i, j) is <= 0.
• We have to reach at (n-1, m-1) with minimum positive points i.e., > 0

Example

Input: points[m][n] = { {-2, -3,   3}, 

                        {-5, -10,  1}, 

                        {10,  30, -5} 

                      };

Output: 7

Explanation: 

7 is the minimum value to reach destination with 

positive throughout the path. Below is the path.

(0,0) -> (0,1) -> (0,2) -> (1, 2) -> (2, 2)

We start from (0, 0) with 7, we reach(0, 1) 

with 5, (0, 2) with 2, (1, 2) with 5, (2, 2)

with and finally we have 1 point (we needed 

greater than 0 points at the end). 

pasting the code below, please let me know if you found any bug in it.
import java.io.*;

class minInitialDP
{
    public static int max(int x, int y)
    {
        return (x>y?x:y);
    }

    public static int min(int x, int y)
    {
        return (x<y?x:y);
    }

    public static void main(String []args)
    {
        int points[][] = { {-2, -3,   3}, 
                        {-5, -10,  1}, 
                        {10,  30, -5} 
                      };

        int DP [][] = new int[3][3];

        // main code goes here 

        for(int i=0; i<3; i++)
        {
            for(int j=0; j<3; j++)
            {
                if (i==0 && j==0)
                {
                    DP[i][j] = 0;
                    continue;
                }

                if( i==0 )
                {
                    if(points[i][j-1] < 0)
                    {
                        DP[i][j] = -points[i][j-1]+DP[i][j-1]+1;       
                    }
                    else
                    {
                        DP[i][j] = DP[i][j-1];
                    }
                    continue;
                }

                if(j==0)
                {
                    if(points[i-1][j] < 0)
                        DP[i][j] = -points[i-1][j]+DP[i-1][j]+1;
                    else
                        DP[i][j] = DP[i-1][j];
                    continue;
                }

                int pi, pj;

                if(points[i][j-1] < 0)
                    pi = -points[i][j-1]+DP[i][j-1]+1;
                else
                    pi =  DP[i][j-1];

                if(points[i-1][j] < 0)
                    pj = -points[i-1][j]+DP[i-1][j]+1;
                else
                    pj = DP[i-1][j];

                DP[i][j] = min(pi, pj);
            }
        }

        for(int i=0; i<3; i++)
        {
            for(int j =0; j<3; j++)
                 System.out.print(DP[i][j] + " ");
            System.out.println("\n");
        }
    }

}

Find length of the longest consecutive path from a given starting character

Given a matrix of characters. Find length of the longest path from a given character, such that all characters in the path are consecutive to each other, i.e., every character in path is next to previous in alphabetical order. It is allowed to move in all 8 directions from a cell.

example:

for mat[][]={{a,c,d},
                     {h,b,e},
                     {i,g,f}} 
and input character 'e' o/p will be 5

At first this problem is looking easy (Indeed this is) by simply finding the next character via doing a 8 way recursion, this is doable this way but we can do it more efficiently by using dynamic programing, there can be some subproblem while we are searching for a path so we will store that paths in our dp matrix and will use it in between.

simple solution in java 

class SearchPath

{

    public static final int R=3;

    public static final int C=3;

    // matrix for tracking purpose 

    public static boolean [][] visited;

    

    //input matrix

    public static char [][] mat ={ {'a','c','d'},{ 'h','b','a'},{ 'i','g','f'}};

    

    // just storing all 8 position for iterative recurs 

    public static int [] x = {1,0,1,1,-1,-1,0,-1};

    public static int [] y = {0,1,1,-1,1,-1,-1,0};

    

    //dp storage

    public static int [][]dp;

    

    public static int max(int a, int b)

    {

        return(a>b?a:b);

    } 

    //will check if and i,j pair in matrix valid or not

    public static boolean isValid(int i, int j)

    {

        if(i<0 || j<0 || i>=R || j >=C)

            return false;

        else

            return true;

    }

    

    public static int getpath_util(char m, int r, int c)

    {

        if(!isValid(r,c) || visited[r][c] ||  m+1 != mat[r][c])

            return 0;

        if(dp[r][c]!= -1)

        {

            return dp[r][c];

        }

        

        // make this visited so in subsequent call it will not be taken into account

        

        visited[r][c] = true;

        int ans=0;

        for(int k=0; k<8; k++)

        {

            ans= max(ans, 1+getpath_util(mat[r][c], x[k]+r, y[k]+c));

        }  

        

        // unset this

        visited [r][c] = false;

        

        return dp[r][c] = ans;

        

    }

    public static void getpath(char m)

    {

        int ans=0;

        for(int i=0; i<R; i++)

        {

            for(int k=0; k<C;k++)

            {

                if(mat[i][k] == m)

                {

                    for(int j=0; j<8; j++)

                    {   

                        ans = max(ans, 1+getpath_util(m, i+x[j], k+y[j]));

                    }       

                }

            }

        }   

        System.out.println(ans);

    }

    public static void main(String[]args)

    { 

        visited  = new boolean[R][C];

        dp = new int [R][C];

        for(int i=0; i<R;i++)

            for(int k=0; k<C; k++)

                dp[i][k]=-1;

        for(int i=0; i<R;i++)

            for(int k=0; k<C; k++)

                visited[i][k]=false;

        getpath('a');

        getpath('e');

        getpath('b');

        getpath('f'); 

    }

}

Source:- gfg

Merge two sorted linked list (Recursive Approach)

Merge is one of those nice recursive problems where the recursive solution code is much cleaner than the iterative code

Node *Merge(Node * head1, Node *head2)
{
        // Base conditions

       if(! head1 || !head2)
       {
              if(!head1)
                   return head2;
              else
                   return head1;
     
        }
        else
        {

                 if(Node1.data <= Node2.data)
                 {

                        Node1.next = Merge(Node1.next, Node2)
                        return Node1;

                 }
                 else
                 {
       
                       Node2.next= Merge(Node1, Node2.next);
                       return Node2;
                 }
        }

}

[Uber][LeetCode] Trapping Rain Water

Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Input: height = [4,2,0,3,2,5]
Output: 9

Approach: Basically if we see the problem closely, we can easily figure out that the trapped water amount at any bar 'i' is as follows:

water(i) = Min (max height among all the bar in left of i, max height among all the bars in right of i ) - height(i)

We just need the sum of all of these amount to get the answer. We can achieve it using brute force approach but let's try to do better:

we can pre calculate the max height from left for every i and store in an array say leftMax and we can do the same from the right and store it in the array say rightMax. Now the calculation is something like this:

• FOR i = 1 TO n
• water += ( Min(leftMax[i], rightMax[i]) - height[i])

This approach will solve the problem in linear time but if you see it is taking extra space. Let's try to reduce it. The intuition is if till leftMax is greater than rightMax, we just calculate according to rightMax only right? (see above, we take the min only). Same thing we can say about when rightMax is greater than leftMax.

Now we can use two pointer approach one from left (index = 0) and one from right(index = n - 1) and can follow the following steps:

• WHILE left < right
• IF height[left] < height[right]
• IF height[left] > leftMax //. can't trap water 
• leftMax = height[left]
• ELSE
• water += leftMax - height[left]
• ++left;
• ELSE
• // same for right
• --right

Implementation in C#:

Approach 1:

    public int Trap(int[] height) 

    {

        int length = height?.Length ?? 0;

        if (length <= 1)

        {

            return 0;

        }

        int[] leftMax = new int[length];

        leftMax[0] = height[0];

        for (int i = 1; i < length; ++i)

        {

            leftMax[i] = Math.Max(leftMax[i - 1], height[i]);

        }

        int[] rightMax = new int[length];

        rightMax[length - 1] = height[length - 1];

        for (int i = length - 2; i >=0; --i)

        {

            rightMax[i] = Math.Max(rightMax[i + 1], height[i]);

        }

        int sum = 0;

        for (int i = 1; i < length - 1; ++i)

        {

            sum += (Math.Min(leftMax[i], rightMax[i]) - height[i]);

        }

        return sum;

    }

Approach 2:

    public int Trap(int[] height)

    {

        int length = height?.Length ?? 0;

        if (length <= 2)

        {

            return 0;

        }

        int water = 0;

        int leftMax = 0, rightMax = 0;

        int left = 0, right = length - 1;

        while (left < right)

        {

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

            {

                if (height[left] <= leftMax)

                {

                    water += leftMax - height[left];

                }

                else

                {

                    leftMax = height[left];

                }

                ++left;

            }

            else

            {

                if (height[right] <= rightMax)

                {

                    water += rightMax - height[right];

                }

                else

                {

                    rightMax = height[right];

                }

                --right;

            }

        }

        return water;

    }

Complexity: O(n)