algorithms

commit 37fef6b06c8afe4e5f0d70bddd85942fe338f883
parent c86c8cdf1619b2e553effcc8de0d0af504772038
Author: Andrew Laack <andrew@laack.co>
Date:   Wed,  2 Sep 2026 13:35:19 -0500

Prefix sum start

Diffstat:
A
product-of-array-except-self/product-of-array-except-self.cpp
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
A
range-sum-query-immutable/range-sum-query-immutable.cpp
 | 
18
++++++++++++++++++

2 files changed, 61 insertions(+), 0 deletions(-)
diff --git a/product-of-array-except-self/product-of-array-except-self.cpp b/product-of-array-except-self/product-of-array-except-self.cpp
@@ -0,0 +1,43 @@
+class Solution {
+public:
+    vector<int> productExceptSelf(vector<int>& nums) {
+        
+        vector<int> prefix_product (nums.size());
+        vector<int> suffix_product (nums.size());
+
+        int prefix_prd = 1;
+        int suffix_prd = 1;
+
+        for(size_t i = 0; i < nums.size(); ++i) {
+            
+            prefix_product[i] = prefix_prd;
+
+            int inv = (nums.size() - 1) - i;
+            suffix_product[inv] = suffix_prd;
+
+            if (i < nums.size()) {
+                prefix_prd *= nums[i];
+            }
+
+            if (inv >= 0 && inv < nums.size()) {
+                suffix_prd *= nums[inv];
+            }
+
+
+        }
+
+        vector<int> results (nums.size());
+        for(size_t i = 0; i < nums.size(); ++i) {
+            int res = 1;
+            if(i > 0) {
+                res *= prefix_product[i];
+            }
+            if(i + 1 < nums.size()) {
+                res *= suffix_product[i];
+            }
+
+            results[i] = res;
+        }
+        return results;
+    }
+};
diff --git a/range-sum-query-immutable/range-sum-query-immutable.cpp b/range-sum-query-immutable/range-sum-query-immutable.cpp
@@ -0,0 +1,18 @@
+class NumArray {
+public:
+    unordered_map<int, int> map {};
+    NumArray(vector<int>& nums) {
+        // init with nums list
+        int prefix = 0;
+        for(size_t i = 0; i < nums.size(); ++i) {
+            map[i] = prefix;
+            prefix += nums[i]; 
+        }
+        map[nums.size()] = prefix;
+    }
+    
+    int sumRange(int left, int right) {
+        // query: return sum[left:right]
+        return map[right + 1] - map[left];
+    }
+};