C# - O(kn), coded for any increasing K-let subsequence


  • -2
    A

    It tracks k smallest sequences which has length less then k.

    public bool IncreasingTriplet(int[] nums) 
    {
        int k = 3;
        if(nums == null || nums.Length < k) return false;
        
        int[] seq = new int[k];
        for(int i = 0; i < k; i++) seq[i] = int.MaxValue;
        
        foreach(int aNum in nums)
        {
            for(int j = 0; j < seq.Length; j++)
            {
                if(aNum <= seq[j])
                {
                    seq[j] = aNum;
                    if(j == seq.Length - 1) return true;
                    else break;                    
                }
            }
        }
        
        return false;
    }

Log in to reply
 

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