334. Increasing Triplet Subsequence (Medium)
https://leetcode.com/problems/increasing-triplet-subsequence/
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.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
Example 1:
Input: [1,2,3,4,5] Output: true
Example 2:
Input: [5,4,3,2,1] Output: false
Solutions
1.
class Solution {
// Firstly, Initialize the first and second element; Then, update the them if meets better alternatives;
// 3. Finally, return true if hit element > second.
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) {
return false;
}
int len = nums.length;
int first = nums[0];
int second = nums[0];
int i = 1;
for (; i < len; i++) {
if (nums[i] > first) {
second = nums[i];
break;
}
if (nums[i] < first) {
first = nums[i];
}
}
// second not found or second is the last one
if (i >= len - 1) {
return false;
}
// Now, we get the sort a ascending pair (one, second). But I need to point out that it doesn't
// represent they will form the final answer.
// Move on to find the third element.
i++;
for (; i < len; i++) {
if (nums[i] > second) {
return true;
}
// to reach here, subject to nums[i] <= second and nums[i-1] <= second
// Here we have 3 jobs to do:
// 1. replace second only
if (nums[i] < second && nums[i] > first) {
second = nums[i];
continue;
}
// 2. replace one and second both, must cover = situation
// [5,6,1,6,2,3], [5,6,2,3]
if (nums[i - 1] <= first && nums[i] <= second && nums[i - 1] < nums[i]) {
first = nums[i - 1];
second = nums[i];
continue;
}
// 3. ignore nums[i]
// we cannot replace one with nums[i] because of the index sequence disorder issue
}
return false;
}
}
2.
class Solution {
// This problem is too trivial and nasty. A great number of special cases need to be covered.
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) {
return false;
}
int len = nums.length;
int first = nums[0];
int second = Integer.MAX_VALUE;
int min = nums[0];
for (int i = 1; i < len; i++) {
// global minimum value
min = Math.min(min, nums[i]);
// if second is not assigned value yet
// [4,1,2], [1,3,4]
if (second == Integer.MAX_VALUE && nums[i] > nums[i - 1]) {
first = nums[i - 1];
second = nums[i];
continue;
}
// if (i-1, i) is a ascending pair
if (nums[i] > nums[i - 1]) {
// [1,5,3], (1,3) is better than (1,5)
if (nums[i - 1] > first && nums[i - 1] < second) {
second = nums[i - 1];
}
// min can be any values before i-1, so sequence min < nums[i - 1] < nums[i] meets
// the requirement.
else if (nums[i - 1] > min) {
return true;
}
// nums[i-1]<nums[i]<second, choose the minimums from both (first, nums[i-1])
// and (second, nums[i]).
else if (nums[i] < second) {
if (first < nums[i - 1]) {
second = nums[i - 1];
} else {
first = nums[i - 1];
second = nums[i];
}
// Following statements are incorrect. If first is set to nums[i-1], second
// must be nums[i]. Supposed second not change, index of second will be
// smaller than one.
// first = Math.min(first, nums[i - 1]);
// second = Math.min(second, nums[i]);
}
}
// To narrow down the search scale, no need to take the descending pair into account.
// one and second are already settled, if nums[i] > second, the ascending
// sequence of length 3 is found.
if (second != Integer.MAX_VALUE && nums[i] > second) {
return true;
}
}
return false;
}
}
Incorrect Solutions
class Solution {
// FIXME Incorrect Solution, extra space is not allowed.
// Apply a stack, walk through nums elements and push into elements smaller than
// the stack top, meanwhile pop out the larger value until current nums element can get in.
// Return directly if desired ans found.
public boolean increasingTriplet(int[] nums) {
if (nums == null || nums.length <= 2) {
return false;
}
// failed case [2,3,1,4]
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
// FIXME stack.peek() == nums[i] will still be popped.
while (!stack.isEmpty() && stack.peek() >= nums[i]) {
stack.pop();
}
stack.push(nums[i]);
if (stack.size() == 3) {
return true;
}
}
return false;
}
}