Find the Middle Index in Array - Practice Coding Problems

Find the Middle Index in Array - Problem

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.

Input & Output

Example 1 — Basic Case

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

› Output: 0

💡 Note: At index 0: left sum = 0 (no elements), right sum = 1 + (-1) = 0. Since 0 = 0, return 0.

Example 2 — Middle Balance

$ Input: nums = [2,3,1,0,4]

› Output: 2

💡 Note: At index 2: left sum = 2 + 3 = 5, right sum = 0 + 4 = 4. Not equal. At index 2: left sum = 2 + 3 = 5, right sum = 0 + 4 = 4. Continue checking...

Example 3 — No Balance Point

$ Input: nums = [1,7,3,6,5,6]

› Output: -1

💡 Note: No index satisfies the condition where left sum equals right sum.

Constraints

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,1,-1] where we need to find balance point

Process

Check each index for equal left and right sums

Output

Return leftmost index where balance exists

Key Takeaway

🎯 Key Insight: Use total sum to calculate right sum efficiently: rightSum = totalSum - leftSum - currentElement

Asked in

a Amazon 45 M Microsoft 32 f Facebook 28 G Google 21

The key insight is to use the total sum to calculate right sum efficiently. Instead of recalculating sums repeatedly, compute total sum once, then use rightSum = totalSum - leftSum - currentElement. Best approach is prefix sum with Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n²)	O(1)	For each index, calculate left sum and right sum separately
Prefix Sum Optimization	O(n)	O(1)	Calculate total sum first, then use running sum to find left and right sums efficiently

Brute Force — Algorithm Steps

For each index i from 0 to n-1
Calculate sum of elements from 0 to i-1 (left sum)
Calculate sum of elements from i+1 to n-1 (right sum)
If left sum equals right sum, return i

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Index 0

Left sum = 0, Right sum = 7+(-3)+2 = 6

Check Index 1

Left sum = 1, Right sum = -3+2 = -1

Check Index 2

Left sum = 1+7 = 8, Right sum = 2. Not equal

Check Index 3

Left sum = 1+7+(-3) = 5, Right sum = 0. Not equal

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        int leftSum = 0;
        int rightSum = 0;
        
        // Calculate left sum
        for (int j = 0; j < i; j++) {
            leftSum += nums[j];
        }
        
        // Calculate right sum
        for (int j = i + 1; j < numsSize; j++) {
            rightSum += nums[j];
        }
        
        if (leftSum == rightSum) {
            return i;
        }
    }
    
    return -1;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple JSON array parsing
    int nums[1000];
    int count = 0;
    char* ptr = line + 1; // Skip opening bracket
    
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[count++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, count);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Outer loop runs n times, inner loops calculate sums taking O(n) each

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses a few variables for sum calculations

✓ Linear Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler