0%

Longest Increasing Subsequence Problem and Its Duality

In this post I will give some algorithm problem from Google OA as well as Leetcode and my thoughts on them.
Our main problem here will be the OA problem appeared in the OA practice of Google Intern 2020 Online Assesment.

Problem Description

You are given an array A representing heights of students. All the students are asked to stand in rows. The students arrive by one, sequentially (as their heights appear in A). For the i-th student, if there is a row in which all the students are taller than A[i], the student will stand in one of such rows. If there is no such row, the student will create a new row. Your task is to find the minimum number of rows created.

Write a function that, given a non-empty array A containing N integers, denoting the heights of the students, returns the minimum number of rows created.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
For example, given A = [5, 4, 3, 6, 1], the function should return 2.
Students will arrive in sequential order from A[0] to A[N−1]. So, the first
student will have height = 5, the second student will have height = 4, and so on.
For the first student, there is no row, so the student will create a new row.
Row1 = [5]
For the second student, all the students in Row1 have height greater than 4.
So, the student will stand in Row1.
Row1 = [5, 4]
Similarly, for the third student, all the students in Row1 have height greater
than 3. So, the student will stand in Row1.
Row1 = [5, 4, 3]
For the fourth student, there is no row in which all the students have height
greater than 6. So, the student will create a new row.
Row1 = [5, 4, 3]
Row2 = [6]
For the fifth student, all the students in Row1 and Row2 have height greater
than 1. So, the student can stand in either of the two rows.
Row1 = [5, 4, 3, 1]
Row2 = [6]
Since two rows are created, the function should return 2.

Assume that:

  • N is an integer within the range [1..1,000]
  • each element of array A is an integer within the range [1..10,000]

In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment

Thoughts

Original Problem

Patience. Deal cards $c_1, c_2, …, c_n$ into piles according to two rules:

  • Can’t place a higher-valued card onto a lowered-valued card.
  • Can form a new pile and put a card onto it.

Goal. Form as few piles as possible.

Dual Problem

The dual problem for this is Longest increasing subsequence. And the Problem is defined as: Given a sequence of elements $c_1, c_2, …, c_n$ from a totally-ordered universe, find the longest increasing subsequence.

Duality Proof

  • Greedy Algorithm
    • Place each card on leftmost pile that fits.
    • Observation. At any stage during greedy algorithm, top cards of piles increase from left to right.
  • Weak duality.
    • In any legal game of patience, the number of piles ≥ length of any increasing subsequence.
    • Proof.
      1) Cards within a pile form a decreasing subsequence.
      2) Any increasing sequence can use at most one card from each pile.
  • Strong duality
    • [Hammersley 1972]Min number of piles = max length of an IS; moreover greedy algorithm finds both.
    • Proof.
      Each card maintains a pointer to top card in previous pile at time of insertion.
      1) Follow pointers to obtain IS whose length equals the number of piles.
      2) By weak duality, both are optimal.

Conclusion
The length of longest increasing subsequence is equal to the smallest number of decresing subsequences.

Solution

Greedy Algorithm + Binary Search Algorithm

Time complexity: $O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#!/usr/bin/env python3
from typing import List

def get_min_row_num(student_height_arr: List[int]) -> int:
# greedy and binary search
tail_list = [0] * len(student_height_arr)
size = 0
for height in student_height_arr:
# i: start index of rows
# j: end index of rows
i, j = 0, size
while i != j:
m = int((i + j)/2)
# note here we need <= to ensure in each row is strictly decreasing
# according to the problem description
if tail_list[m] <= height:
i = m + 1
else:
j = m
tail_list[i] = height
size = max([i+1, size])
return size


def main():
assert get_min_row_num([5, 4, 3, 6, 1]) == 2
assert get_min_row_num([5, 4, 4, 3, 6, 1]) == 3

if __name__ == '__main__':
main()

DP

Time complexity: $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python3
# view it as a LNDS problem
from typing import List

def get_min_row_num(student_height_arr: List[int]) -> int:
# DP, convert to Longest Non-decreasing Subsequence Problem (LNDS)
# memo[i] LNDS including ending with arr[i]
n = len(student_height_arr)
if n == 0:
return 0
memo = [1]*n
for i in range(1, n):
for j in range(i):
if student_height_arr[i] >= student_height_arr[j]:
memo[i] = max([memo[i], memo[j]+1])
return max(memo)


def main():
assert get_min_row_num([5, 4, 3, 6, 1]) == 2
assert get_min_row_num([5, 4, 4, 3, 6, 1]) == 3

if __name__ == '__main__':
main()
  • Patience sorting
    • Deal all cards using greedy algorithm; repeatedly remove smallest card.
    • For uniformly random deck, time complexity: $O(n^{3/2})$
    • ([Persi Diaconis]Patience sorting is the fastest wayto sort a pile of cards by hand.)

Reference