Golang O(n) O(1) solution with some explanation


  • 1

    Let's call a candidate of minimum value of triplet as s, and a candidate of second minimum value as m while iterating the given array.

    For an array [1, 2, 3, 4, 5] , we can walk through like this:

    0th: [1, 2, 3, 4, 5]
          ↑ s
    
    1th: [1, 2, 3, 4, 5]
          ↑s ↑m
                
    2th: [1, 2, 3, 4, 5]
                ↑ found a larger value than m, return true.
    

    This is straight-forward. We can stop and return true if there is larger value than m. Let's call this as l.
    What if there is a smaller value than m before we find the l? Let's see the example below.

    0th: [2, 9, 4, 1, 6]
          ↑s
    1th: [2, 9, 4, 1, 6]
          ↑s ↑m
    2th: [2, 9, 4, 1, 6]
          ↑s    ↑ 4 is smaller than m=9 😨
    

    Yes, this may happen. But as you see, 4 is still larger than s and we can just shift m from 9 to 4, which makes more chance to find valid l.

    2th: [2, 9, 4, 1, 6]
          ↑s    ↑ m
    

    Okay, but then again, what happens if there is smaller number even than s before finding l ?
    This is very tricky part and honestly I didn't notice until I saw others' solution. Let's proceed to 3rd index.

    3rd: [2, 9, 4, 1, 6]
          ↑s    ↑m ↑ 1 is smaller than s = 2 😱
    

    Surprisingly, we can move s to the newly found smallest number. Why? Because we still capture m, so if there is a larger number than m, we can still know that a triplet exists ([2, 4, 6]), even if we lose the information that s = 2.

    3rd: [2, 9, 4, 1, 6]
                ↑m ↑s
    
    4th: [2, 9, 4, 1, 6]
                ↑m ↑s ↑ found larger value than m, return true.
    

    Just applying those observation in our code while iterating all elements in the array, we can successfully deliver the result.

    func increasingTriplet(nums []int) bool {
    	nlen := len(nums)
    	if nlen < 3 {
    		return false
    	}
    
    	smallest, secondSmallest := nums[0], math.MaxInt32
    	for i := 1; i < nlen; i++ {
    		switch num := nums[i]; {
    		case num < smallest:
    			smallest = num
    		case num > smallest && num < secondSmallest:
    			secondSmallest = num
    		case num > secondSmallest:
    			return true
    		}
    	}
    	return false
    }
    

    Actually this way, we may lose the information of triplet itself, so if we're asked to return the triplet, we will be upset in the interview, and it looks actually being asked at some companies like Amazon...
    Further investigation: http://www.geeksforgeeks.org/find-a-sorted-subsequence-of-size-3-in-linear-time/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.