Beats 100% 14ms Java Solutions. O(nlogn) time complexity and constant spaceO(1 solution using quicksort and BST


  • 0

    /*The basic ideal for this problem will be "quicksort" to rearrange the envelopes. We try to organize the array using the w(from smallest to highest) first. if the w is equal, then we arrange the array based on h(from highest to smallest).
    The reason is because it can reduce the work when we do the BST. By doing so, we only need to find smaller h if we want to build a valid Russian Doll.
    According to the rule, we must make sure both (w1, h1) should smaller than current envelope(w2, h2) for a longer Russian Doll Envelopes. If you think carefully about how I sort the array, It is not hard to deduce that as long as we find the smaller h, then the w must also be smaller accordingly.

    1. switch the envelops between index1 and index2. eg. [[1,2], [1,3]] -> [[1,3], [1,2]]

    2. find the index i used for quicksort. Envelopes left to the index i will smaller or equall to envelopes[i][0]. Right will higher than the envelopes[i][0].
      eg. [[1, 2], [3,1], [2, 2], [2, 3]] -> [[1,2], [2, 3], [2, 2], [3, 1]];

    3. Recursion to do quicksort. First throught the w(Smallest to highest), if equal, then the h(Highest to smallest).

    4. Using binary search to find the right place for current enveloper which will insert into the ordered envelopes(this array will contain the smallest h envelopes will form current length Russian doll).
      eg. {[2,3], [3, 4]}: the smallest h envelopes form length 1 Russian doll will be [2,3]. [3, 4] form the length 2 Russian doll.

    5. Without using the extra space, I directly store the sorted array using the envelopes. Start and End will give the range of the sorted array. */

    public class Solution
    {
    private void switchTo(int[][] envelopes, int index1, int index2)
    {
    int x = envelopes[index1][0];
    int y = envelopes[index1][1];

      envelopes[index1][0] = envelopes[index2][0];
      envelopes[index1][1] = envelopes[index2][1];
    
      envelopes[index2][0] = x;
      envelopes[index2][1] = y;
    

    }

    private int findMid(int[][] envelopes, int start, int end)
    {
    int i = start, j = end;
    while (i <= j)
    {
    if (envelopes[i][0] > envelopes[start][0] && envelopes[j][0] <= envelopes[start][0])
    {
    switchTo(envelopes, i, j);
    }
    else if (envelopes[i][0] == envelopes[start][0])
    {
    if (envelopes[i][1] < envelopes[start][1]) // if the 'w' is equal, we try to get the smallest 'h'.
    {
    switchTo(envelopes, i, start);
    }

            i++;
         }
         else if (envelopes[i][0] < envelopes[start][0])
            i++;
         else
            j--;
      }
    
      switchTo(envelopes, start, j);
    
      return j;
    

    }

    private void quickSort(int[][] envelopes, int start, int end)
    {
    if (start >= end)
    return;
    int index = findMid(envelopes, start, end);
    quickSort(envelopes, start, index - 1);
    quickSort(envelopes, index + 1, end);
    }

    private int BST(int[][] envelopes, int start, int end, int target)
    {
    int i = start, j = end;

      while (i <= j)
      {
         int mid = (i + j) / 2;
         if (envelopes[mid][1] < envelopes[target][1])
            i = mid + 1;
         else
            j = mid - 1;
      }
    
      if (i == end + 1) // extend the Russian Doll length
      {
         switchTo(envelopes, end + 1, target);
    
         return end + 1;
      }
      else
      {
         if (envelopes[target][1] < envelopes[i][1]) // Replace the current Russian Doll using smaller h envelope.
         {
            envelopes[i][0] = envelopes[target][0];
            envelopes[i][1] = envelopes[target][1];
    
         }
    
         return end;
      }
    

    }

    public int maxEnvelopes(int[][] envelopes)
    {
    int m = envelopes.length;
    if (m == 0)
    return 0;

      quickSort(envelopes, 0, m - 1);
      int start = 0, end = 0;
    
      for (int i = 1; i < m; i++)
      {
         end = BST(envelopes, start, end, i);
      }
    
      return end + 1;
    

    }
    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.