Quick Overview

Find the earliest fixed-length block to remove so the remaining array has equal even- and odd-index sums, accounting for the reindexed suffix.

Find the Earliest Contiguous Removal That Balances Index Sums

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement `smallest_balanced_removal(nums, k)` for an integer array `nums` and an integer `k` satisfying `1 <= k <= len(nums)`. Use the exact integer representation described below for this console interface. Delete exactly one contiguous block of `k` elements. Keep the remaining elements in their original relative order and reindex the resulting array starting at zero. Find the smallest zero-based starting index of a deletion for which the sum at even indices equals the sum at odd indices in that resulting array. Return `-1` if no deletion works. If the entire array is removed, both sums are zero. The deletion may begin at the first element or end at the last element. Do not compare the original index parities after deletion: elements to the right of the removed block move left by `k` positions. ### Exact integer representation This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude. - `nums` is an array of strings representing signed integers. - `k` is a string representing a positive integer. Its numeric value satisfies the bounds above. - Return the starting index as a decimal string, or `"-1"` if no deletion works. - A canonical decimal string is `"0"`, a sequence of ASCII digits beginning with `1` through `9`, or `"-"` followed by such a sequence. It has no leading plus sign, leading zeroes, whitespace, or negative zero. - Arithmetic and equality refer to the represented integer values. Do not use rounding, fixed-width overflow, or modular equality. ### Examples ```text smallest_balanced_removal(["2","1","6","4"], "1") -> "1" ``` Removing the element at index 1 leaves integer values `[2,6,4]`. Its even-index sum is `2 + 4 = 6`, equal to its odd-index sum of `6`. Starting at index 0 does not work. ```text smallest_balanced_removal(["1","5","5","1"], "2") -> "1" ``` Removing the two middle elements leaves integer values `[1,1]`, whose even- and odd-index sums are equal. Removing the first two elements does not balance the result.

Overview: Find the earliest fixed-length block to remove so the remaining array has equal even- and odd-index sums, accounting for the reindexed suffix.

Implement `smallest_balanced_removal(nums, k)` for an integer array `nums` and an integer `k` satisfying `1 <= k <= len(nums)`. Use the exact integer representation described below for this console interface. Delete exactly one contiguous block of `k` elements. Keep the remaining elements in their original relative order and reindex the resulting array starting at zero. Find the smallest zero-based starting index of a deletion for which the sum at even indices equals the sum at odd indices in that resulting array. Return `-1` if no deletion works. If the entire array is removed, both sums are zero. The deletion may begin at the first element or end at the last element. Do not compare the original index parities after deletion: elements to the right of the removed block move left by `k` positions. ### Exact integer representation This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude. - `nums` is an array of strings representing signed integers. - `k` is a string representing a positive integer. Its numeric value satisfies the bounds above. - Return the starting index as a decimal string, or `"-1"` if no deletion works. - A canonical decimal string is `"0"`, a sequence of ASCII digits beginning with `1` through `9`, or `"-"` followed by such a sequence. It has no leading plus sign, leading zeroes, whitespace, or negative zero. - Arithmetic and equality refer to the represented integer values. Do not use rounding, fixed-width overflow, or modular equality. ### Examples ```text smallest_balanced_removal(["2","1","6","4"], "1") -> "1" ``` Removing the element at index 1 leaves integer values `[2,6,4]`. Its even-index sum is `2 + 4 = 6`, equal to its odd-index sum of `6`. Starting at index 0 does not work. ```text smallest_balanced_removal(["1","5","5","1"], "2") -> "1" ``` Removing the two middle elements leaves integer values `[1,1]`, whose even- and odd-index sums are equal. Removing the first two elements does not balance the result.

Constraints

  • nums is nonempty and contains canonical signed decimal strings.
  • k is a canonical positive decimal string representing 1 through len(nums).
  • Delete exactly k contiguous elements and reindex; return the earliest valid start or "-1", as a string.
  • No finite value or length cap is introduced; whole-array deletion balances zero sums.

Examples

Input: (['2', '1', '6', '4'], '1')

Expected Output: '1'

Explanation: The first source example requires a parity flip in the shifted suffix.

Input: (['1', '5', '5', '1'], '2')

Expected Output: '1'

Explanation: The second source example preserves suffix parity for even k.

Hints

  1. The suffix shifts left by exactly the deletion length.
  2. If several deletions work, the smallest starting index is required.

Loading coding console...

Show the approach

Approach

Let prefix[j] be the alternating sum of the original entries before j, with even positions positive. For a deletion starting at s, the left part contributes prefix[s]. The original alternating sum of the surviving suffix is prefix[n]-prefix[s+k]; moving it left by k preserves its sign when k is even and reverses it when k is odd. The difference between the reindexed even and odd sums is therefore their sum with this sign adjustment. Test that exact difference for zero while visiting starts in increasing order. Every legal deletion is examined, and the first zero gives precisely the required earliest index; no zero yields "-1". The entire-array case evaluates two empty contributions. All numeric values use the exact decimal representation in the public statement. Input arrays/strings must be materialized by the host; container indices and lengths use their native representable types, while mathematical values and sums use arbitrary precision. No additional problem-domain magnitude bound is imposed. Python parses decimal chunks of at most nine digits, avoiding its configurable whole-string conversion limit.

Time complexity:
O(n) arbitrary-precision additions/subtractions after decimal parsing; include the digit cost of parsing and each accumulated sum operation.
Space complexity:
O(n) arbitrary-precision prefix values; total storage depends on their digit lengths.