Untitled

mail@pastecode.io avatar
unknown
python
2 years ago
1.4 kB
0
Indexable
Never
def find_132(nums):
    smallest_on_left = nums[0]
    for idx in range(1, len(nums)-1):
        i = smallest_on_left
        j = nums[idx]
        smallest_on_left = min(smallest_on_left, j)
        if j <= i:
            continue
        for idx2 in range(idx+1, len(nums)):
            if (nums[idx2] > i) and (nums[idx2] < j):
                return True
    return False

print(find_132([1,2,3,4]))
print(find_132([3,1,4,2]))
print(find_132([-1,3,2,0]))

def find_132_v2(nums):
    valid_ijs = []
    valid_ijs.append([nums[0], None])
    for idx in range(1, len(nums)):
        new_num = nums[idx]

        # Check validity of existing pairs
        for pair in valid_ijs:
            if pair[1] is not None:
                if (pair[0]<new_num) and (pair[1]>new_num):
                    return True

        # Update pairs on new number
        if new_num<min([x[0] for x in valid_ijs]):
            valid_ijs = [x for x in valid_ijs if x[1] is not None]
            valid_ijs.append([new_num, None])
            continue
        for pair in valid_ijs:
            if pair[1] is None:
                pair[1] = new_num
            else:
                pair[1] = max(pair[1], new_num)
    return False
        

print(find_132_v2([1,2,3,4]))
print(find_132_v2([3,1,4,2]))
print(find_132_v2([-1,3,2,0]))