1570. Dot Product of Two Sparse Vectors

 一刷 08/2022

Version #1 Two Pointers

Time O(N) - construction, O(N) - calculate product

Space O(N)

Runtime: 18 ms, faster than 25.58% of Java online submissions for Dot Product of Two Sparse Vectors.

Memory Usage: 122 MB, less than 27.25% of Java online submissions for Dot Product of Two Sparse Vectors.

class SparseVector {

    public List<Integer> indices;

    public List<Integer> values;

    SparseVector(int[] nums) {

        indices = new ArrayList<>();

        values = new ArrayList<>();

        for (int i = 0; i < nums.length; i++) {

            if (nums[i] == 0) {

                continue;

            }

            indices.add(i);

            values.add(nums[i]);

        }

    }

    

// Return the dotProduct of two sparse vectors

    public int dotProduct(SparseVector vec) {

        int result = 0;

        int p = 0, q = 0;

        while (p < this.indices.size() && q < vec.indices.size()) {

            if (this.indices.get(p) < vec.indices.get(q)) {

                p++;

            } else if (this.indices.get(p) > vec.indices.get(q)) {

                q++;

            } else {

                result += this.values.get(p) * vec.values.get(q);

                p++;

                q++;

            }

        }

        return result;

    }

}