Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1991.html

1991. Find the Middle Index in Array

Level

Easy

Description

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] + nums[middleIndex+2] + ... + nums[nums.length-1].

If middleIndex == 0, the left side sum is considered to be 0. Similarly, if middleIndex == nums.length - 1, the right side sum is considered to be 0.

Return the leftmost middleIndex that satisfies the condition, or -1 if there is no such index.

Example 1:

Input: nums = [2,3,-1,8,4]

Output: 3

Explanation:

The sum of the numbers before index 3 is: 2 + 3 + -1 = 4

The sum of the numbers after index 3 is: 4 = 4

Example 2:

Input: nums = [1,-1,4]

Output: 2

Explanation:

The sum of the numbers before index 2 is: 1 + -1 = 0

The sum of the numbers after index 2 is: 0

Example 3:

Input: nums = [2,5]

Output: -1

Explanation:

There is no valid middleIndex.

Example 4:

Input: nums = [1]

Output: 0

Explantion:

The sum of the numbers before index 0 is: 0

The sum of the numbers after index 0 is: 0

Constraints:

• 1 <= nums.length <= 100
• -1000 <= nums[i] <= 1000

Solution

For each element in nums, calculate the sum of elements to its left and the sum of elements to its right. Then loop over nums from left to right and return the first index such that the sum of elements to its left equals the sum of elements to its right. If such an index does not exist, return -1.

• Java
• C++
• Python
• Go
• TypeScript
• Javascript

• class Solution {
      public int findMiddleIndex(int[] nums) {
          int length = nums.length;
          int[] leftSum = new int[length];
          for (int i = 1; i < length; i++)
              leftSum[i] = leftSum[i - 1] + nums[i - 1];
          int[] rightSum = new int[length];
          for (int i = length - 2; i >= 0; i--)
              rightSum[i] = rightSum[i + 1] + nums[i + 1];
          for (int i = 0; i < length; i++) {
              if (leftSum[i] == rightSum[i])
                  return i;
          }
          return -1;
      }
  }
  
  ############
  
  class Solution {
      public int findMiddleIndex(int[] nums) {
          int left = 0, right = Arrays.stream(nums).sum();
          for (int i = 0; i < nums.length; ++i) {
              right -= nums[i];
              if (left == right) {
                  return i;
              }
              left += nums[i];
          }
          return -1;
      }
  }
  

• // OJ: https://leetcode.com/problems/find-the-middle-index-in-array/
  // Time: O(N)
  // Space: O(1)
  class Solution {
  public:
      int findMiddleIndex(vector<int>& A) {
          int right = accumulate(begin(A), end(A), 0), N = A.size(), left = 0;
          for (int i = 0; i < N; ++i) {
              if (i - 1 >= 0) left += A[i - 1];
              right -= A[i];
              if (left == right) return i;
          }
          return -1;
      }
  };
  

• class Solution:
      def findMiddleIndex(self, nums: List[int]) -> int:
          s = sum(nums)
          total = 0
          for i, num in enumerate(nums):
              total += num
              if total - num == s - total:
                  return i
          return -1
  
  ############
  
  # 1991. Find the Middle Index in Array
  # https://leetcode.com/problems/find-the-middle-index-in-array
  
  class Solution:
      def findMiddleIndex(self, nums: List[int]) -> int:
          
          for i,x in enumerate(nums):
              left = sum(nums[:i]) if i > 0 else 0
              right = sum(nums[i + 1:]) if i < len(nums) else 0
  
              if left == right:
                  return i
          
          return -1
  
  

• func findMiddleIndex(nums []int) int {
  	var left, right int
  	for _, x := range nums {
  		right += x
  	}
  	for i, x := range nums {
  		right -= x
  		if left == right {
  			return i
  		}
  		left += x
  	}
  	return -1
  }
  

• function findMiddleIndex(nums: number[]): number {
      let left = 0,
          right = nums.reduce((a, b) => a + b);
      for (let i = 0; i < nums.length; ++i) {
          right -= nums[i];
          if (left == right) {
              return i;
          }
          left += nums[i];
      }
      return -1;
  }
  
  

• /**
   * @param {number[]} nums
   * @return {number}
   */
  var findMiddleIndex = function (nums) {
      let left = 0,
          right = nums.reduce((a, b) => a + b);
      for (let i = 0; i < nums.length; ++i) {
          right -= nums[i];
          if (left == right) {
              return i;
          }
          left += nums[i];
      }
      return -1;
  };
  
  

All Problems

All Solutions