Count almost equal pairs ii

Array Hash Table Sorting Counting Enumeration

27.0% acceptance

Feb 25, 2026

You are given an array nums of positive integers (length up to 5000, values < 10^7). Two integers x and y are almost equal if one can become the other by at most TWO digit swaps on one of them. Return the number of pairs i < j where nums[i] and nums[j] are almost equal.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(nums: Vec<i32>) -> i32 {
    use std::collections::HashMap;
    // Build frequency map: value -> count
    let mut freq: HashMap<i32, i64> = HashMap::new();
    for &v in &nums {
      *freq.entry(v).or_insert(0) += 1;
    }
    let unique_vals: Vec<i32> = freq.keys().cloned().collect();

    // For each unique value, compute all reachable values once.
    // Since R is symmetric (v ∈ R(u) ↔ u ∈ R(v)), count each pair once.
    // Use a sorted unique list and count (v, r) with r >= v only.
    let mut ans = 0i64;
    for &v in &unique_vals {
      let reachable = Self::all_within_2_swaps(v);
      let fv = freq[&v];
      for &r in &reachable {
        if r > v {
          // distinct pair (v, r): all combinations
          if let Some(&fr) = freq.get(&r) {
            ans += fv * fr;
          }
        } else if r == v {
          // same-value pairs
          ans += fv * (fv - 1) / 2;
        }
      }
    }
    ans as i32
  }

  fn all_within_2_swaps(x: i32) -> std::collections::HashSet<i32> {
    let mut set = std::collections::HashSet::new();
    let digits: Vec<u8> = format!("{:07}", x).bytes().collect(); // pad to 7 digits
    let d = digits.len();
    set.insert(x);
    // 1-swap and 2-swap
    let mut buf = digits.clone();
    for i in 0..d {
      for j in (i + 1)..d {
        buf.swap(i, j);
        set.insert(std::str::from_utf8(&buf).unwrap().parse::<i32>().unwrap());
        // 2nd swap from this state
        for ii in 0..d {
          for jj in (ii + 1)..d {
            if ii == i && jj == j { continue; }
            buf.swap(ii, jj);
            set.insert(std::str::from_utf8(&buf).unwrap().parse::<i32>().unwrap());
            buf.swap(ii, jj);
          }
        }
        buf.swap(i, j);
      }
    }
    set
  }
}