This post is completed by 1 user

  • 1
 Add to List
Medium

556. Patience Sorting - Longest Increasing Subsequence

Patience sort is a sorting algorithm  inspired by the card game "Patience" (also known as Solitaire). The key idea behind the algorithm is to sort a sequence by playing a game of patience sorting,  where piles of cards (or lists of elements) are formed, and each pile is kept sorted.

A variant of the algorithm efficiently computes the length of the longest increasing subsequence in a given array.

Example: 

Input  = [3, 7, 5, 6, 4, 2, 10, 9, 8, 12, 1]
Output: [3, 5, 6, 8, 12], length = 5
  • Earlier, we discussed the longest increasing sequence (LIS) problem using dynamic programming with a time complexity of O(n²).
  • Patience sorting is a powerful technique for optimizing solutions for longest increasing sequence (LIS) problems, reducing the time complexity from O(n²) to O(nlogn).
  • This method can help you tackle difficult dynamic programming challenges more efficiently.

Steps:

Pile Formation:

  • You cannot place a card with a higher value on top of a pile with a lower value card.
  • Place the card on the leftmost pile that fits. (use binary search - O(logn))
  • If no suitable pile is found, create a new pile for that card.
  • The number of piles after processing the entire array gives the length of the longest increasing subsequence (LIS).

Reconstructing the LIS:

  • Maintain back pointers to reconstruct the LIS by backtracking through the piles.

Merging the Piles:

  • The sorted sequence is produced by merging the piles using a min-heap or other techniques similar to a multi-way merge.

Walk Through:

Input  = [3, 7, 5, 6, 4, 2, 10, 9, 8, 12, 1]

Card 3:
No piles exist, so create the first pile: [3].
Card 7:
7 > 3, so create a new pile: [3], [7].
Card 5:
5 < 7, replace 7 in the second pile: [3], [5].
Card 6:
6 > 5, so create a new pile: [3], [5], [6].
Card 4:
4 < 5, replace 5 in the second pile: [3], [4], [6].
Card 2:
2 < 3, replace 3 in the first pile: [2], [4], [6].
Card 10:
10 > 6, so create a new pile: [2], [4], [6], [10].
Card 9:
9 < 10, replace 10 in the fourth pile: [2], [4], [6], [9].
Card 8:
8 < 9, replace 9 in the fourth pile: [2], [4], [6], [8].
Card 12:
12 > 8, so create a new pile: [2], [4], [6], [8], [12].
Card 1:
1 < 2, replace 2 in the first pile: [1], [4], [6], [8], [12].

The piles are: [1], [4], [6], [8], [12]. So, the number of piles = 5, which is the longest increasing subsequence (LIS).

Algorithm:

  • Custom binary search: This function will search for the leftmost pile where the top element is greater than or equal to the current element.
  • Patience sort: Process each element in the array and use the binary search to either place the element in an existing pile or create a new pile.

Code:

 

Output:

The length of the longest increasing subsequence is: 5

Reconstructing the LIS:

Approach:

  • Tracking pile indices:
    • Instead of just keeping the top elements of the piles, we store the index of the element in the input array for each pile. This will allow us to reconstruct the LIS later.
  • Tracking predecessors:
    • For each element in the input array, we keep a predecessor array that stores the index of the previous element in the LIS. This allows us to backtrack and reconstruct the subsequence once we know the ending element.
  • Reconstructing the LIS:
    • After processing the entire array and creating piles, we find the index of the last element of the LIS (this will be the top element of the last pile). We then backtrack using the predecessor array to reconstruct the full subsequence.

Code:

 

Output:

The length of the longest increasing subsequence is: 5
The longest increasing subsequence is: [3, 5, 6, 8, 12]

Related Problems: