• ← Previous
• Next →

Problem: Check If Two String Arrays are Equivalent

We can use two pointers and NOT have to construct the string. Check If Two String Arrays are Equivalent: We can use two pointers and NOT have to construct the string.

Problem: Increasing Triplet Subsequence

Given an unsorted array, return whether an increasing subsequence of length 3 exists or not in the array. We need to find three numbers in sequence (a < b < c). Here we track b and c

Basically, use three pointers. Keep track of first (smallest), second (smallest), and then compare with a[i]. You don't need to keep three variables.

The key idea is that we push first and second to smaller values, if we see one. So, that if we hit the third number, it would compare against the two smallest earlier numbers (the smallest forming a sequence)..

• Start with first as a[0].
• If you find something smaller (or equal to) than first, then make it first.
• Else, compare with second -- if it is smaller (or equal), then set second to that.
• Else, you have a found a number that is not smaller than first or second. It must be the third. So, return true.

Here is the code (in C):

 bool increasingTriplet(int* a, int len) {
     int i, first, second = INT_MAX;

     if (!len) return false;

     // first is the smallest of the three.
     first = a[0];
     for (i = 1; i < len; i++) {
         if (a[i] <= first) {
             first = a[i];
         } else if (a[i] <= second ) {
             second = a[i];
         } else {
             return true;
         }
     }
     return false;
 }

• ← Previous
• Next →