_1570. Dot Product of Two Sparse Vectors.md

1570. Dot Product of Two Sparse Vectors

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : June 06, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Hash Table, Two Pointers, Design

Acceptance Rate : 89.88 %

---

Solutions

• m1570 v2 efficient storing.py
• m1570 v2-2 improved further and simplified.py
• m1570.py
• m1570 v2-2.java
• m1570 v2.c

Python

m1570 v2 efficient storing.py

# Notably more efficient amortized & better space efficiency if highly sparse
# THIS IN EFFECT IS SIMILAR TO THE INDEX-PAIRS METHOD

class SparseVector:
    def __init__(self, nums: List[int]):
        self.nums = {}
        for i in range(len(nums)) :
            if nums[i] :
                self.nums[i] = nums[i]

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        output = 0
        
        selfIndicies = sorted(self.nums.keys())
        vecIndicies = sorted(vec.nums.keys())

        while selfIndicies and vecIndicies :
            if selfIndicies[-1] > vecIndicies[-1] :
                selfIndicies.pop()
            elif selfIndicies[-1] < vecIndicies[-1] :
                vecIndicies.pop()
            else :
                output += vec.nums[vecIndicies.pop()] * self.nums[selfIndicies.pop()]
        return output

# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

m1570 v2-2 improved further and simplified.py

# Similar to the previous v2 version but optimized after recognizing the lack of need for
# two independent sets

class SparseVector:
    def __init__(self, nums: List[int]):
        self.nums = {}
        for i in range(len(nums)) :
            if nums[i] :
                self.nums[i] = nums[i]

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        output = 0
        
        for i in self.nums.keys() :
            if i in vec.nums.keys() :
                output += vec.nums[i] * self.nums[i]
                
        return output

# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

m1570.py

class SparseVector:
    def __init__(self, nums: List[int]):
        self.nums = nums

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        output = 0
        for i in range(len(self.nums)) :
            output += self.nums[i] * vec.nums[i]

        return output

# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

Java

m1570 v2-2.java

class SparseVector {
    
    private HashMap<Integer, Integer> vals = new HashMap<>();
    SparseVector(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                vals.put(i, nums[i]);
            }
        }
    }
    
	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int output = 0;
        for (Integer i : vals.keySet()) {
            if (vec.vals.containsKey(i)) {
                output += vec.vals.get(i) * vals.get(i);
            }
        }
        return output;
    }
}

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1 = new SparseVector(nums1);
// SparseVector v2 = new SparseVector(nums2);
// int ans = v1.dotProduct(v2);

C

m1570 v2.c

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


SparseVector* sparseVectorCreate(int* nums, int numsSize) {
    
    // number of values to store
    int newNumSize = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i]) {
            newNumSize++;
        }
    }

    // storing the values
    SparseVector* data = malloc(sizeof(SparseVector));
    data->nums = (int*) malloc(sizeof(int) * newNumSize * 2);
    data->numsSize = newNumSize;
    
    for (int i = 0, currPointer = 0; i < numsSize; i++) {
        if (nums[i]) {
            data->nums[currPointer] = i;
            data->nums[currPointer + 1] = nums[i];
            currPointer += 2;
        }
    }

    return data;
}

// Return the dotProduct of two sparse vectors
int sparseVectordotProduct(SparseVector* obj, SparseVector* vec) {
    int output = 0;
    for (int i = 0, j = 0; i < 2 * obj->numsSize && j < 2 * vec->numsSize;) {
        if (obj->nums[i] < vec->nums[j]) {
            i += 2;
        } else if (obj->nums[i] > vec->nums[j]) {
            j += 2;
        } else {
            output += obj->nums[i + 1] * vec->nums[j + 1];
            i += 2;
            j += 2;
        }
    }

    return output;
}

/**
 * Your SparseVector struct will be instantiated and called as such:
 * SparseVector* v1 = sparseVectorCreate(nums1, nums1Size);
 * SparseVector* v2 = sparseVectorCreate(nums2, nums2Size);
 * int ans = sparseVectordotProduct(v1, v2);
*/