1991. Find the Middle Index in Array - LeetCode Fastest Solution

Hello Code Recipian! In our previous article we introduced the prefix sum pattern, and as promised, we are back with a solution to problem 1991. Find the Middle Index in Array which uses this pattern.

This problem is a direct application of the prefix sum coding pattern discussed in our previous article. If you haven't read it yet, we highly recommend checking it out before continuing with this one.

Okay—with that said let's dive into the problem statement!

Problem Statement: 1991. Find the Middle Index in Array

Given an integer array nums, find the middle index in nums array, middleIndex. Note that you must find the leftmost middle index in nums array.

A middleIndex is an index where nums[0] + nums[1] + ... + nums[middleIndex-1] == nums[middleIndex+1] + nums[middleIndex+2] + ... + nums[nums.length-1].

For the first element in nums, the left sum is considered 0, and for the last element, the right sum is considered 0.

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

Example 1

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

Output: 3 Justification: The sum of the numbers to the left of index 3 is (2 + 3 + -1 = 4) and the sum of the numbers to the right of index 3 is also 4.

Example 2

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

Output: 0

Justification: The sum of the numbers to the left of index 0 is 0. The sum of the numbers to the right of index 0 (1 + -1 = 0) is also 0.

Constraints

• 1 <= nums.length <= 100

• -1000 <= nums[i] <= 1000

Solution

To solve this problem, we need to calculate the sum of elements on both sides of each element in nums array. A straight forward way to solve this problem is to use nested loops, but that would result in suboptimal time complexity. Instead, we will use the prefix sum technique, which ensures efficiency in both time and space. Let's see how this works.

Algorithm

Below is a step-by-step explanation for the working of the algorithm:

1. Calculate total sum:

   1. Create an integer variable totalSum and initialize it to 0.

   2. Iterate through all elements in nums array and calculate the total sum. Let's store this in totalSum.

   3. totalSum will be used in our next step to efficiently calculate the right sum.

2. Find middle index:

   In this step we calculate left sum and right sum and check if they are equal. Left sum is calculated in each iteration as we traverse through the array, right sum is calculated using mathematical formula:

   1. Create an integer variable leftSum and initialize it to 0.

   2. Since we have the total sum from previous step, we can calculate the right sum using the formula: rightSum = totalSum - leftSum - current number

      

   3. Once we have the right sum, compare it with the current left sum and check if they are equal.

      1. If leftSum == rightSum, we have found the middle element, immediately return the current index as result.

      2. If leftSum != rightSum, update leftSum by adding the current number to it and continue iterating.

3. Middle index not found:

   If the execution comes out of the 2nd loop without returning, it means the given nums array does not contain a middle index. Therefore return -1 as result.

Want to master coding? Looking to upskill and crack interviews? We suggest you check out these specially designed courses:

1. Artificial Intelligence A-Z 2025: Build 7 AI + LLM & ChatGPT

2. Udemy Video Tutorials - Available at 95% off

3. System Design Interview Complete Guide

4. Data Structures And Algorithms - A Complete Guide 

5. Learn In-Demand Tech Skills And Stay Ahead Of Others

Simulation

Below is a pictorial depiction for the working of the algorithm:

Code

Go Solution

Python Solution

Java Solution

JavaScript Solution

TypeScript Solution

C++ Solution

C# Solution

C Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution

Scala Solution

Rust Solution

Complexity Analysis

Time Complexity

Calculating total sum:

For calculating the total sum we iterate through all elements of nums once. Hence the time complexity for this step is O(n).

Checking if middle element exists:

For checking if there exists a middle element in nums array, we use another loop for iterating through all elements. Apart from this all operations inside the loop are constant time operations. Hence the time complexity for this step is O(n).

Overall time complexity:

Combining the above time complexities for individual steps, the overall time complexity of this solution is O(n) + O(n) = O(n).

Space Complexity

Apart from few variables which use constant space, we do not use any extra space that is a varies with the input size. Hence the overall space complexity of this solution is O(1).

These are some of the problems we've solved using the prefix sum pattern:

• 560. Subarray Sum Equals K

That is all for this article. We will be back with more problems related to prefix sum pattern. Do not miss to check out our other articles in the LeetCode problem solutions series.

Code Recipe Limited Time Offer: Get 100% discount on the Code Recipe Membership Plan. Sign up now and get access to exclusive premium content for free. Hurry—offer only available for a limited time - Join now.