{"action":"created","comment":{"url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/comments/59659146","id":59659146,"diff_hunk":"@@ -0,0 +1,62 @@\n+import java.util.List;\n+\n+/**\n+ * 120. Triangle\n+ * Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.\n+ * For example, given the following triangle\n+ * [\n+ *    [2],\n+ *   [3,4],\n+ *  [6,5,7],\n+ * [4,1,8,3]\n+ * ]\n+ * The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).\n+ * Note:\n+ * Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.\n+ * Tags: Array Dynamic Programming\n+ * Analysis: DP\n+ * @author chenshuna\n+ */ \n+\n+public class Triangle {\n+    public static int minimumTotal(List<List<Integer>> triangle) {\n+        int minSum = Integer.MAX_VALUE;\n+        int[] sum = new int[triangle.size()];\n+        sum[0] = triangle.get(0).get(0);\n+        for(int i = 1; i < triangle.size(); i++){  // from top to bottom\n+            List<Integer> line = triangle.get(i);\n+            for(int j = i; j >= 0; j--){\n+                if(j == 0){\n+                    sum[j] += line.get(j);\n+                }\n+                else if(j == i){\n+                    sum[j] = sum[j - 1] + line.get(j);\n+                }\n+                else{\n+                    sum[j] = Math.min(sum[j], sum[j - 1]) + line.get(j);\n+                }\n+            }\n+        }\n+        for(int cnt : sum){","path":"Medium/Triangle_shuna.java","position":40,"original_position":40,"commit_id":"1ccb715218f2b887eebbca0b73c2d803b87bd59b","original_commit_id":"1ccb715218f2b887eebbca0b73c2d803b87bd59b","user":{"login":"kuangami","id":17601918,"avatar_url":"https://avatars.githubusercontent.com/u/17601918?v=3","gravatar_id":"","url":"https://api.github.com/users/kuangami","html_url":"https://github.com/kuangami","followers_url":"https://api.github.com/users/kuangami/followers","following_url":"https://api.github.com/users/kuangami/following{/other_user}","gists_url":"https://api.github.com/users/kuangami/gists{/gist_id}","starred_url":"https://api.github.com/users/kuangami/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/kuangami/subscriptions","organizations_url":"https://api.github.com/users/kuangami/orgs","repos_url":"https://api.github.com/users/kuangami/repos","events_url":"https://api.github.com/users/kuangami/events{/privacy}","received_events_url":"https://api.github.com/users/kuangami/received_events","type":"User","site_admin":false},"body":"In this for-loop, you need to have extra space for each row at line 27, plus you need another for-loop to find the minimum at line 40.\r\n\r\nIt could be much easier if you try from bottom to top, you can initialize the `sum` array with the last row elements, adding all the way up to the top, finally you will find the minimum at sum[0].","created_at":"2016-04-14T03:27:31Z","updated_at":"2016-04-14T03:27:31Z","html_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res/pull/129#discussion_r59659146","pull_request_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129","_links":{"self":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/comments/59659146"},"html":{"href":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res/pull/129#discussion_r59659146"},"pull_request":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129"}}},"pull_request":{"url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129","id":66418631,"html_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res/pull/129","diff_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res/pull/129.diff","patch_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res/pull/129.patch","issue_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues/129","number":129,"state":"open","locked":false,"title":"finished 120","user":{"login":"JoannaCode","id":11778819,"avatar_url":"https://avatars.githubusercontent.com/u/11778819?v=3","gravatar_id":"","url":"https://api.github.com/users/JoannaCode","html_url":"https://github.com/JoannaCode","followers_url":"https://api.github.com/users/JoannaCode/followers","following_url":"https://api.github.com/users/JoannaCode/following{/other_user}","gists_url":"https://api.github.com/users/JoannaCode/gists{/gist_id}","starred_url":"https://api.github.com/users/JoannaCode/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoannaCode/subscriptions","organizations_url":"https://api.github.com/users/JoannaCode/orgs","repos_url":"https://api.github.com/users/JoannaCode/repos","events_url":"https://api.github.com/users/JoannaCode/events{/privacy}","received_events_url":"https://api.github.com/users/JoannaCode/received_events","type":"User","site_admin":false},"body":"@kuangami ","created_at":"2016-04-14T01:57:12Z","updated_at":"2016-04-14T03:27:31Z","closed_at":null,"merged_at":null,"merge_commit_sha":"88f05512ee33ecf0bb3b4a44e040bc30edf8fe4d","assignee":null,"milestone":null,"commits_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129/commits","review_comments_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129/comments","review_comment_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/comments{/number}","comments_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues/129/comments","statuses_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/statuses/1ccb715218f2b887eebbca0b73c2d803b87bd59b","head":{"label":"JoannaCode:shuna120","ref":"shuna120","sha":"1ccb715218f2b887eebbca0b73c2d803b87bd59b","user":{"login":"JoannaCode","id":11778819,"avatar_url":"https://avatars.githubusercontent.com/u/11778819?v=3","gravatar_id":"","url":"https://api.github.com/users/JoannaCode","html_url":"https://github.com/JoannaCode","followers_url":"https://api.github.com/users/JoannaCode/followers","following_url":"https://api.github.com/users/JoannaCode/following{/other_user}","gists_url":"https://api.github.com/users/JoannaCode/gists{/gist_id}","starred_url":"https://api.github.com/users/JoannaCode/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoannaCode/subscriptions","organizations_url":"https://api.github.com/users/JoannaCode/orgs","repos_url":"https://api.github.com/users/JoannaCode/repos","events_url":"https://api.github.com/users/JoannaCode/events{/privacy}","received_events_url":"https://api.github.com/users/JoannaCode/received_events","type":"User","site_admin":false},"repo":{"id":53106941,"name":"LeetCode-Sol-Res","full_name":"JoannaCode/LeetCode-Sol-Res","owner":{"login":"JoannaCode","id":11778819,"avatar_url":"https://avatars.githubusercontent.com/u/11778819?v=3","gravatar_id":"","url":"https://api.github.com/users/JoannaCode","html_url":"https://github.com/JoannaCode","followers_url":"https://api.github.com/users/JoannaCode/followers","following_url":"https://api.github.com/users/JoannaCode/following{/other_user}","gists_url":"https://api.github.com/users/JoannaCode/gists{/gist_id}","starred_url":"https://api.github.com/users/JoannaCode/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/JoannaCode/subscriptions","organizations_url":"https://api.github.com/users/JoannaCode/orgs","repos_url":"https://api.github.com/users/JoannaCode/repos","events_url":"https://api.github.com/users/JoannaCode/events{/privacy}","received_events_url":"https://api.github.com/users/JoannaCode/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/JoannaCode/LeetCode-Sol-Res","description":"Clean, Understandable Solutions and Resources for LeetCode Online Judge Algorithms Problems. ","fork":true,"url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res","forks_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/forks","keys_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/keys{/key_id}","collaborators_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/teams","hooks_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/hooks","issue_events_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/issues/events{/number}","events_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/events","assignees_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/assignees{/user}","branches_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/branches{/branch}","tags_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/tags","blobs_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/git/refs{/sha}","trees_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/git/trees{/sha}","statuses_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/statuses/{sha}","languages_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/languages","stargazers_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/stargazers","contributors_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/contributors","subscribers_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/subscribers","subscription_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/subscription","commits_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/commits{/sha}","git_commits_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/git/commits{/sha}","comments_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/comments{/number}","issue_comment_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/issues/comments{/number}","contents_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/contents/{+path}","compare_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/compare/{base}...{head}","merges_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/merges","archive_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/downloads","issues_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/issues{/number}","pulls_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/pulls{/number}","milestones_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/milestones{/number}","notifications_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/labels{/name}","releases_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/releases{/id}","deployments_url":"https://api.github.com/repos/JoannaCode/LeetCode-Sol-Res/deployments","created_at":"2016-03-04T04:17:54Z","updated_at":"2016-03-04T04:17:55Z","pushed_at":"2016-04-14T01:56:20Z","git_url":"git://github.com/JoannaCode/LeetCode-Sol-Res.git","ssh_url":"git@github.com:JoannaCode/LeetCode-Sol-Res.git","clone_url":"https://github.com/JoannaCode/LeetCode-Sol-Res.git","svn_url":"https://github.com/JoannaCode/LeetCode-Sol-Res","homepage":"","size":4089,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"FreeTymeKiyan:master","ref":"master","sha":"fae9a2fb44f1062e53da089c367434fee3b69716","user":{"login":"FreeTymeKiyan","id":1934618,"avatar_url":"https://avatars.githubusercontent.com/u/1934618?v=3","gravatar_id":"","url":"https://api.github.com/users/FreeTymeKiyan","html_url":"https://github.com/FreeTymeKiyan","followers_url":"https://api.github.com/users/FreeTymeKiyan/followers","following_url":"https://api.github.com/users/FreeTymeKiyan/following{/other_user}","gists_url":"https://api.github.com/users/FreeTymeKiyan/gists{/gist_id}","starred_url":"https://api.github.com/users/FreeTymeKiyan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/FreeTymeKiyan/subscriptions","organizations_url":"https://api.github.com/users/FreeTymeKiyan/orgs","repos_url":"https://api.github.com/users/FreeTymeKiyan/repos","events_url":"https://api.github.com/users/FreeTymeKiyan/events{/privacy}","received_events_url":"https://api.github.com/users/FreeTymeKiyan/received_events","type":"User","site_admin":false},"repo":{"id":29097862,"name":"LeetCode-Sol-Res","full_name":"FreeTymeKiyan/LeetCode-Sol-Res","owner":{"login":"FreeTymeKiyan","id":1934618,"avatar_url":"https://avatars.githubusercontent.com/u/1934618?v=3","gravatar_id":"","url":"https://api.github.com/users/FreeTymeKiyan","html_url":"https://github.com/FreeTymeKiyan","followers_url":"https://api.github.com/users/FreeTymeKiyan/followers","following_url":"https://api.github.com/users/FreeTymeKiyan/following{/other_user}","gists_url":"https://api.github.com/users/FreeTymeKiyan/gists{/gist_id}","starred_url":"https://api.github.com/users/FreeTymeKiyan/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/FreeTymeKiyan/subscriptions","organizations_url":"https://api.github.com/users/FreeTymeKiyan/orgs","repos_url":"https://api.github.com/users/FreeTymeKiyan/repos","events_url":"https://api.github.com/users/FreeTymeKiyan/events{/privacy}","received_events_url":"https://api.github.com/users/FreeTymeKiyan/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res","description":"Clean, Understandable Solutions and Resources for LeetCode Online Judge Algorithms Problems. ","fork":false,"url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res","forks_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/forks","keys_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/keys{/key_id}","collaborators_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/teams","hooks_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/hooks","issue_events_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues/events{/number}","events_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/events","assignees_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/assignees{/user}","branches_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/branches{/branch}","tags_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/tags","blobs_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/git/refs{/sha}","trees_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/git/trees{/sha}","statuses_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/statuses/{sha}","languages_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/languages","stargazers_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/stargazers","contributors_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/contributors","subscribers_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/subscribers","subscription_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/subscription","commits_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/commits{/sha}","git_commits_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/git/commits{/sha}","comments_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/comments{/number}","issue_comment_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues/comments{/number}","contents_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/contents/{+path}","compare_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/compare/{base}...{head}","merges_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/merges","archive_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/downloads","issues_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues{/number}","pulls_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls{/number}","milestones_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/milestones{/number}","notifications_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/labels{/name}","releases_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/releases{/id}","deployments_url":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/deployments","created_at":"2015-01-11T16:29:55Z","updated_at":"2016-04-12T07:45:07Z","pushed_at":"2016-04-14T01:57:13Z","git_url":"git://github.com/FreeTymeKiyan/LeetCode-Sol-Res.git","ssh_url":"git@github.com:FreeTymeKiyan/LeetCode-Sol-Res.git","clone_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res.git","svn_url":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res","homepage":"","size":4176,"stargazers_count":493,"watchers_count":493,"language":"Java","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":374,"mirror_url":null,"open_issues_count":15,"forks":374,"open_issues":15,"watchers":493,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129"},"html":{"href":"https://github.com/FreeTymeKiyan/LeetCode-Sol-Res/pull/129"},"issue":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues/129"},"comments":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/issues/129/comments"},"review_comments":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129/comments"},"review_comment":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/pulls/129/commits"},"statuses":{"href":"https://api.github.com/repos/FreeTymeKiyan/LeetCode-Sol-Res/statuses/1ccb715218f2b887eebbca0b73c2d803b87bd59b"}}}}