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 existsi, j, k

such thatarr[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

return

Given

`[1, 2, 3, 4, 5]`

,return

`true`

.
Given

return

`[5, 4, 3, 2, 1]`

,return

`false`

.**Understand the problem:**

The easiest solution for this problem is to use the same DP method for the Longest Increasing Subsequence (LIS). If then, we only need to check if the dp[i] >= 3. However, this will result in a O(n^2) time complexity. Since this problem asks for O(n) time, we need to think another solution.

The idea of the O(n) time solution is greedy. We maintain two variables m1 and m2, which denote the minimum number and next to minimum number we have seen so far. So for each number in the array, we update the minimum and next minimum. If the number if greater than both m1 and m2, then we found the increasing triplet.

**Code (Java):**

public class Solution { public boolean increasingTriplet(int[] nums) { if (nums == null || nums.length < 3) { return false; } int m1 = Integer.MAX_VALUE; int m2 = Integer.MAX_VALUE; for (int num : nums) { if (num <= m1) { m1 = num; } else if (num <= m2) { m2 = num; } else { return true; } } return false; } }

## No comments:

## Post a Comment