Skip to main content
Talentd

Dot Product of Two Sparse Vectors - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableTwo PointersDesign9 min readAsked at: Amazon, Microsoft, Apple +9
Practice this problem

Problem Statement

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

  • SparseVector(nums) Initializes the object with the vector nums
  • dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

 

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

 

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 100

Approach Overview

Problem Overview: You receive two vectors that mostly contain zeros. Instead of storing every element, you design a sparse vector structure and implement a function that returns the dot product between two such vectors.

Approach 1: Direct Array Iteration (O(n) time, O(1) space)

The straightforward solution iterates through both vectors and multiplies values at the same index. Maintain a running sum: result += nums1[i] * nums2[i]. This works because the dot product is defined as the sum of element‑wise products. The drawback is wasted work when most values are zero. You still process every index even if the product contributes nothing. This approach is acceptable when vectors are dense or when the input is already stored as full arrays.

Approach 2: Hash Map Sparse Representation (O(k1 + k2) time, O(k1 + k2) space)

A sparse vector only needs to store non‑zero values. During initialization, iterate through the array and insert (index → value) pairs into a hash table whenever the value is not zero. If the vector contains k non‑zero elements, the storage shrinks from O(n) to O(k).

To compute the dot product, iterate through the smaller map and check whether the same index exists in the other map. Each lookup is O(1) on average. If both vectors contain a non‑zero value at index i, multiply them and add to the result. Zero entries never appear in the map, so they are skipped automatically.

This design drastically reduces work when the vectors are sparse. Instead of scanning the entire array length n, you only process indices that matter. The runtime becomes proportional to the number of stored elements rather than the vector size.

Some implementations also keep non‑zero entries sorted and use a two pointers technique to traverse both lists simultaneously. Both methods rely on the same core idea: ignore zero values and operate only on meaningful entries.

Recommended for interviews: The sparse hash map design is what interviewers expect. Start by explaining the naive array scan to show understanding of the dot product definition. Then optimize by storing only non‑zero values. This demonstrates awareness of sparse data structures, practical memory optimization, and efficient lookup using a hash table.

Solution

We use a hash map d to store non-zero elements, where the key is the index, and the value is the corresponding value. We iterate through nums, and if nums[i] is not 0, we add (i, nums[i]) to the hash map d.

When calculating the dot product, we iterate through the hash map with fewer non-zero elements and check if the other hash map contains the corresponding key. If it exists, we multiply the corresponding values and add them to the result.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Array IterationO(n)O(1)Vectors are dense or already stored as full arrays
Hash Map Sparse RepresentationO(k1 + k2)O(k1 + k2)Vectors contain many zeros; only non‑zero elements are stored
Sorted Non‑Zero Lists + Two PointersO(k1 + k2)O(k1 + k2)Non‑zero entries are stored as sorted pairs and traversed simultaneously

Video Solution

DOT PRODUCT OF TWO SPARSE VECTORS - 3 SOLUTIONS EXPLAINED [PYTHON] • Cracking FAANG • 16,922 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Dot Product of Two Sparse Vectors easy or hard?
Dot Product of Two Sparse Vectors is classified as a Medium problem. The core math operation is simple, but the challenge is designing an efficient sparse representation that avoids iterating through many zero values.
Dot Product of Two Sparse Vectors Python/Java solution
The typical implementation creates a SparseVector class that stores non-zero entries in a dictionary (Python) or HashMap (Java). During the dotProduct operation, iterate through one map and multiply values when the same index exists in the other map. This keeps the complexity proportional to the number of stored elements.
How to solve Dot Product of Two Sparse Vectors in O(n)?
Store non-zero elements in a hash table keyed by index. While computing the dot product, iterate through one map and check if the same index exists in the other map. Each lookup is O(1) on average, so the total work is proportional to the number of stored elements rather than the full vector length.
What is the best approach for Dot Product of Two Sparse Vectors?
The optimal approach stores only non-zero values using a hash map or sparse representation. Each vector keeps (index, value) pairs for non-zero elements, then multiplies values when both vectors share the same index. This avoids scanning zeros and reduces the runtime to O(k1 + k2), where k1 and k2 are the number of non-zero entries.
Is Dot Product of Two Sparse Vectors asked at Google/Amazon/Meta?
Sparse vector and sparse matrix operations appear in interviews at companies working with large-scale data or machine learning systems. Variants of this problem have been reported in interviews at companies like Meta and Google because they test data structure design and efficiency with sparse datasets.
What data structure is used in Dot Product of Two Sparse Vectors?
A hash table is commonly used to store non-zero entries as (index → value) pairs. This allows constant-time lookup when checking whether both vectors share the same index. Some implementations also store pairs in sorted lists and apply a two-pointer traversal.
What is the time complexity of Dot Product of Two Sparse Vectors?
The optimal sparse solution runs in O(k1 + k2) time where k1 and k2 represent the number of non-zero elements in each vector. Building the sparse representation also takes O(k). A naive dense array iteration would take O(n) time regardless of sparsity.

Ready to solve this problem?

Practice Dot Product of Two Sparse Vectors with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays