Problem

You have a large array with most of the elements as zero.

Use a more space-efficient data structure, SparseArray, that implements the same interface:

  • init(arr, size): initialize with the original large array and size.
  • set(i, val): updates index at i with val.
  • get(i): gets the value at index i.

Examples

Example 1

1
2
3
4
5
6
7
8
9

Input: arr = [0, 1, 0, 0, 2, 0, 0, 3], size = 8
Output: values at indices by calling get(i) have the same values as the original array.

Input: sparseArray.set(4, 5)
Explanation: Updates the value at index 4 to 5 in the sparse array.

Input: sparseArray.get(4)
Output: 5
Explanation: Retrieves the updated value (5) at index 4.

Solution

Method 1 - Using Hashmap

A sparse array contains mostly zero values. Storing zeros explicitly in an array would be very space inefficient. Instead, we can use a dictionary (hashmap) to store only the non-zero elements. This way, we only use space proportional to the number of non-zero elements.

Approach

  1. Initialization: init(arr, size) will take the large array and its size, and store only non-zero elements in a dictionary where the key is the index and the value is the element.
  2. Set Operation: set(i, val) will update the dictionary. If val is non-zero, it adds or updates the entry in the dictionary. If val is zero and the key exists in the dictionary, it removes the key.
  3. Get Operation: get(i) will fetch the value from the dictionary. If the key does not exist, it returns zero.

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

public class Solution {
    public static class SparseArray {
        private Map<Integer, Integer> map;
        private int size;

        public void init(int[] arr, int size) {
            this.size = size;
            this.map = new HashMap<>();
            for (int i = 0; i < size; i++) {
                if (arr[i] != 0) {
                    map.put(i, arr[i]);
                }
            }
        }
        
        public void set(int i, int val) {
            if (i >= size) {
                throw new IndexOutOfBoundsException();
            }
            if (val == 0) {
                map.remove(i);
            } else {
                map.put(i, val);
            }
        }
        
        public int get(int i) {
            if (i >= size) {
                throw new IndexOutOfBoundsException();
            }
            return map.getOrDefault(i, 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

class Solution:
    class SparseArray:
        def __init__(self):
            self.map: Dict[int, int] = {}
            self.size: int = 0
        
        def init(self, arr: List[int], size: int) -> None:
            self.size = size
            for i, val in enumerate(arr):
                if val != 0:
                    self.map[i] = val

        def set(self, i: int, val: int) -> None:
            if i >= self.size:
                raise IndexError("Index out of bounds")
            if val == 0:
                self.map.pop(i, None)
            else:
                self.map[i] = val

        def get(self, i: int) -> int:
            if i >= self.size:
                raise IndexError("Index out of bounds")
            return self.map.get(i, 0)

Complexity

  • ⏰ Time complexity: 
    • Initialization (init): O(n) where n is the size of the array.
    • Set Operation (set): O(1) for insert/update/remove operations in the dictionary.
    • Get Operation (get): O(1) for lookup in the dictionary.
  • 🧺 Space complexity: O(m), where m is the number of non-zero elements in the array.