rust_algorithms/other/

two_pointers.rs

//! Ikki ko'rsatkich (two pointers) texnikasi.
//!
//! **G'oya:** ichma-ich ikki tsikl (O(n²)) o'rniga, ikkita indeksni **bir yo'nalishda
//! yoki qarama-qarshi** harakatlantirib, bitta yurishda javob topamiz — O(n).
//!
//! Ko'pincha massiv **tartiblangan** bo'lishi kerak.

/// Tartiblangan massivda yig'indisi `target` ga teng ikkita son topadi.
///
/// **G'oya:** ikki ko'rsatkich — biri boshda, biri oxirida.
/// Yig'indi katta bo'lsa o'ngdagini chapga suramiz, kichik bo'lsa chapdagini o'ngga.
///
/// ```text
///  [1, 3, 4, 6, 8, 11]   target = 10
///   ↑              ↑     1 + 11 = 12 > 10 → o'ngni suramiz
///   ↑           ↑        1 + 8  = 9  < 10 → chapni suramiz
///      ↑        ↑        3 + 8  = 11 > 10 → o'ngni suramiz
///      ↑     ↑           3 + 6  = 9  < 10 → chapni suramiz
///         ↑  ↑           4 + 6  = 10 ✓
/// ```
///
/// - **Time:** O(n) (hash-jadvalsiz!), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::other::two_pointers::two_sum_sorted;
///
/// assert_eq!(two_sum_sorted(&[1, 3, 4, 6, 8, 11], 10), Some((2, 3)));
/// assert_eq!(two_sum_sorted(&[1, 2], 100), None);
/// ```
pub fn two_sum_sorted(nums: &[i64], target: i64) -> Option<(usize, usize)> {
    if nums.len() < 2 {
        return None;
    }
    let (mut chap, mut ong) = (0usize, nums.len() - 1);
    while chap < ong {
        let yigindi = nums[chap] + nums[ong];
        match yigindi.cmp(&target) {
            std::cmp::Ordering::Equal => return Some((chap, ong)),
            std::cmp::Ordering::Less => chap += 1,
            std::cmp::Ordering::Greater => ong -= 1,
        }
    }
    None
}

/// Tartiblangan massivdan takrorlarni **joyida** olib tashlaydi.
///
/// Qaytadi: yangi (noyob) elementlar soni. Massivning shu qadar boshlang'ich qismi
/// to'g'ri qiymatlarni saqlaydi.
///
/// **G'oya:** `yozish` ko'rsatkichi noyob qiymatlar uchun, `oqish` — skanerlash uchun.
///
/// - **Time:** O(n), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::other::two_pointers::remove_duplicates;
///
/// let mut v = vec![1, 1, 2, 2, 2, 3, 4, 4];
/// let n = remove_duplicates(&mut v);
/// assert_eq!(n, 4);
/// assert_eq!(&v[..n], &[1, 2, 3, 4]);
/// ```
pub fn remove_duplicates<T: PartialEq + Copy>(nums: &mut [T]) -> usize {
    if nums.is_empty() {
        return 0;
    }
    let mut yozish = 1usize;
    for oqish in 1..nums.len() {
        if nums[oqish] != nums[yozish - 1] {
            nums[yozish] = nums[oqish];
            yozish += 1;
        }
    }
    yozish
}

/// Eng ko'p suv sig'diradigan idish (container with most water).
///
/// Balandliklari berilgan ustunlardan ikkitasini tanlab, ular orasidagi
/// maksimal suv hajmini topamiz: `hajm = min(h[i], h[j]) × (j − i)`.
///
/// **G'oya:** ikki chetdan boshlaymiz va **pastroq** devorni ichkariga suramiz —
/// chunki uni qoldirib, kenglikni kamaytirish hech qachon foyda bermaydi.
///
/// - **Time:** O(n), **Space:** O(1).
///
/// # Misol
/// ```
/// use rust_algorithms::other::two_pointers::max_water_container;
///
/// assert_eq!(max_water_container(&[1, 8, 6, 2, 5, 4, 8, 3, 7]), 49);
/// assert_eq!(max_water_container(&[1, 1]), 1);
/// ```
pub fn max_water_container(heights: &[i64]) -> i64 {
    if heights.len() < 2 {
        return 0;
    }
    let (mut chap, mut ong) = (0usize, heights.len() - 1);
    let mut eng_katta = 0i64;

    while chap < ong {
        let hajm = heights[chap].min(heights[ong]) * (ong - chap) as i64;
        eng_katta = eng_katta.max(hajm);
        if heights[chap] < heights[ong] {
            chap += 1;
        } else {
            ong -= 1;
        }
    }
    eng_katta
}

/// Yig'indisi nolga teng bo'lgan barcha uchliklar (3Sum) — takrorsiz.
///
/// **G'oya:** massivni tartiblab, har bir element uchun qolganida
/// [`two_sum_sorted`] mantiqini qo'llaymiz.
///
/// - **Time:** O(n²), **Space:** O(n) (natijadan tashqari).
///
/// # Misol
/// ```
/// use rust_algorithms::other::two_pointers::three_sum_zero;
///
/// let mut r = three_sum_zero(&[-1, 0, 1, 2, -1, -4]);
/// r.sort();
/// assert_eq!(r, vec![vec![-1, -1, 2], vec![-1, 0, 1]]);
/// ```
pub fn three_sum_zero(nums: &[i64]) -> Vec<Vec<i64>> {
    let mut v = nums.to_vec();
    v.sort_unstable();
    let n = v.len();
    let mut natija = Vec::new();

    for i in 0..n.saturating_sub(2) {
        if i > 0 && v[i] == v[i - 1] {
            continue; // takror uchliklardan qochamiz
        }
        let (mut chap, mut ong) = (i + 1, n - 1);
        while chap < ong {
            let yigindi = v[i] + v[chap] + v[ong];
            match yigindi.cmp(&0) {
                std::cmp::Ordering::Equal => {
                    natija.push(vec![v[i], v[chap], v[ong]]);
                    while chap < ong && v[chap] == v[chap + 1] {
                        chap += 1;
                    }
                    while chap < ong && v[ong] == v[ong - 1] {
                        ong -= 1;
                    }
                    chap += 1;
                    ong -= 1;
                }
                std::cmp::Ordering::Less => chap += 1,
                std::cmp::Ordering::Greater => ong -= 1,
            }
        }
    }
    natija
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::util::Rng;

    #[test]
    fn two_sum_bruteforce_bilan_mos() {
        let mut rng = Rng::new(1001);
        for _ in 0..50 {
            let mut v = rng.vec(30, -30, 30);
            v.sort_unstable();
            let target = rng.range(-40, 40);

            let natija = two_sum_sorted(&v, target);
            let kutilgan_bor =
                (0..v.len()).any(|i| ((i + 1)..v.len()).any(|j| v[i] + v[j] == target));

            assert_eq!(natija.is_some(), kutilgan_bor, "target = {target}");
            if let Some((i, j)) = natija {
                assert_eq!(v[i] + v[j], target);
            }
        }
    }

    #[test]
    fn takrorlarni_olib_tashlash() {
        let mut bosh: Vec<i32> = vec![];
        assert_eq!(remove_duplicates(&mut bosh), 0);

        let mut v = vec![7];
        assert_eq!(remove_duplicates(&mut v), 1);

        let mut hammasi_teng = vec![3, 3, 3, 3];
        assert_eq!(remove_duplicates(&mut hammasi_teng), 1);

        let mut noyob = vec![1, 2, 3];
        assert_eq!(remove_duplicates(&mut noyob), 3);
    }

    #[test]
    fn idish_hajmi() {
        assert_eq!(max_water_container(&[]), 0);
        assert_eq!(max_water_container(&[5]), 0);
        assert_eq!(max_water_container(&[4, 3, 2, 1, 4]), 16);
        assert_eq!(max_water_container(&[1, 2, 1]), 2);
    }

    #[test]
    fn uchliklar_togri_va_takrorsiz() {
        let mut rng = Rng::new(1002);
        for _ in 0..20 {
            let v = rng.vec(25, -10, 10);
            let uchliklar = three_sum_zero(&v);
            for u in &uchliklar {
                assert_eq!(u.iter().sum::<i64>(), 0);
            }
            let mut nusxa = uchliklar.clone();
            nusxa.sort();
            nusxa.dedup();
            assert_eq!(nusxa.len(), uchliklar.len());
        }
        assert!(three_sum_zero(&[1, 2, 3]).is_empty());
    }
}