Auxiliary Array.md

Auxiliary Array

For some array problems on leetcode, often we need to use some extra data structures to efficiently solve them. A useful one is so called auxiliary array. This is a typical space time tradeoff strategy. Here we use some examples to illustrate the different kinds of auxiliary arrays.

1. L/R Min/Max Array

   This array is in the same size as the input array. They contain values which are min or max of the input array at the index i from left or right. Here is a problem to which this kind of array is very useful.

   334 Increasing Triplet Subsequence

   Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

   • Example 1:

     Input: nums = [1,2,3,4,5]

     Output: true

     Explanation: Any triplet where i < j < k is valid.

   • Example 2:

     Input: nums = [5,4,3,2,1]

     Output: false

     Explanation: No triplet exists.

   • Example 3:

     Input: nums = [2,1,5,0,4,6]

     Output: true

     Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.

   The general idea is to iterate the array, and for each element search its left and right to find if there is a smaller and bigger element respectively. A naive approach then will be O(N^2). Here is when the L/R Min/Max Array gets handy. We define 2 arrays f and b as below

       f = [nums[0]]*n    
       b = [nums[-1]]*n
       for i in range(1, n):
           # f[i] min in [0, i]
           f[i] = min(f[i-1], nums[i])
       for i in range(n-2, -1, -1):
           # b[i] max in [i, n-1]
           b[i] = max(b[i+1], nums[i])
   

   With these 2 auxiliary arrays, it is much more efficient to find out the min and max elements to the left and right.

       for i in range(n):
           if nums[i] > f[i] and nums[i] < b[i]: # triplet exists
               return True
       return False