We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Three Equal Parts

Number: 963

Difficulty: Hard

Paid? No

Companies: Hotstar

Problem Description

Given an array arr consisting of only zeros and ones, divide the array into three non-empty parts such that each part represents the same binary value. Here, the entire part (including any leading zeros) is considered when determining the binary value. If such a division is possible, return any [i, j] such that:

  • arr[0...i] is the first part,
  • arr[i+1...j-1] is the second part, and
  • arr[j...end] is the third part, with i + 1 < j. If no such division exists return [-1, -1].

Key Insights

  • The total number of 1's must be divisible by 3; if there are no 1's, any split works.
  • Use the positions of the first 1 in each of the three parts to identify a candidate pattern.
  • The pattern (subarray starting at these indices) must be the same for each part. Additionally, there must be enough zeros at the end of the array to cover any trailing zeros.
  • Walking through the array in a single pass helps track where parts should begin.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array. Space Complexity: O(1)

Solution

The solution first counts the total ones. If the count is 0, then the array has only zeros and any valid partition works (e.g., [0, length - 1]). If the total number of 1's is not divisible by 3, the answer is [-1, -1]. Otherwise, we determine the starting indices for the first 1 in each of the three parts. The idea is to use the third part as the "pattern" reference, and then match the corresponding portions in the first and second parts against it. Finally, we check that there are enough trailing zeros after the identified pattern to make the three parts valid. This approach relies only on pointer manipulations and simple comparisons, giving an efficient linear time solution with constant extra space.

Code Solutions

# Python solution for "Three Equal Parts"
class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        n = len(arr)
        total_ones = sum(arr)
        # If there are no ones, any split is valid (all parts are zero).
        if total_ones == 0:
            return [0, n - 1]
        # If total ones are not divisible by 3, it's impossible.
        if total_ones % 3 != 0:
            return [-1, -1]
        
        ones_per_part = total_ones // 3
        first = second = third = -1
        one_count = 0
        
        # Identify the first index of the 1 in each part.
        for i, val in enumerate(arr):
            if val == 1:
                one_count += 1
                if one_count == 1:
                    first = i
                elif one_count == ones_per_part + 1:
                    second = i
                elif one_count == 2 * ones_per_part + 1:
                    third = i
        
        # Determine the length of the candidate pattern from the third part.
        len_candidate = n - third
        # Validate that the segments match for all three parts.
        if first + len_candidate > second or second + len_candidate > third:
            return [-1, -1]
        for i in range(len_candidate):
            if arr[first + i] != arr[second + i] or arr[first + i] != arr[third + i]:
                return [-1, -1]
        
        # The partitions end at:
        return [first + len_candidate - 1, second + len_candidate]
← Back to All Questions