Quick Overview

This question evaluates proficiency with array manipulation, parity-aware summation, and combinatorial counting when elements are removed, situating it in the Coding & Algorithms domain.

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/

Overview: 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)

Hints

  1. Compute total sums at even and odd indices once.
  2. Scan left-to-right maintaining prefix sums left_even and left_odd.
  3. 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.

Loading coding console...

Show the approach

Approach

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)