Introduction

In this blog post, we will explore how to solve the LeetCode problem "927" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given an array arr which consists of only zeros and ones, divide the array into three non-empty parts such that all of these parts represent the same binary value. If it is possible, return any [i, j] with i + 1 < j, such that: arr[0], arr[1], ..., arr[i] is the first part, arr[i + 1], arr[i + 2], ..., arr[j - 1] is the second part, and arr[j], arr[j + 1], ..., arr[arr.length - 1] is the third part. All three parts have equal binary values. If it is not possible, return [-1, -1]. Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value. Example 1: Input: arr = [1,0,1,0,1] Output: [0,3] Example 2: Input: arr = [1,1,0,1,1] Output: [-1,-1] Example 3: Input: arr = [1,1,0,0,1] Output: [0,2] Constraints: 3 <= arr.length <= 3 * 104 arr[i] is 0 or 1

Explanation

Here's a breakdown of the approach, followed by the code:

• Find the number of ones: The core idea is to determine the count of ones in the entire array. If the count isn't divisible by 3, it's impossible to split the array into three equal parts.

• Locate the start and end indices of the first and last parts: Find the starting indices of the first and third parts that contain the required number of ones. This avoids issues with leading zeros.

• Compare the three parts: Compare the binary values of the three segments. Due to leading zeros this comparison should be done by ensuring that the three segments are of equal lengths when the leading zeros are truncated.

• Time & Space Complexity: O(n) time, O(1) space.

Code

    def threeEqualParts(arr):
    ones = sum(arr)
    if ones % 3 != 0:
        return [-1, -1]
    if ones == 0:
        return [0, 2]

    target_ones = ones // 3
    first_start = -1
    second_start = -1
    third_start = -1
    count = 0

    for i in range(len(arr)):
        if arr[i] == 1:
            count += 1
            if first_start == -1:
                first_start = i
            elif count == target_ones + 1 and second_start == -1:
                second_start = i
            elif count == 2 * target_ones + 1 and third_start == -1:
                third_start = i

    len_suffix = len(arr) - third_start
    if first_start + len_suffix > second_start or second_start + len_suffix > third_start:
        return [-1, -1]

    for i in range(len_suffix):
        if arr[first_start + i] != arr[second_start + i] or arr[first_start + i] != arr[third_start + i]:
            return [-1, -1]

    return [first_start + len_suffix - 1, second_start + len_suffix]