LeetCode 75
Increasing Triplet Subsequence
- Problem
- LC 334
- Topic
- Array / String
- File
- official75_LC334IncreasingTripletSubsequence.java
- Path
- pkg5leetcode/official75/official75_LC334IncreasingTripletSubsequence.java
- Package
- pkg5leetcode.official75
- Command
- java pkg5leetcode/official75/official75_LC334IncreasingTripletSubsequence.java
- Approach
- Track smallest and second smallest seen so far.
- Complexity
- Time O(n), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.official75;2 3/*4 * Increasing Triplet Subsequence | LC 3345 * APPROACH: Track smallest and second smallest seen so far.6 * COMPLEXITY: Time O(n), Space O(1)7 */8public class official75_LC334IncreasingTripletSubsequence {9 static boolean increasingTriplet(int[] nums) {10 int first = Integer.MAX_VALUE, second = Integer.MAX_VALUE;11 for (int n : nums) {12 if (n <= first) first = n;13 else if (n <= second) second = n;14 else return true;15 }16 return false;17 }18 19 public static void main(String[] args) {20 check(increasingTriplet(new int[]{1,2,3,4,5}), "case1");21 check(!increasingTriplet(new int[]{5,4,3,2,1}), "case2");22 check(increasingTriplet(new int[]{2,1,5,0,4,6}), "case3");23 System.out.println("all tests passed");24 }25 26 static void check(boolean cond, String name) {27 if (!cond) throw new AssertionError("FAILED: " + name);28 System.out.println(" PASS " + name);29 }30}