{"id":9372,"date":"2021-12-31T16:26:32","date_gmt":"2022-01-01T00:26:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9372"},"modified":"2021-12-31T16:26:49","modified_gmt":"2022-01-01T00:26:49","slug":"leetcode-1991-find-the-middle-index-in-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-1991-find-the-middle-index-in-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1991. Find the Middle Index in Array"},"content":{"rendered":"\n

Given a 0-indexed<\/strong> integer array nums<\/code>, find the leftmost<\/strong> middleIndex<\/code> (i.e., the smallest amongst all the possible ones).<\/p>\n\n\n\n

A middleIndex<\/code> is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1]<\/code>.<\/p>\n\n\n\n

If middleIndex == 0<\/code>, the left side sum is considered to be 0<\/code>. Similarly, if middleIndex == nums.length - 1<\/code>, the right side sum is considered to be 0<\/code>.<\/p>\n\n\n\n

Return the leftmost<\/strong> <\/em>middleIndex<\/code> that satisfies the condition, or <\/em>-1<\/code> if there is no such index<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> nums = [2,3,-1,8,4]\nOutput:<\/strong> 3\nExplanation:<\/strong> The sum of the numbers before index 3 is: 2 + 3 + -1 = 4\nThe sum of the numbers after index 3 is: 4 = 4\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [1,-1,4]\nOutput:<\/strong> 2\nExplanation:<\/strong> The sum of the numbers before index 2 is: 1 + -1 = 0\nThe sum of the numbers after index 2 is: 0\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> nums = [2,5]\nOutput:<\/strong> -1\nExplanation:<\/strong> There is no valid middleIndex.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= nums.length <= 100<\/code><\/li>
  • -1000 <= nums[i] <= 1000<\/code><\/li><\/ul>\n\n\n\n
    Solution: Pre-compute + prefix sum<\/strong><\/h2>\n\n\n\n
    Pre-compute the sum of entire array. We scan the array and accumulate prefix sum and we can compute the sum of the rest of array.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int findMiddleIndex(vector& nums) {\n    int sum = accumulate(begin(nums), end(nums), 0);\n    for (int i = 0, cur = 0; i < nums.size(); ++i) {\n      if (cur == sum - cur - nums[i]) return i;\n      cur += nums[i];\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    Given a 0-indexed integer array nums, find the leftmost middleIndex (i.e., the smallest amongst all the possible ones). A middleIndex is an index where nums[0] + nums[1] + … + nums[middleIndex-1] == nums[middleIndex+1] +…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[20,222,761],"class_list":["post-9372","post","type-post","status-publish","format-standard","hentry","category-array","tag-array","tag-easy","tag-pre-compute-2","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9372","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=9372"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9372\/revisions"}],"predecessor-version":[{"id":9374,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9372\/revisions\/9374"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9372"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9372"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9372"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}