range addition

fishercoder1534 · fishercoder1534 · commit 5fda0be42536 · 2016-11-23T15:25:38.000-08:00
diff --git a/MEDIUM/src/medium/RangeAddition.java b/MEDIUM/src/medium/RangeAddition.java
@@ -0,0 +1,53 @@
+package medium;
+
+public class RangeAddition {
+    /**Previously AC'ed brute force solution results in TLE now.*/
+    public static int[] getModifiedArray_TLE(int length, int[][] updates) {
+        int[] nums = new int[length];
+        int k = updates.length;
+        for(int i = 0; i < k; i++){
+            int start = updates[i][0];
+            int end = updates[i][1];
+            int inc = updates[i][2];
+            for(int j = start; j <= end; j++){
+                nums[j] += inc;
+            }
+        }
+        return nums;
+    }
+    
+    /**Looked at this post: https://discuss.leetcode.com/topic/49691/java-o-k-n-time-complexity-solution and one OJ official article: https://leetcode.com/articles/range-addition/*/
+    public static int[] getModifiedArray(int length, int[][] updates) {
+        int[] nums = new int[length];
+        int k = updates.length;
+        for (int i = 0; i < k; i++){
+            int start = updates[i][0];
+            int end = updates[i][1];
+            int inc = updates[i][2];
+            nums[start] += inc;
+            if (end < length-1) nums[end+1] -= inc;
+        }
+        
+        int sum = 0;
+        for (int i = 0; i < length; i++){
+            sum += nums[i];
+            nums[i] = sum;
+        }
+        return nums;
+    }
+    
+    public static void main(String...args){
+    /**5
+    [[1,3,2],[2,4,3],[0,2,-2]]*/
+        int length = 5;
+        int[][] updates = new int[][]{
+                {1,3,2},
+                {2,4,3},
+                {0,2,-2},
+        };
+        int[] result = getModifiedArray(length, updates);
+        for (int i : result) {
+            System.out.print(i + "\t");
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -31,6 +31,7 @@
 |386|[Lexicographical Numbers](https://leetcode.com/problems/lexicographical-numbers/)|[Solution](../../blob/master/MEDIUM/src/medium/LexicographicalNumbers.java)| O(n)|O(1) | Medium| 
 |379|[Design Phone Directory](https://leetcode.com/problems/design-phone-directory/)|[Solution](../../blob/master/MEDIUM/src/medium/DesignPhoneDirectory.java)| O(1)|O(n) | Medium| 
 |374|[Guess Number Higher or Lower](https://leetcode.com/problems/guess-number-higher-or-lower/)|[Solution](../../blob/master/EASY/src/easy/GuessNumberHigherorLower.java)| O(logn)|O(1) | Easy| Binary Search
+|370|[Range Addition](https://leetcode.com/problems/range-addition/)|[Solution](../../blob/master/MEDIUM/src/medium/RangeAddition.java)| O(n+k)|O(1) | Medium| 
 |350|[Intersection of Two Arrays II](https://leetcode.com/problems/intersection-of-two-arrays-ii/)|[Solution](../../blob/master/EASY/src/easy/IntersectionOfTwoArraysII.java)| O(m+n)|O((m+n)) could be optimized | Easy| HashMap, Binary Search
 |349|[Intersection of Two Arrays](https://leetcode.com/problems/intersection-of-two-arrays/)|[Solution](../../blob/master/EASY/src/easy/IntersectionOfTwoArrays.java)| O(m+n)|O(min(m,n)) | Easy| Two Pointers, Binary Search
 |339|[Nested List Weight Sum](https://leetcode.com/problems/nested-list-weight-sum/)|[Solution](../../blob/master/EASY/src/easy/NestedListWeightSum.java)| O(n)|O(h)) | Easy| DFS
