fork download
copy 
  1. //using 2 arrays prefix suffix sums
  2. /* class IncreasingTripletOptimized {
  3.  
  4.     public static boolean increasingTriplet(int[] b) {
  5.         int n = b.length;
  6.         if (n < 3) return false;
  7.  
  8.         int[] p = new int[n];
  9.         int[] s = new int[n];
  10.  
  11.         // Prefix minimum
  12.         p[0] = b[0];
  13.         for (int i = 1; i < n; i++) {
  14.             p[i] = Math.min(p[i - 1], b[i]);
  15.         }
  16.  
  17.         // Suffix maximum
  18.         s[n - 1] = b[n - 1];
  19.         for (int i = n - 2; i >= 0; i--) {
  20.             s[i] = Math.max(s[i + 1], b[i]);
  21.         }
  22.  
  23.         // Check condition
  24.         for (int i = 1; i <= n - 2; i++) {
  25.             if (p[i - 1] < b[i] && b[i] < s[i + 1]) {
  26.                 return true;
  27.             }
  28.         }
  29.  
  30.         return false;
  31.     }
  32.  
  33.     public static void main(String[] args) {
  34.         int[] a1 = {18, 5, 4, 3, 2, 1, 8, 10};
  35.         int[] a2 = {5, 4, 3, 2, 1, 8};
  36.  
  37.         System.out.println(increasingTriplet(a1)); // true
  38.         System.out.println(increasingTriplet(a2)); // false
  39.     }
  40. }
  41. /*
  42. //i thought it looked like stock span so below stack approach
  43. /*
  44. import java.util.Stack;
  45.  
  46. public class IncreasingTripletStack {
  47.  
  48.     public static boolean increasingTriplet(int[] arr) {
  49.         int n = arr.length;
  50.         if (n < 3) return false;
  51.  
  52.         int[] leftMin = new int[n];
  53.         int[] rightGreater = new int[n];
  54.  
  55.         // Step 1: Left smaller
  56.         leftMin[0] = Integer.MAX_VALUE;
  57.         for (int i = 1; i < n; i++) {
  58.             leftMin[i] = Math.min(leftMin[i - 1], arr[i - 1]);
  59.         }
  60.  
  61.         // Step 2: Right greater using stack (stock-span style)
  62.         Stack<Integer> st = new Stack<>();
  63.         for (int i = n - 1; i >= 0; i--) {
  64.             while (!st.isEmpty() && st.peek() <= arr[i]) {
  65.                 st.pop();
  66.             }
  67.             rightGreater[i] = st.isEmpty() ? Integer.MIN_VALUE : st.peek();
  68.             st.push(arr[i]);
  69.         }
  70.  
  71.         // Step 3: Check triplet
  72.         for (int i = 0; i < n; i++) {
  73.             if (leftMin[i] < arr[i] && arr[i] < rightGreater[i]) {
  74.                 return true;
  75.             }
  76.         }
  77.         return false;
  78.     }
  79.  
  80.     public static void main(String[] args) {
  81.         int[] a1 = {18, 5, 4, 3, 2, 1, 8, 10};
  82.         int[] a2 = {5, 4, 3, 2, 1, 8};
  83.  
  84.         System.out.println(increasingTriplet(a1)); // true
  85.         System.out.println(increasingTriplet(a2)); // false
  86.     }
  87. }
  88. */
  89. class IncreasingSubsequence {
  90.     public static boolean increasingTriplet(int[] nums) {
  91.         // Initialize the first and second minimums
  92.         int min1 = Integer.MAX_VALUE;
  93.         int min2 = Integer.MAX_VALUE;
  94.         // wrong logic The variable c is incremented every time a number greater than min1 is found, 
  95.         // but this does not necessarily indicate that an increasing triplet is being formed. I
  96.         /*int c=0;
  97.         for (int num : nums) {
  98.             if (num < min1) { // assume no same nums
  99.                 min1 = num; 
  100.             } else {
  101.                 c++; // means we found a greater element than min1
  102.                 if (c==3)  return true; // Found an increasing triplet
  103.             }
  104.         }
  105.          */   
  106.         for (int num : nums) {
  107.             if (num <= min1) {
  108.                 min1 = num; // Update min1
  109.             } else if (num <= min2) {
  110.                 min2 = num; // Update min2
  111.             } else {
  112.                 // Found a number greater than both min1 and min2
  113.                 return true; // Found an increasing triplet
  114.             }
  115.         }
  116.         return false; // No increasing triplet found
  117.     }
  118.  
  119.     public static void main(String[] args) {
  120.         int[] array1 = {18, 2,5, 7, 3, 4};
  121.         int[] array2 = {5, 4, 3, 2, 1, 8};
  122.  
  123.         System.out.println(increasingTriplet(array1)); // Output: true
  124.         System.out.println(increasingTriplet(array2)); // Output: true
  125.     }
  126. }
  127.  
Success #stdin #stdout 0.11s 52584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
false
https://ideone.com/c4lc84
language:
Java (HotSpot 12)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!