Teaching Kids Programming – Prefix Sum Algorithm to Find the Middle Index in Array

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hints:
Could we go from left to right and check to see if an index is a middle index?
Do we need to sum every number to the left and right of an index each time?
Use a prefix sum array where prefix[i] = nums[0] + nums[1] + … + nums[i].

Bruteforce Algorithm to Find the Middle Index of Array

We can bruteforce the index from left to right – and compute the sum of left and right part.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        s = sum(nums)
        n = len(nums)
        for i in range(n):
            l = sum(nums[:i])
            r = sum(nums[i + 1:])
            if l == r:
                return i
        return -1

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        s = sum(nums)
        n = len(nums)
        for i in range(n):
            l = sum(nums[:i])
            r = sum(nums[i + 1:])
            if l == r:
                return i
        return -1

The time complexity is O(N^2) as the sum function requires O(N) time to compute.

Prefix Sum Algorithm to Find the Middle Index of Array

We can apply the prefix sum algorithm to this problem. We need to sum all numbers in O(N) linear time using the sum function. Then we accumulate the sum of left part – and then check the rest excluding the value at middle index.

1
2
3
4
5
6
7
8
9

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        s = sum(nums)
        c = 0
        for i, x in enumerate(nums):
            if s - x - c == c:
                return i
            c += x            
        return -1

class Solution:
    def findMiddleIndex(self, nums: List[int]) -> int:
        s = sum(nums)
        c = 0
        for i, x in enumerate(nums):
            if s - x - c == c:
                return i
            c += x            
        return -1

The time complexity is improved to O(N) time and the space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —