MediumNo. 1664
Ways to Make a Fair Array — LeetCode 1664 Python Solution
- Pattern
- Prefix Sum
- Topics
- Array, Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given an integer array nums. You can choose exactly one index (0-indexed) and remove the element.
Example
- Input
- nums = [2,1,6,4]
- Output
- 1
- Explanation
- Remove index 0: [1,6,4] -> Even sum: 1 + 4 = 5. Odd sum: 6. Not fair.
Python solution
class Solution:
def waysToMakeFair(self, nums: List[int]) -> int:
s1, s2 = sum(nums[::2]), sum(nums[1::2])
ans = t1 = t2 = 0
for i, v in enumerate(nums):
ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2
ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v
t1 += v if i % 2 == 0 else 0
t2 += v if i % 2 == 1 else 0
return ansComplexity
- Time
- O(n)where n is the length of the array
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 1664. Ways to Make a Fair Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0238 | Product of Array Except Self | Medium |
| 0303 | Range Sum Query - Immutable | Easy |
| 0304 | Range Sum Query 2D - Immutable | Medium |
| 0724 | Find Pivot Index | Easy |
| 0798 | Smallest Rotation with Highest Score | Hard |
| 0848 | Shifting Letters | Medium |
Frequently asked questions
- How hard is LeetCode 1664. Ways to Make a Fair Array?
LeetCode 1664. Ways to Make a Fair Array is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1664. Ways to Make a Fair Array?
The Python solution on this page runs in O(n), where n is the length of the array.
- What is the space complexity of LeetCode 1664. Ways to Make a Fair Array?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 1664. Ways to Make a Fair Array cover?
LeetCode 1664. Ways to Make a Fair Array is tagged Array and Prefix Sum on LeetCode.