[LeetCode][Uber] Russian Doll Envelopes

Problem: You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.

What is the maximum number of envelopes can you Russian doll (put one inside other) given rotation is not allowed? 

Example(taken from leetcode):

Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3 
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).

Approach: This is a longest increasing subsequence problem with the exception here that we don't have to follow any sequence here :). We can sort the input array first according to width and then according to height. Once we sort the array, we can apply LIS on it. That's all!

Implementation in C#:

        public static int MaxEnvelopes(int[][] envelopes)

        {

            if (envelopes?.Length <= 0)

            {

                return 0;

            }

            SortEnvelopes(envelopes);

            int[] lis = new int[envelopes.Length];

            lis[0] = 1;

            // Applying LIS

            for (int i = 1; i < envelopes.Length; ++i)

            {

                lis[i] = 1;

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

                {

                    if (envelopes[i][0] > envelopes[j][0] 

                        && envelopes[i][1] > envelopes[j][1]

                        && lis[i] < lis[j] + 1)

                    {

                        lis[i] = lis[j] + 1;

                    }

                }

            }

            return lis.Max();

        }

        private static void SortEnvelopes(int[][] envelopes)

        {

            System.Array.Sort(envelopes, (envlp1, envlp2) =>

            {

                int firstCompare = envlp1[0].CompareTo(envlp2[0]);

                return firstCompare != 0 ? firstCompare : envlp1[1].CompareTo(envlp2[0]);

            });

        }

Complexity: O(n^2)