algoadvance

Leetcode 1991. Find the Middle Index in Array

Problem Statement

Find the Middle Index in Array

Given a 0-indexed integer array nums, find the leftmost middleIndex (if exists) such that:

If there is no such index, return -1. Note that middleIndex should not be considered to be part of either the left sum or the right sum.

Example:

Input: nums = [2, 3, -1, 8, 4]
Output: 3
Explanation: 
The sum of the numbers to the left of index 3 is: 2 + 3 + -1 = 4
The sum of the numbers to the right of index 3 is: 4 = 4

Clarifying Questions

  1. Can the array contain negative numbers? Yes, the array can contain negative as well as positive integers.

  2. Will the array always have at least one element? Constraints typically state the array size, but let’s assume the array will have at least one element for now.

  3. Are there any constraints on time complexity? While no explicit constraints are provided, we should aim for an optimal solution. Ideally, a solution better than O(n^2) should be considered.

Strategy

To find the middle index, we can use the following approach:

  1. Calculate the total sum of the array.
  2. Initialize a variable leftSum to 0. This will be used to store the sum of elements to the left of the current index.
  3. Iterate over the array and for each element:
    • Calculate the sum of elements to the right using the formula: totalSum - leftSum - nums[i].
    • Check if leftSum is equal to the right sum.
    • If they are equal, return the current index.
    • Update leftSum by adding the current element.
  4. If no such index is found, return -1.

Code

Here’s the Java solution for the problem:

public class Solution {
    public int findMiddleIndex(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        
        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        
        return -1;
    }
}

Explanation

  1. Calculate Total Sum:
    • Compute the total sum of all elements in the array.
  2. Iterate and Check:
    • Initialize leftSum to 0.
    • For each element, compute the right sum and check if it matches with leftSum.
    • If it matches, return the current index.
    • Update leftSum to include the current element.
  3. Return -1:
    • If no such index is found after iterating through the array, return -1.

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the array. This is because we are iterating through the array twice:

The space complexity is O(1) as we are using only a few extra variables.

This approach ensures that we find the solution efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI