{"id":312,"date":"2020-12-23T16:21:26","date_gmt":"2020-12-23T16:21:26","guid":{"rendered":"https:\/\/www.canosielabs.com\/blog\/?p=312"},"modified":"2020-12-23T16:21:28","modified_gmt":"2020-12-23T16:21:28","slug":"increasing-triplet-subsequence","status":"publish","type":"post","link":"https:\/\/www.canosielabs.com\/blog\/increasing-triplet-subsequence\/","title":{"rendered":"Increasing Triplet Subsequence"},"content":{"rendered":"\n<p class=\"wp-block-paragraph\">Given an integer array\u00a0<code>nums<\/code>, return\u00a0<code>true<\/code><em>\u00a0if there exists a triple of indices\u00a0<\/em><code>(i, j, k)<\/code><em>\u00a0such that\u00a0<\/em><code>i &lt; j &lt; k<\/code><em>\u00a0and\u00a0<\/em><code>nums[i<\/code>] &lt; nums[j] <code>&lt; nums[k]<\/code>. If no such indices exists, return\u00a0<code>false<\/code>.<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">The inituation behind the optional solution is to undstand that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>We must traverse though the list just once.<\/li><li>We keep track 2 pointers, <code>firstValue <\/code>and <code>secondValue<\/code><\/li><li><code>firstValue <\/code>is updated if we come across a value <code>nums[i] <\/code>such that <code>nums[i]&lt;= firstValue<\/code>.<\/li><li><code>secondValue <\/code>is updated only if it is larger then <code>firstValue <\/code>and <code>nums[i] &lt;= secondValue<\/code><\/li><li>If we come to a value <code>nums[i] <\/code>such that it is larger then both <code>firstValue <\/code>and <code>secondValue<\/code>, we immediately return true since we have found a index <code>i, j, k<\/code> such that <code>nums[i] &lt; nums[j] &lt; nums[k]<\/code><\/li><\/ul>\n\n\n\n<p class=\"wp-block-paragraph\"><code>firstValue <\/code>and <code>secondValue<\/code> can be conveniently set to <strong>MAX INT<\/strong> to start off.  This guarantees that <code>firstValue <\/code>will be set to <code>num[0] <\/code>to start off.  As we traverse down the list, <code>secondValue <\/code>will only be set of it is larger then <code>firstValue<\/code>.   Otherwise <code>firstValue <\/code>will be updated.<\/p>\n\n\n\n<pre><code class=\"language-java\">class Solution {\n    public boolean increasingTriplet(int[] nums) {\n     \n        if (nums.length &lt; 3) {\n            return false;\n        }\n          \n        int first = Integer.MAX_VALUE;\n        int second = Integer.MAX_VALUE;      \n        \n        for (int i=0; i&lt;nums.length; i++) {\n            int currentValue = nums[i];\n            if (currentValue &lt;= first) {\n                first = currentValue;\n            } else if (currentValue &lt;= second) {\n                second = currentValue;\n            } else {\n                return true;\n            }                    \n        }\n        \n        return false;\n    }\n}<\/code><\/pre><br><br>\n\n\n\n<h2 class=\"wp-block-heading\">Conclusion<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">The examples that are presented along with the question are very important.  It is very common for candidates to make the mistake that i, j and k must be subsequent positions one after each other (i.e. i, j = i + 1, and k = i + 2).  <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array\u00a0nums, return\u00a0true\u00a0if there exists a triple of indices\u00a0(i, j, k)\u00a0such that\u00a0i &lt; j &lt; k\u00a0and\u00a0nums[i] &lt; nums[j] &lt; nums[k]. If no such&hellip;<\/p>\n","protected":false},"author":3,"featured_media":255,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"bgseo_title":"","bgseo_description":"","bgseo_robots_index":"index","bgseo_robots_follow":"follow","footnotes":""},"categories":[11],"tags":[10],"class_list":["post-312","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-interview-coding-questions","tag-coding-questions"],"_links":{"self":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/312","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/comments?post=312"}],"version-history":[{"count":1,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/312\/revisions"}],"predecessor-version":[{"id":313,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/posts\/312\/revisions\/313"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media\/255"}],"wp:attachment":[{"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/media?parent=312"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/categories?post=312"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.canosielabs.com\/blog\/wp-json\/wp\/v2\/tags?post=312"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}