Dot product of two sparse vectors

Array Hash Table Two Pointers Design

89.9% acceptance

Mar 31, 2026

1313

170

Dot Product of Two Sparse Vectors - design problem, implementation in test file

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

struct SparseVector {
  pairs: Vec<(usize, i32)>,
}

/** 
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl SparseVector {
  fn new(nums: Vec<i32>) -> Self {
    let pairs = nums
      .into_iter()
      .enumerate()
      .filter_map(|(index, value)| (value != 0).then_some((index, value)))
      .collect();

    Self { pairs }
  }
  
  // Return the dotProduct of two sparse vectors
  fn dot_product(&self, vec: SparseVector) -> i32 {
    let (mut left, mut right) = (0, 0);
    let mut result = 0;

    while left < self.pairs.len() && right < vec.pairs.len() {
      let (left_index, left_value) = self.pairs[left];
      let (right_index, right_value) = vec.pairs[right];

      if left_index == right_index {
        result += left_value * right_value;
        left += 1;
        right += 1;
      } else if left_index < right_index {
        left += 1;
      } else {
        right += 1;
      }
    }

    result
  }
}