data_structures.arrays.equilibrium_index_in_array

Find the Equilibrium Index of an Array.

Reference: https://www.geeksforgeeks.org/equilibrium-index-of-an-array

Python doctest can be run with:

python -m doctest -v equilibrium_index_in_array.py

Given an array arr of size n, return an equilibrium index if one exists; otherwise return -1.

An equilibrium index is an index where the sum of all elements to the left equals the sum of all elements to the right.

Functions

equilibrium_index(→ int)

Find the first equilibrium index of an array.

Module Contents

data_structures.arrays.equilibrium_index_in_array.equilibrium_index(arr: list[int]) → int

Find the first equilibrium index of an array. Args:

arr: The input array of integers.

Returns:

The first equilibrium index, or -1 if none exists.

Examples:

>>> equilibrium_index([])
-1
>>> equilibrium_index([5])
0
>>> equilibrium_index([-7, 1, 5, 2, -4, 3, 0])
3
>>> equilibrium_index([2, 4, 6, 8, 10, 3])
-1
>>> equilibrium_index([1, 2, 3, 4, 5])
-1
>>> equilibrium_index([1, 1, 1, 1, 1])
2
>>> equilibrium_index([0, 0, 0])
0
>>> equilibrium_index([-1, -1, -1])
1
>>> equilibrium_index([1, -1, 0])
2

Time Complexity:

O(n), where n is the length of the array.

Space Complexity:

O(1), using only constant extra space.