Dot product of Sparse matrix

1570.Dot Product of Two Sparse Vectors

Array

Two Pointers

Design

Java Solution:

// There are a couple solutions to this one
// 1. Store entire erray solution
// 2. Hashmap solution - not accepted by Meta interviewers because hash is high computation apparently
//    And also Hashmap reallocates array at 75 percent capacity so not the most sparse solution
// 3. Add all pairs and use 2 pointer solution
// 4. Follow up only one vector is sparse -> use binary search..
class SparseVector {

    List<int[]> pairs;

    SparseVector(int[] nums) {
        pairs = new ArrayList<>();

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

    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int result = 0, i = 0, j = 0;

        while (i < pairs.size() && j < vec.pairs.size()) {
            if (pairs.get(i)[0] == vec.pairs.get(j)[0]) {
                result += pairs.get(i)[1] * vec.pairs.get(j)[1];
                i++;
                j++;
            }
            else if (pairs.get(i)[0] > vec.pairs.get(j)[0]) 
                j++;
            else 
                i++;
        }
        return result;
    }
}

Python Solution:

class SparseVector:
    def __init__(self, nums: List[int]):
        self.pairs = []  
        for i, num in enumerate(nums):
            if num != 0:
                self.pairs.append([i, num])
        
    def dotProduct(self, vec: 'SparseVector') -> int:
        result = 0
        i = j = 0
        
        while i < len(self.pairs) and j < len(vec.pairs):
            if self.pairs[i][0] == vec.pairs[j][0]:
                result += self.pairs[i][1] * vec.pairs[j][1]
                i += 1
                j += 1
            elif self.pairs[i][0] > vec.pairs[j][0]:
                j += 1
            else:
                i += 1
                
        return result

C++ Solution:

class SparseVector {
private:
    vectorint, int>> pairs;
    
public:
    SparseVector(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] != 0) {
                pairs.push_back({i, nums[i]});
            }
        }
    }
    
    int dotProduct(SparseVector& vec) {
        int result = 0;
        int i = 0, j = 0;
        
        while(i < pairs.size() && j < vec.pairs.size()) {
            if(pairs[i].first == vec.pairs[j].first) {
                result += pairs[i].second * vec.pairs[j].second;
                i++;
                j++;
            }
            else if(pairs[i].first > vec.pairs[j].first) {
                j++;
            }
            else {
                i++;
            }
        }
        
        return result;
    }
};