[코딩 인터뷰][LeetCode] – Increasing Triplet Subsequence

Posted on by

※ 이 포스트는 LeetCode 코딩 인터뷰 문제인 Increasing Triplet Subsequence의 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, LeetCode에서의 Submission 통과만을 보장합니다.

문제 정보

문제 출처 : https://leetcode.com/problems/increasing-triplet-subsequence/
카테고리 : DP(?), Greedy(?)
난이도 : 쉬움

문제 설명

어떤 정수 리스트 A가 주어졌을 때, i < j < k이고, A[i] < A[j] < A[k]인 (i, j, k)가 존재하는지를 리턴하여라

문제 풀이

Simple – O(N)의 방법

배열 Min, Max를 정의한다.
Min[i]는 인덱스 A[0] ~ A[i]의 수 중에서 가장 작은 값을 저장한다.
Max[i]는 A[i] ~ A[size – 1] 중에서 가장 큰 값을 저장한다.
A[i]에 대해 A[i]와 Min[i]를 비교해서 A[i] > Min[i]이면, i 이전에 A[i] > A[j]인 j가 있다는 말이다.
같은 원리로 A[i]와 Max[j]를 비교해서 A[i] < Max[i]이면, i 이후에 A[i] < A[j]인 j가 있다는 말이다.
따라서 모든 i에 대해 Min[i] < A[i] < Max[i]인 i가 존재하면 True를 리턴하고, 아니면 False를 리턴하면 된다.

코드
class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        
        # Return False on minimum size exception
        if len(nums) < 3:
            return False
        
        # Init Size
        size = len(nums)
        Min, Max = [0] * size, [0] * size
        
        # Init Min, Max array
        Min[0] = nums[0]
        for i in range(1, size):
            Min[i] = min(nums[i], Min[i - 1])
        Max[size - 1] = nums[size - 1]
        for i in reversed(range(len(nums) - 1)):
            Max[i] = max(nums[i], Max[i + 1])
        
        # Compare nums[i] with min before i and max after i
        for i in range(1, size - 1):
            if Min[i] < nums[i] and nums[i] < Max[i]:
                return True
        return False

코딩 인터뷰 – Increasing Triplet Subsequence