use std::collections::HashMap;
use std::cmp::Ordering;

impl Solution {
    pub fn len_longest_fib_subseq(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut dp: HashMap<(i32, i32), i32> = HashMap::new(); // DP table storing lengths of valid subsequences

        // Iterate over each element z as a potential end of a Fibonacci-like sequence
        for k in 2..n {
            let z = arr[k];

            // Use an iterator to find all valid pairs (x, y) where x + y = z
            for (x, y) in Self::pair_sum_iterator(arr[..k].iter(), z) {
                // Apply DP transition: dp[z, y] = dp[y, x] + 1, defaulting to 2 if not found
                let cur_len = dp.get(&(y, x)).unwrap_or(&2) + 1;

                // Store computed length for (z, y)
                dp.insert((z, y), cur_len);
            }
        }

        // Return the longest found subsequence length, or 0 if none exist
        *dp.values().max().unwrap_or(&0)
    }

    /// A helper function that iterates over pairs (x, y) in a sorted array slice,
    /// finding pairs where x + y == target_sum using a two-pointer approach.
    fn pair_sum_iterator<'a>(mut iter: impl DoubleEndedIterator<Item = &'a i32>, target_sum: i32) -> impl Iterator<Item = (i32, i32)> {
        std::iter::from_fn(move || {
            let mut front = iter.next();
            let mut back = iter.next_back();

            while let (Some(&x), Some(&y)) = (front, back) {
                match (x + y).cmp(&target_sum) {
                    Ordering::Equal => return Some((x, y)), // Found a valid pair (x, y)
                    Ordering::Less => front = iter.next(),  // Increase x to increase the sum
                    Ordering::Greater => back = iter.next_back(), // Decrease y to reduce the sum
                }
            }
            None
        })
    }
}

impl Solution {
    pub fn tuple_same_product(nums: Vec<i32>) -> i32 {
        // Build vector of products for all unique pairs.
        let mut products: Vec<_> = (1..nums.len())
            .flat_map(|j| (0..j).map(|i| nums[i] * nums[j]).collect::<Vec<_>>())
            .collect();

        // Sort to group identical products.
        products.sort_unstable();

        // Group products, calculate frequency-based contributions, and sum them.
        4 * products.chunk_by(|a, b| a == b)
            .filter_map(|group| if group.len() > 1 {Some(group.len() as i32)} else {None})
            .map(|freq| freq * (freq - 1))
            .sum::<i32>()
    }
}

impl Solution {
    pub fn pivot_array(mut nums: Vec<i32>, pivot: i32) -> Vec<i32> {
        nums.sort_by_key(|&num| num.cmp(&pivot)); nums
    }
}