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.
-
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
andb
as belowf = [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
-