Quick Overview

Find the maximum length of equal arrays obtainable by merging adjacent positive values into their sums, or report that equality is impossible.

Maximize Equal Array Length After Contiguous Sum Merges

Company: Microsoft

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given two nonempty arrays of positive integers, `a` and `b`. In either array, you may replace a contiguous group of elements with one element equal to their sum. You may repeat this operation independently on both arrays. Implement `maxCommonLength(a, b)`. Return the maximum possible length of the resulting arrays when they are exactly equal, element by element. Return `-1` if they cannot be made equal. ### Rules and Constraints - Merging preserves element order. You may merge adjacent groups but cannot split an element, reorder elements, or remove values. - You may perform no operations on an array that already has the desired form. - Each array has between 1 and 100,000 elements. Every value is between 1 and 1,000,000,000. - Intermediate and total sums must be represented exactly. ### Example 1 ```text a = [1, 2, 3, 3] b = [3, 3, 3] Output: 3 ``` Merge the first two elements of `a` to obtain `[3, 3, 3]`. Length 3 is maximal because `b` starts with only three elements and merging cannot increase its length. ### Example 2 ```text a = [1, 2] b = [4] Output: -1 ``` No allowed sequence of merges makes these arrays equal.

Overview: Find the maximum length of equal arrays obtainable by merging adjacent positive values into their sums, or report that equality is impossible.

You are given two nonempty arrays of positive integers, `a` and `b`. In either array, you may replace a contiguous group of elements with one element equal to their sum. You may repeat this operation independently on both arrays. Implement `maxCommonLength(a, b)`. Return the maximum possible length of the resulting arrays when they are exactly equal, element by element. Return `-1` if they cannot be made equal. ### Rules and Constraints - Merging preserves element order. You may merge adjacent groups but cannot split an element, reorder elements, or remove values. - You may perform no operations on an array that already has the desired form. - Each array has between 1 and 100,000 elements. Every value is between 1 and 1,000,000,000. - Intermediate and total sums must be represented exactly. ### Example 1 ```text a = [1, 2, 3, 3] b = [3, 3, 3] Output: 3 ``` Merge the first two elements of `a` to obtain `[3, 3, 3]`. Length 3 is maximal because `b` starts with only three elements and merging cannot increase its length. ### Example 2 ```text a = [1, 2] b = [4] Output: -1 ``` No allowed sequence of merges makes these arrays equal.

Constraints

  • Both arrays are nonempty, with lengths from 1 through 100000.
  • Every element is a positive integer from 1 through 1000000000.
  • Only contiguous order-preserving sum merges are allowed; elements cannot be split, reordered or removed.
  • Return the maximum equal resulting length, or -1 when totals differ.
  • Intermediate and total sums are exact; a total is at most 100000000000000.

Examples

Input: ([1, 2, 3, 3], [3, 3, 3])

Expected Output: 3

Explanation: Published sample 1: merging 1 and 2 yields three matching elements.

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

Expected Output: -1

Explanation: Published sample 2: totals differ, and every merge preserves the total.

Loading coding console...

Show the approach

Approach

A resulting element corresponds to a contiguous segment of each original array. Therefore each boundary between completed segments must be a cumulative sum that appears in both arrays. Since every input element is positive, each array's prefix sums are strictly increasing.

Use two indices and two cumulative sums. Advance the side with the smaller cumulative sum; when they are equal, advance either available side. Count each equality reached after an advance. Once one side is exhausted, advance the remaining side until both are exhausted. If the final totals differ, return -1; otherwise return the number of common positive prefix sums found.

This is a merge of two increasing prefix-sum sequences. When one current sum is smaller, it cannot equal the other current sum or any later, larger sum until its own index advances. Thus the scan misses no common boundary and counts each once. All common boundaries can be used simultaneously in increasing order: consecutive common sums define equal positive segment totals on the two sides. This constructs a valid result with one element per common boundary, while no result can have more boundaries than the number shared. Equal totals always include the final boundary; unequal totals cannot be repaired because merging preserves the total.

Each iteration consumes exactly one input element, giving O(a.length + b.length) time and O(1) auxiliary space. Java and C++ accumulate in 64-bit integers. Python integers are exact, and every allowed JavaScript sum is at most 10^14, below its exact-integer limit 2^53.

Time complexity:
O(a.length + b.length).
Space complexity:
O(1) auxiliary space.