FilesExpand file tree

 master

/

increasing-triplet-subsequence.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

57 lines (48 loc) · 1.41 KB

 master

/

increasing-triplet-subsequence.py

Copy path

Top

File metadata and controls

• Code
• Blame

57 lines (48 loc) · 1.41 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

# Time: O(n)

# Space: O(1)

# Given an unsorted array return whether an increasing

# subsequence of length 3 exists or not in the array.

# Formally the function should:

# Return true if there exists i, j, k

# such that arr[i] < arr[j] < arr[k]

# given 0 <= i < j < k <= n-1 else return false.

# Your algorithm should run in O(n) time complexity and O(1) space complexity.

# Examples:

# Given [1, 2, 3, 4, 5],

# return true.

# Given [5, 4, 3, 2, 1],

# return false.

import bisect

class Solution(object):

def increasingTriplet(self, nums):

"""

:type nums: List[int]

:rtype: bool

"""

min_num, a, b = float("inf"), float("inf"), float("inf")

for c in nums:

if min_num >= c:

min_num = c

elif b >= c:

a, b = min_num, c

else: # a < b < c

return True

return False

# Time: O(n * logk)

# Space: O(k)

# Generalization of k-uplet.

class Solution_Generalization(object):

def increasingTriplet(self, nums):

"""

:type nums: List[int]

:rtype: bool

"""

def increasingKUplet(nums, k):

inc = [float('inf')] * (k - 1)

for num in nums:

i = bisect.bisect_left(inc, num)

if i >= k - 1:

return True

inc[i] = num

return k == 0

return increasingKUplet(nums, 3)