Dot Product of 2 Sparse Vectors

Problem

Given two sparse vectors X and Y, implement an algorithm to compute their dot product efficiently. In sparse vectors, most elements are zero, and only a few elements (with non-zero values) contribute to the dot product. The goal is to compute the dot product in O(m + n) time, where m and n are the numbers of non-zero elements in X and Y, respectively.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input:
X = [1, 0, 0, 4, 5]
Y = [2, 0, 0, 7, 0]

Compressed sparse vector representation:
X: indices = [0, 3, 4], values = [1, 4, 5]
Y: indices = [0, 3], values = [2, 7]

Output:
Dot Product: 2 + 28 = 30

Explanation:
Dot product is calculated as:
(1 * 2) + (4 * 7) = 2 + 28 = 30

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Input:
X = [1, 0, 3]
Y = [0, 0, 2]

Compressed sparse vector representation:
X: indices = [0, 2], values = [1, 3]
Y: indices = [2], values = [2]

Output:
Dot Product: 3 * 2 = 6

Explanation:
Dot product is calculated as:
(3 * 2) = 6
Only elements at index 2 are non-zero in both vectors.

Solution

Method 1 - Two Pointer technique

Linked List Representation:
- Implement sparse vectors using linked lists where each node contains an index and a value.
Two-Pointer Technique:
- Use two pointers to traverse both linked lists.
- Compare the indices of the current nodes from both lists.
- If the indices match, multiply the values and add to the result.
- Move the pointer with the smaller index forward.
- Continue until one or both of the pointers reach the end of the lists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


class SparseVector {
    static class Node {
        int index;
        int value;
        Node next;

        Node(int index, int value) {
            this.index = index;
            this.value = value;
            this.next = null;
        }
    }

    Node head;

    public SparseVector(int[] indices, int[] values) {
        head = new Node(-1, 0);  // Dummy node
        Node current = head;
        for (int i = 0; i < indices.length; i++) {
            current.next = new Node(indices[i], values[i]);
            current = current.next;
        }
    }

    public int dotProduct(SparseVector vec) {
        Node p1 = this.head.next;
        Node p2 = vec.head.next;
        int result = 0;

        while (p1 != null && p2 != null) {
            if (p1.index == p2.index) {
                result += p1.value * p2.value;
                p1 = p1.next;
                p2 = p2.next;
            } else if (p1.index < p2.index) {
                p1 = p1.next;
            } else {
                p2 = p2.next;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        // Example 1
        int[] indicesX1 = {0, 3, 4};
        int[] valuesX1 = {1, 4, 5};
        SparseVector X1 = new SparseVector(indicesX1, valuesX1);

        int[] indicesY1 = {0, 3};
        int[] valuesY1 = {2, 7};
        SparseVector Y1 = new SparseVector(indicesY1, valuesY1);

        System.out.println("Dot Product: " + X1.dotProduct(Y1));  // Expected output: 30

        // Example 2
        int[] indicesX2 = {0, 2};
        int[] valuesX2 = {1, 3};
        SparseVector X2 = new SparseVector(indicesX2, valuesX2);

        int[] indicesY2 = {2};
        int[] valuesY2 = {2};
        SparseVector Y2 = new SparseVector(indicesY2, valuesY2);

        System.out.println("Dot Product: " + X2.dotProduct(Y2));  // Expected output: 6

        // Example 3
        int[] indicesX3 = {1, 5};
        int[] valuesX3 = {1, 2};
        SparseVector X3 = new SparseVector(indicesX3, valuesX3);

        int[] indicesY3 = {3, 4};
        int[] valuesY3 = {3, 1};
        SparseVector Y3 = new SparseVector(indicesY3, valuesY3);

        System.out.println("Dot Product: " + X3.dotProduct(Y3));  // Expected output: 0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53


class SparseVector:
    class Node:
        def __init__(self, index, value):
            self.index = index
            self.value = value
            self.next = None

    def __init__(self, indices, values):
        self.head = self.Node(-1, 0)  # Dummy node
        current = self.head
        for index, value in zip(indices, values):
            current.next = self.Node(index, value)
            current = current.next

    def dotProduct(self, vec):
        p1 = self.head.next
        p2 = vec.head.next
        result = 0

        while p1 is not None and p2 is not None:
            if p1.index == p2.index:
                result += p1.value * p2.value
                p1 = p1.next
                p2 = p2.next
            elif p1.index < p2.index:
                p1 = p1.next
            else:
                p2 = p2.next

        return result

# Example usage
# Example 1
indicesX1 = [0, 3, 4]
valuesX1 = [1, 4, 5]
X1 = SparseVector(indicesX1, valuesX1)

indicesY1 = [0, 3]
valuesY1 = [2, 7]
Y1 = SparseVector(indicesY1, valuesY1)

print("Dot Product:", X1.dotProduct(Y1))  # Expected output: 30

# Example 2
indicesX2 = [0, 2]
valuesX2 = [1, 3]
X2 = SparseVector(indicesX2, valuesX2)

indicesY2 = [2]
valuesY2 = [2]
Y2 = SparseVector(indicesY2, valuesY2)

print("Dot Product:", X2.dotProduct(Y2))  # Expected output: 6

Complexity

⏰ Time complexity: O(m + n), where m and n are the numbers of non-zero elements in vectors X and Y, respectively.
🧺 Space complexity: O(1) for the algorithm itself, ignoring space used to store the input

Problem#

Examples#

Solution#

Method 1 - Two Pointer technique#

Code#

Complexity#