Skip to content

1570. Dot Product of Two Sparse Vectors 👍

Approach 1: Hash Table

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class SparseVector {
 public:
  SparseVector(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i)
      if (nums[i])
        indexToNum[i] = nums[i];
  }

  // Returns the dot product of the two sparse vectors.
  int dotProduct(SparseVector& vec) {
    if (indexToNum.size() < vec.indexToNum.size())
      return vec.dotProduct(*this);

    int ans = 0;

    for (const auto& [index, num] : vec.indexToNum)
      if (const auto it = indexToNum.find(index); it != indexToNum.cend())
        ans += num * it->second;

    return ans;
  }

 private:
  unordered_map<int, int> indexToNum;  // {index: num}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class SparseVector {
  SparseVector(int[] nums) {
    for (int i = 0; i < nums.length; ++i)
      if (nums[i] != 0)
        indexToNum.put(i, nums[i]);
  }

  // Returns the dot product of the two sparse vectors.
  public int dotProduct(SparseVector vec) {
    if (indexToNum.size() < vec.indexToNum.size())
      return vec.dotProduct(this);

    int ans = 0;

    for (final int index : vec.indexToNum.keySet())
      if (indexToNum.containsKey(index))
        ans += vec.indexToNum.get(index) * indexToNum.get(index);

    return ans;
  }

  private Map<Integer, Integer> indexToNum = new HashMap<>();
}

Approach 2: Two Pointers

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class SparseVector {
 public:
  SparseVector(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i)
      if (nums[i])
        v.push_back({i, nums[i]});
  }

  // Returns the dot product of the two sparse vectors.
  int dotProduct(SparseVector& vec) {
    int ans = 0;

    for (int i = 0, j = 0; i < v.size() && j < vec.v.size();)
      if (v[i].first == vec.v[j].first)
        ans += v[i++].second * vec.v[j++].second;
      else if (v[i].first < vec.v[j].first)
        ++i;
      else
        ++j;

    return ans;
  }

 private:
  vector<pair<int, int>> v;  //  [(index, num)]
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class T {
  public int index;
  public int num;

  public T(int index, int num) {
    this.index = index;
    this.num = num;
  }
}

class SparseVector {
  SparseVector(int[] nums) {
    for (int i = 0; i < nums.length; ++i)
      if (nums[i] != 0)
        v.add(new T(i, nums[i]));
  }

  // Returns the dot product of the two sparse vectors.
  public int dotProduct(SparseVector vec) {
    int ans = 0;

    for (int i = 0, j = 0; i < v.size() && j < vec.v.size();)
      if (v.get(i).index == vec.v.get(j).index)
        ans += v.get(i++).num * vec.v.get(j++).num;
      else if (v.get(i).index < vec.v.get(j).index)
        ++i;
      else
        ++j;

    return ans;
  }

  private List<T> v = new ArrayList<>(); // [(index, num)]
}