Count deletions making array fair
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 1664. Ways to Make a Fair Array – Given an integer array nums, count the indices whose removal results in the sum of elements at even indices equaling the sum at odd indices (k =
1). Follow-up: extend the algorithm to count ways after deleting exactly k elements.
https://leetcode.com/problems/ways-to-make-a-fair-array/description/
Quick Answer: This question evaluates proficiency with array manipulation, parity-aware summation, and combinatorial counting when elements are removed, situating it in the Coding & Algorithms domain.
Given a 0-indexed integer array nums, return the number of indices i such that removing nums[i] and re-indexing the remaining elements from 0 makes the sum of elements at even indices equal to the sum of elements at odd indices. An empty array has both sums equal to 0.
Constraints
- 1 <= len(nums) <= 200000
- -10^9 <= nums[i] <= 10^9
- Use 64-bit integer arithmetic for sums
- Target time complexity: O(n)
- Target extra space: O(1)
Solution
from typing import List
def count_fair_deletions(nums: List[int]) -> int:
total_even = 0
total_odd = 0
for i, v in enumerate(nums):
if i % 2 == 0:
total_even += v
else:
total_odd += v
left_even = 0
left_odd = 0
ans = 0
for i, v in enumerate(nums):
if i % 2 == 0:
rem_even = total_even - left_even - v
rem_odd = total_odd - left_odd
else:
rem_even = total_even - left_even
rem_odd = total_odd - left_odd - v
if left_even + rem_odd == left_odd + rem_even:
ans += 1
if i % 2 == 0:
left_even += v
else:
left_odd += v
return ans
Explanation
Let total_even and total_odd be the sums at even and odd indices in the original array. As you iterate, maintain left_even and left_odd for the prefix before index i. If you remove nums[i], the suffix elements (to the right of i) shift left by one, flipping their parity: former even-indexed suffix elements contribute to the new odd sum and vice versa. Therefore, for each i, the new even sum is left_even + (total_odd - left_odd - (nums[i] if i is odd else 0)), and the new odd sum is left_odd + (total_even - left_even - (nums[i] if i is even else 0)). Count i when these are equal. This yields an O(n) time and O(1) extra space solution.
Time complexity: O(n). Space complexity: O(1).
Hints
- Compute total sums at even and odd indices once.
- Scan left-to-right maintaining prefix sums left_even and left_odd.
- When removing index i, the suffix elements shift left by one, flipping their parity. New even sum = left_even + suffix_odd; new odd sum = left_odd + suffix_even.