Dot Product of Two Sparse Vectors - Practice Coding Problems

Dot Product of Two Sparse Vectors - Problem

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?

Input & Output

Example 1 — Basic Case

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

› Output: 8

💡 Note: Dot product = 1×0 + 0×3 + 0×0 + 2×4 + 3×0 = 0 + 0 + 0 + 8 + 0 = 8

Example 2 — All Zeros

$ Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]

› Output: 0

💡 Note: No overlapping non-zero elements: 0×0 + 1×0 + 0×0 + 0×0 + 0×2 = 0

Example 3 — Same Position Non-Zero

$ Input: nums1 = [0,1,0,0,2,0], nums2 = [1,0,0,0,3,0]

› Output: 6

💡 Note: Only position 4 has non-zero in both: 0×1 + 1×0 + 0×0 + 0×0 + 2×3 + 0×0 = 6

Constraints

n == nums1.length == nums2.length
1 ≤ n ≤ 10⁵
0 ≤ nums1[i], nums2[i] ≤ 100

Visualization

Tap to expand

Understanding the Visualization

Input Sparse Vectors

Two vectors with mostly zero values

Store Non-Zero Only

Extract and store only non-zero elements with indices

Compute Dot Product

Find overlapping indices and multiply corresponding values

Key Takeaway

🎯 Key Insight: Store only non-zero elements to skip unnecessary multiplications by zero and save memory

Asked in

f Facebook 15 a Amazon 8 G Google 6

The key insight is to store only non-zero elements to optimize space and computation for sparse vectors. Best approach uses hash map to store {index: value} pairs and iterate through the smaller map for intersection. Time: O(min(a,b)), Space: O(a+b) where a,b are non-zero counts.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Store All Elements	O(n)	O(n)	Store entire vector and iterate through all positions for dot product
Hash Map - Store Non-Zero Elements	O(min(a, b))	O(a + b)	Store only non-zero elements with their indices in a hash map
Two Pointers - Sorted Index Arrays	O(a + b)	O(a + b)	Store non-zero elements in sorted arrays and use two pointers for intersection

Brute Force - Store All Elements — Algorithm Steps

Store the entire input vector as-is
For dot product, iterate through all positions
Multiply nums1[i] * nums2[i] for each i
Sum all products to get final result

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Complete Vectors

Store all elements including zeros

Multiply All Positions

Calculate nums1[i] * nums2[i] for every i

Sum Results

Add all products to get dot product

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int* nums;
    int size;
} SparseVector;

SparseVector* sparseVectorCreate(int* nums, int size) {
    SparseVector* sv = (SparseVector*)malloc(sizeof(SparseVector));
    sv->nums = (int*)malloc(size * sizeof(int));
    sv->size = size;
    for (int i = 0; i < size; i++) {
        sv->nums[i] = nums[i];
    }
    return sv;
}

int sparseVectorDotProduct(SparseVector* sv1, SparseVector* sv2) {
    int result = 0;
    for (int i = 0; i < sv1->size; i++) {
        result += sv1->nums[i] * sv2->nums[i];
    }
    return result;
}

int solution(int* nums1, int size1, int* nums2, int size2) {
    SparseVector* vec1 = sparseVectorCreate(nums1, size1);
    SparseVector* vec2 = sparseVectorCreate(nums2, size2);
    int result = sparseVectorDotProduct(vec1, vec2);
    free(vec1->nums);
    free(vec1);
    free(vec2->nums);
    free(vec2);
    return result;
}

int main() {
    char line[1000];
    int nums1[100], nums2[100];
    int size1 = 0, size2 = 0;
    
    // Parse first array
    fgets(line, sizeof(line), stdin);
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums1[size1++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    // Parse second array
    fgets(line, sizeof(line), stdin);
    token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] >= '0' && token[0] <= '9') {
            nums2[size2++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums1, size1, nums2, size2));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through all n elements for dot product calculation

✓ Linear Growth

Space Complexity

O(n)

Stores entire vector of length n including zero elements

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Store All Elements — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler