132 Pattern

                                            
class Solution {
public:
    bool find132pattern(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) {
            return false;
        }
        
        stack<int> st;
        vector<int> minPrefix(n);
        minPrefix[0] = nums[0];
        
        for (int i = 1; i < n; i++) {
            minPrefix[i] = min(minPrefix[i - 1], nums[i]);
        }
        
        for (int j = n - 1; j >= 0; j--) {
            if (nums[j] > minPrefix[j]) {
                while (!st.empty() && st.top() <= minPrefix[j]) {
                    st.pop();
                }
                if (!st.empty() && st.top() < nums[j]) {
                    return true;
                }
                st.push(nums[j]);
            }
        }
        
        return false;
    }
};

                                            
class Solution {
    public boolean find132pattern(int[] nums) {
        if (nums.length < 3) {
            return false;
        }
        
        int n = nums.length;
        int min_i = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            min_i = Math.min(min_i, nums[j]);
            for (int k = j+1; k < n; k++) {
                if (nums[k] < nums[j] && nums[k] > min_i) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

                                            
class Solution(object):
    def find132pattern(self, nums):
        stack = []
        s3 = float('-inf')
        
        for i in range(len(nums)-1, -1, -1):
            if nums[i] < s3:
                return True
            else:
                while stack and nums[i] > stack[-1]:
                    s3 = stack.pop()
            stack.append(nums[i])
        
        return False

                                            
bool find132pattern(int* nums, int numsSize) {
    if (numsSize < 3) {
        return false;
    }
    
    int i, j, k;
    int min_i = nums[0];
    
    for (j = 1; j < numsSize - 1; j++) {
        for (k = j + 1; k < numsSize; k++) {
            if (nums[k] < nums[j] && nums[j] > min_i && nums[k] > min_i) {
                return true;
            }
        }
        min_i = fmin(min_i, nums[j]);
    }
    
    return false;
}

                                            
public class Solution {
    public bool Find132pattern(int[] nums) {
        if(nums.Length < 3) return false;
        
        int n = nums.Length;
        int[] minArr = new int[n];
        minArr[0] = nums[0];
        
        for(int i = 1; i < n; i++){
            minArr[i] = Math.Min(minArr[i-1], nums[i]);
        }
        
        Stack<int> stack = new Stack<int>();
        
        for(int j = n-1; j >= 0; j--){
            if(nums[j] > minArr[j]){
                while(stack.Count > 0 && stack.Peek() <= minArr[j]){
                    stack.Pop();
                }
                if(stack.Count > 0 && stack.Peek() < nums[j]){
                    return true;
                }
                stack.Push(nums[j]);
            }
        }
        
        return false;
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var find132pattern = function(nums) {
    const n = nums.length;
    const stack = [];
    let third = -Infinity;

    for (let i = n - 1; i >= 0; i--) {
        if (nums[i] < third) {
            return true;
        }
        while (stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            third = stack.pop();
        }
        stack.push(nums[i]);
    }

    return false;
};

                                            
function find132pattern(nums: number[]): boolean {
    const n = nums.length;
    if (n < 3) {
        return false;
    }

    const stack: number[] = [];
    let third = -Infinity;

    for (let i = n - 1; i >= 0; i--) {
        if (nums[i] < third) {
            return true;
        }

        while (stack.length > 0 && nums[i] > stack[stack.length - 1]) {
            third = stack.pop()!;
        }

        stack.push(nums[i]);
    }

    return false;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function find132pattern($nums) {
        $n = count($nums);
        $stack = [];
        $s3 = PHP_INT_MIN;
        
        for ($i = $n - 1; $i >= 0; $i--) {
            if ($nums[$i] < $s3) {
                return true;
            }
            while (!empty($stack) && $nums[$i] > end($stack)) {
                $s3 = array_pop($stack);
            }
            if ($nums[$i] > $s3) {
                $stack[] = $nums[$i];
            }
        }
        
        return false;
    }
}

                                            
class Solution {
    func find132pattern(_ nums: [Int]) -> Bool {
        var minArray = [Int](repeating: 0, count: nums.count)
        var stack = [Int]()
        
        minArray[0] = nums[0]
        for i in 1..<nums.count {
            minArray[i] = min(minArray[i-1], nums[i])
        }
        
        for j in stride(from: nums.count-1, through: 0, by: -1) {
            if nums[j] > minArray[j] {
                while !stack.isEmpty && stack.last! <= minArray[j] {
                    stack.removeLast()
                }
                if !stack.isEmpty && stack.last! < nums[j] {
                    return true
                }
                stack.append(nums[j])
            }
        }
        
        return false
    }
}

                                            
class Solution {
    fun find132pattern(nums: IntArray): Boolean {
        var third = Int.MIN_VALUE
        val stack = Stack<Int>()

        for (i in nums.size - 1 downTo 0) {
            if (nums[i] < third) {
                return true
            }
            while (stack.isNotEmpty() && nums[i] > stack.peek()) {
                third = stack.pop()
            }
            stack.push(nums[i])
        }

        return false
    }
}

                                            
class Solution {
  bool find132pattern(List<int> nums) {
    if (nums.length < 3) {
      return false;
    }
    
    int n = nums.length;
    List<int> minSoFar = List.filled(n, 0);
    minSoFar[0] = nums[0];
    
    for (int i = 1; i < n; i++) {
      minSoFar[i] = nums[i] < minSoFar[i - 1] ? nums[i] : minSoFar[i - 1];
    }
    
    List<int> stack = [];
    for (int j = n - 1; j >= 0; j--) {
      if (nums[j] > minSoFar[j]) {
        while (stack.isNotEmpty && stack.last <= minSoFar[j]) {
          stack.removeLast();
        }
        if (stack.isNotEmpty && stack.last < nums[j]) {
          return true;
        }
        stack.add(nums[j]);
      }
    }
    
    return false;
  }
}

                                            
func find132pattern(nums []int) bool {
    if len(nums) < 3 {
        return false
    }

    stack := make([]int, 0)
    third := math.MinInt64

    for i := len(nums) - 1; i >= 0; i-- {
        if nums[i] < third {
            return true
        }

        for len(stack) > 0 && nums[i] > stack[len(stack)-1] {
            third = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
        }

        stack = append(stack, nums[i])
    }

    return false
}

                                            
impl Solution {
    pub fn find132pattern(nums: Vec<i32>) -> bool {
        let n = nums.len();
        let mut stack = Vec::new();
        let mut second = std::i32::MIN;
        
        for i in (0..n).rev() {
            if nums[i] < second {
                return true;
            }
            while !stack.is_empty() && nums[i] > stack[stack.len() - 1] {
                second = stack.pop().unwrap();
            }
            stack.push(nums[i]);
        }
        
        false
    }
}

                                            
# @param {Integer[]} nums
# @return {Boolean}
def find132pattern(nums)
    n = nums.length
    min_i = []
    min_i[0] = nums[0]
    (1..n-1).each do |i|
        min_i[i] = [min_i[i-1], nums[i]].min
    end
    stack = []
    (n-1).downto(0) do |j|
        if nums[j] > min_i[j]
            while !stack.empty? && stack.last <= min_i[j]
                stack.pop
            end
            return true if !stack.empty? && stack.last < nums[j]
            stack.push(nums[j])
        end
    end
    return false
end

Explanation

To solve this coding challenge, we need to determine if a given list of integers contains a specific pattern known as the "132 pattern". This pattern is defined by the presence of three elements in the list such that their values and positions satisfy the condition \( \text{nums}[i] < \text{nums}[k] < \text{nums}[j] \) where \( i < j < k \). Essentially, we are looking for a subsequence in the array that matches this pattern. To efficiently find the 132 pattern within the list, we make use of a stack-based approach which helps us keep track of possible candidates for the \( \text{nums}[k] \) element from the right end of the array. By iterating backward through the array, we can efficiently find \( \text{nums}[j] \) and check for the \( \text{nums}[k] \) and \( \text{nums}[i] \) conditions.

Detailed Steps in Pseudocode

Initialize an empty stack to keep track of potential \( \text{nums}[k] \) elements.
Initialize a variable
s3

to keep track of the largest possible \( \text{nums}[k] \) found so far, starting as negative infinity because we want to find the smallest possible value initially.
Iterate backward through the array to analyze each element as a potential candidate for \( \text{nums}[i] \):

Check if the current element is less than
s3

. If true, this means we have identified a valid 132 pattern and we can return
True

.
If not, while the stack is not empty and the current element is greater than the topmost element of the stack, pop elements from the stack and update
s3

with these values. These elements represent potential \( \text{nums}[k] \) values.
Add the current element to the stack. This element could eventually serve as a potential \( \text{nums}[j] \).

If the loop completes and no valid 132 pattern is found, return
False

.

Pseudocode with Comments

                                            
# Initialize an empty stack to keep potential candidates for nums[k]
stack = []

# Initialize s3 which will track the largest value that could be nums[k]
s3 = -infinity

# Loop through the array in reverse order to check each element
for each element in reverse of nums:
# Check if the current element is a potential nums[i] in a 132 pattern
if current element < s3:
# If true, a valid 132 pattern is found
return True

# Update s3 and stack to keep track of potential nums[k] values
while stack is not empty and current element > top element of stack:
# Pop the top element of the stack which could be nums[k]
s3 = pop the top element of the stack

# Push the current element onto the stack. This element could be a future nums[j]
push current element onto the stack

# If the loop completes without finding any 132 pattern
return False

Step-by-Step Explanation

Initialization : We start by setting up an empty stack and a variable
s3

initialized to negative infinity. The stack will help us manage potential values for \( \text{nums}[k] \), and
s3

will keep track of the most recent candidate that meets the 132 condition.
Reverse Iteration : By iterating from the end of the list to the beginning, we aim to find the optimal candidate for \( \text{nums}[j] \) first, while simultaneously updating our candidate for \( \text{nums}[k] \) using the stack.
Checking the Pattern : For each element, we check if it could be \( \text{nums}[i] \) by comparing it to
s3

. If it is less, we immediately know we've found a valid pattern and return
True

.
Updating Stack and
s3

: If the current element is not less than
s3

, we use the stack to adjust our potential \( \text{nums}[k] \) values. We pop from the stack until the condition
current element > top of stack

is no longer valid and update
s3

with these popped elements.
Adding to Stack : Finally, we push the current element onto the stack, assuming it to be a future candidate for \( \text{nums}[j] \).
Final Check : If the loop completes without finding any valid pattern, we return
False

.

In summary, the solution leverages a stack to efficiently track and update the elements necessary to identify the 132 pattern while iterating through the input array in reverse order. This ensures that we can appropriately manage and check the conditions for the 132 pattern using the elements encountered.